Проектирование трансляторов

┌────────────┤ │

│ / нет ┌──┴──┐

│ < 6 >────┐ │ 12 │

│ / │ └──┬──┘

│ да│ │ │да

┌──┴──┐ ┌──┴──┐ │нет /

│ 9 │ │ 7 │ ├────<11>

└──┬──┘ └──┬──┘ │ /

│ ├──────┘ │

│ < / > ┌──┴──┐

└──────────< 8 >────────┤ 10 │

/ └─────┘


Рис. 2. Блок-схема алгоритма нахождения самых левых символов


Обозначения к алгоритму:

1. l = 1.

2. i = 1 - номер символа в синтаксическом правиле.

3. ] P: Ul ::= Si z - является ли i-ый символ самым левым

в синтаксическом правиле l.

4. Si записать в L(Ul): (L(Ul) = L (Ul) U Si).

5. k = 1.

6. ] P: Uk ::= Ul z - является ли Ul самым левым символом Uk

при условии, что Si C L(Ul).

7. L (Uk) = L (Uk) U Ul U Si - дополнить символами Ul и Si

мн-во L(Ul)

8. k < l (k, l - номера синтаксических правил),

проверка окончания цепочки.

9. k = k + 1.

10. i = i + 1.

11. Si = ; - завершилось ли синтаксическое правило.

12. l = l + 1.

13. l <= (L - общее число грамматических правил в грамматике).


Допущения к алгоритму:

- синтаксические правила отделены друг от друга ";"

- левая часть не отделяется от правой, и левая часть (т.е.

контекстно-свободная грамматика) всегда состоит из одного символа.


Аналогично можно построить множество самых правых символов.

Теперь перейдем к нахождению матрицы предшествования.

Блок-схема алгоритма построения матрицы предшествования, ис-

пользующая определения 1а-3а, представлена на рис. 3. Используют-

ся следующие условные обозначения:

i, j - индексы определяют номер символа в списке символов

языка.

M[i,j] - элемент матрицы предшествования;

l, k - номера синтаксических правил языка.


┌─────┐

│ 1 │

└──┬──┘

│

┌──┴──┐

│ 2 ├─────────────────────────┐

└──┬──┘ │

│ │

┌─────┐ / │

│ 4 │────< 3 >─────────────────┐ │

└─────┘ / │ │

│ │ │

┌──┴──┐ │ │

│ 5 │ │ │

└──┬──┘ │ │

├────────┐ │ │

/ да / │ │ │

┌──────────< 7 >────< 6 > │ │ │

│ / / │ │ │

│ │нет │нет │ │ │

│┌─────┐ │ / ┌──┴──┐ │ │

└┤ 8 ├─────┴──────< 9 >───┤ 10 │ │ │

└─────┘ / < └─────┘ │ │

│> │ │

┌──┴──┐ │ │

│ 11 │ │ │

└──┬──┘ │ │

├────────┐ │ │

┌─────┐ да / да / │ │ │

│ 14 ├───<13>────<12> │ │ │

└──┬──┘ / / │ │ │

└────────┴────────┤ │ │ │

/ ┌──┴──┐ │ │

<15>───┤ 16 │ │ │

/ < └─────┘ │ │

│ │ ┌──┴──┐

┌──┴──┐ │ │ 29 │

│ 17

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: