Стр. 54 - Информационные структуры и их преобразование
Упрощенная HTML-версия
52
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ
ПРЕОБРАЗОВАНИЕ
Нисходящий разбор
Пусть
π
= 1,2,3,… k – левый разбор цепочки W
∈
L(G). Зная
π
, можно
построить дерево разбора. Начинают с корня, помеченного начальным
символом.
Пусть 1-е правило имеет вид S = x
1
,…,x
k
. Нужно присоединить k
потомков к вершине S. Если x
i
– первый слева – нетерминал, то 2-е правило
будет иметь вид x
i
= y
1
…y
e
. По этому принципу строим все дерево.
Простая СУ – схема: Т=
N,
Σ
,
∆
, R, S
отображает разбор в левом или
правом выводе.
Правила из R, которые имеют вид А:=
α, β
, представим в виде
A:=
α
, i
α
’
, где i – номер правила.
α
’
:=
β
\T (в цепочке
β
удалим все терминальные символы)
∆
k
...
1
.
=
=
=
=
=
+ =
6,i:F
E5,)E(:F
F4,F:T
TF3,F*T:T
T2,T:E
ET1,T E:E
R
Нисходящий преобразователь (распознаватель)
Если контекстно свободная грамматика G является LL-грамматикой, то
с помощью метода итерационного спуска можно построить синтаксический
анализатор языка L(G), который явно не использует стек, однако алгоритм
его функционирования включает ряд рекурсивных процедур, которые
обычно реализуют с помощью стека.
В простейшей форме метод рекурсивного спуска предоставляет
удобную возможность построения лексического анализатора (распознавателя
символов) языка, порожденного LL(1)-грамматикой G=(N,
Σ
, P, S). Такой
лексический анализатор каждому символу из множества N
Σ
ставит в
соответствие единственную процедуру, с помощью которой для любой
строки языка можно однозначно определить, выводима она из этого символа
или нет.
T
T
F *
E T
T
+
F
i
E
(E)
F
F i
i
E
2T
3TF
4F 5E
6
1ET
2T 4F
4F 6
6
