LL(1)-анализ

Для грамматики G построить эквивалентную LL(1)-грамматику G1.Для грамматики G1 построить LL(1) анализатор и продемонстрировать его работу на ba.
SAB|A
Ba
AbA|Ac|bC|a
CCc
...

Для грамматики G построить эквивалентную LL(1)-грамматику G1.Для грамматики G1 построить LL(1) анализатор и продемонстрировать его работу на ba.
SAB|A
Ba
AbA|Ac|bC|a
CCc

Для грамматики G построить эквивалентную LL(1)-грамматику G1.Для грамматики G1 построить LL(1) анализатор и продемонстрировать его работу на ba.
SAB|A
Ba
AbA|Ac|bC|a
CCc

1. FIRST(α)∩ FIRST(β)=
2. Если  FIRST(α), FIRST(β)∩FOLLOW(A)=
Для обеспечения дальнейшей работы необходимы следующие понятия:
Пусть a — промежуточная цепочка вывода в КС-грамматике G = <N, T, P, S>. Определим FIRST (a), как множество терминальных символов, которые являются первыми символа­ми цепочек, выводимых из a.
Цепочка aÎ {N È Т}* называется аннулирующей, если a=> *
Правило грамматики вида A®, где АN, — пустой символ, называется также аннулирующим.
Для данного правила (А ®a)Î Р, где AÎ N, aÎ {NUT}* определим
ВЫБОР (А®a)=FIRST(a), если a—не аннулирующая, и
ВЫБОР (А®a) = FIRST (a)\{}  FOLLOW (А), если a — аннулирующая цепочка.
При этом FOLLOW (А) — множество следую­щих за А терминалов в промежуточной цепочке, выводимой из S$, где S — аксиома грамматики и $ — концевой маркер.
То есть ВЫБОР(Аα) = FIRST(αFOLLOW(A)).
Таким образом, построение множеств ВЫБОР и их пересечений дает возможность проверить, является ли заданная КС-грамматика грамматикой типа LL(1).
Проверим, является ли заданная КС – грамматика грамматикой типа LL(1). Построим множества ВЫБОР:
ВЫБОР(SAC)={a,b,$}
ВЫБОР(CB)={a}
ВЫБОР(C)={$}
ВЫБОР(Ba)={ a}
ВЫБОР(AaA’)={a}
ВЫБОР(AbA)={b}
ВЫБОР(A’сA’)={c}
ВЫБОР(A’)={a,$}
Так как множества ВЫБОР не пересекаются, данная грамматика является 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AC
SAC
Ошибка
SAC
A
AaA’
AbA
Ошибка
Ошибка
A’
A’
Ошибка
A’сA’
A’
B
Ba
Ошибка
Ошибка
Ошибка
C
CB
Ошибка
Ошибка
C
Проверим работу LL(1)-анализатора путем построения его последовательности конфигураций при обработке слова ba.
Процесс разбора цепочки заключается в следующем: на каждом шаге разбора считывается верхний символ v из стека анализатора и берется крайний символ t входной цепочки.
Если v – терминальный символ, совпадает с t, то они оба уничтожаются и происходит сдвиг.
Если v – терминальный символ, не совпадает с t, то сигнализируется ошибка.