Проектирование трансляторов
│ / нет ┌──┴──┐
│ < 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