Языки и трансляции. Мартыненко Б.К. - 176 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

174
табл.
Правило
Мн-во лок.
прав. конт-в
T
0
= T
S
, {ε}
aa
ab
bb
S → aAaa
S → aAaa
S → bAba
·{ aa }Ò
·{ aa }Ò
·{ ba }Ò
T
1
= T
A
,
{aa}
ba
aa
A → b
A → ε
—
—
T
2
= T
A
,
{ba}
bb
ba
A → b
A → ε
—
—
Этот порядок построения LL(k)-таблиц фиксируется в следующем
описании алгоритма:
Алгоритм 2.2: построение множества LL(k)-таблиц, необходимых для
анализа в данной LL(k)-грамматике.
Вход: G =(V
N
,V
T
,P,S) — LL(k)-грамматика.
Выход:
à — множество LL(k)-таблиц, необходимых для анализа в грамматике G.
Метод.
1. Построить T
0
= T
S,{ε}
и = {T
0
}.
2. Если T
A,L
∈Ã и для некоторой цепочки u ∈V
T
*
k
и
T
A,L
(u)=(A → x
0
B
1
x
1
B
2
… B
m
x
m
, ·Y
1
, Y
2
,…, Y
m
Ò), то к множеству таблиц Ã
добавить те таблицы из множества
{T
B
i
,Y
i
| i =1, 2,…, m}, которых нет в Ã.
3. Повторять шаг 2 до тех пор, пока ни одну новую LL(k)-таблицу не удастся
добавить к
Ã.
Такой момент обязательно настанет, так как для любой данной cfg G
существует только конечное число таких таблиц (число нетерминалов —
конечно, число подмножеств L
⊆ V
T
*
k
тоже конечно). Фактически же для
анализа требуются не все возможные LL(k)-таблицы, которые можно построить
для грамматики G, а только те, которые определяются описанным алгоритмом.
Алгоритм 2.3: построение k-предсказывающего алгоритма анализа.
Вход: G =(V
N
,V
T
,P,S) — LL(k)-грамматика.
Выход:
A — правильный k-предсказывающий алгоритм анализа для G.
Метод.

Страницы