Программа грамматического разбора использует таблицу правил подстановки и стек, содержащий уже рассмотренную и возможно частично свернутую часть строки. Исходная строка дополняется ограничителем ┴, первый символ строки заносится в стек. Применение очередного правила начинается с сопоставления k верхних символов стека с образцом x1...xk. При несовпадении применяется следующее по порядку правило. При совпадении x1...xk заменяется на y1...ym (если y1...ym пусто, то замена не производится). Далее, при необходимости, выполняется семантическая подпрограмма. Затем, если задан символ *, то в вершину стека добавляется очередной символ входной строки. Выполняется переход к правилу, помеченному M2.
Пример грамматического разбора предложения a+b*c+d┴:
Правила подстановки Флойда
(после упорядочения)
|
|
Метка
|
Стек
|
Остаток строки
|
Правило
|
(1) Z0
|
ид
|
T
|
|
*
|
T1
|
|
Z0
|
a
|
+b*c+d┴
|
1
|
(2)
|
|
|
ош1
|
|
|
|
T1
|
T+
|
b*c+d┴
|
5
|
(3) T1
|
T*
|
|
|
*
|
*1
|
|
S1
|
S+
|
b*c+d┴
|
8
|
(4)
|
S+T
|
S
|
|
|
S1
|
|
T0
|
S+b
|
*c+d┴
|
10
|
(5)
|
T
|
S
|
|
|
S1
|
|
T1
|
S+T*
|
C+d┴
|
3
|
(6)
|
|
|
ош2
|
|
|
|
*1
|
S+T*c
|
+d┴
|
12
|
(7) S1
|
S┴
|
Z
|
вых
|
|
|
|
T1
|
S+T+
|
d┴
|
4
|
(8)
|
S+
|
|
|
*
|
T0
|
|
S1
|
S+
|
d┴
|
8
|
(9)
|
|
|
ош3
|
|
|
|
T0
|
S+d
|
┴
|
10
|
(10)T0
|
ид
|
T
|
|
*
|
T1
|
|
T1
|
S+T┴
|
|
4
|
(11)
|
|
|
ош4
|
|
|
|
S1
|
S┴
|
|
7
|
(12)*1
|
T*ид
|
T
|
|
*
|
T1
|
|
|
Z
|
выход
|
|
(13)
|
|
|
ош5
|
|
|
|
|
|
|
|
|
Скачать 0.64 Mb.