Построение LL(1)-анализатора

i. Для грамматики G = {{S,A,B}, {a,c,b}, {P},S}
P:
SSAbB|a
Aab|aa|
BBc|
Постройте эквивалентную LL(1)-грамматику G1
ii. Постройте LL(1)-анализатор для G1
iii. Укажите последовательность конфигураций анализатора при обработке слова aabb
...

Построение LL(1)-анализатора

Построение LL(1)-анализатора

ВЫБОР (А®a)=FIRST(a), если a—не аннулирующая, и
ВЫБОР (А®a) = FIRST (a)\{}  FOLLOW (А), если a — аннулирующая цепочка.
При этом FOLLOW (А) — множество следую­щих за А терминалов в промежуточной цепочке, выводимой из S$, где S — аксиома грамматики и $ — концевой маркер.
То есть ВЫБОР(Аα) = FIRST(αFOLLOW(A)).
Таким образом, построение множеств ВЫБОР и их пересечений дает возможность проверить, является ли заданная КС-грамматика грамматикой типа LL(1).
Проверим, является ли заданная КС – грамматика грамматикой типа LL(1). Построим множества ВЫБОР:
ВЫБОР(SaS’)={a}
ВЫБОР(S’AbBS’)={a,b}
ВЫБОР(S’)={$}
ВЫБОР(BB’)={c}
ВЫБОР(B’cB’)={c}
ВЫБОР(B’)={a,b,$}
ВЫБОР(АаC)={a}
ВЫБОР(A)={b}
ВЫБОР(Ca)={a}
ВЫБОР(Cb)={b}
Так как множества ВЫБОР не пересекаются, данная грамматика является LL(1)-грамматикой.
2) Построим LL(1)-анализатор.
Для того чтобы построить LL(1)-анализатор для LL(1)-грамматики, нужно заполнить управляющую таблицу. Элементами таблицы являются либо правила, либо спецсимвол «Ошибка». Правила заполнения таковы. M[A,a]=p для всякого нетерминала A  N, правила p: Aα, a FIRST(αFOLLOW(A)). В остальных случаях – спецсимвол «Ошибка».
Таблица 1 – Управляющая таблица
a
b
c
$
S
SaS’
Ошибка
Ошибка
Ошибка
S’
S’AbBS’
S’AbBS’
Ошибка
S’
B
Ошибка
Ошибка
BB’
Ошибка
B’
B’
B’
B’cB’
B’
A
АаC
А
Ошибка
Ошибка
C
Ca
Cb
Ошибка
Ошибка
Проверим работу LL(1)-анализатора путем построения его последовательности конфигураций при обработке слова aabb.
Процесс разбора цепочки заключается в следующем: на каждом шаге разбора считывается верхний символ v из стека анализатора и берется крайний символ t входной цепочки.
Если v – терминальный символ, совпадает с t, то они оба уничтожаются и происходит сдвиг.