3.2.3. Конструирование таблиц предсказывающего анализатора
Для конструирования таблиц предсказывающего анализатора по грамматике G может быть использован алгоритм, основанный на следующей идее. Предположим, что A -> u - правило вывода грамматики и a FIRST(u). Тогда анализатор делает развертку A по u, если входным символом является a. Трудность возникает, когда u=e или u *e . В этом случае нужно развернуть A в u, если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и $ FOLLOW(A).
Алгоритм 3.4. Построение таблиц предсказывающего анализатора.
Для каждого A -> u правила вывода грамматики выполнить шаги 1 и 2.
Шаг 1. Для каждого терминала a из FIRST(u) добавить A -> u к M[A,a] .
Шаг 2. Если e FIRST(u), добавить A -> u к M[A,b] для каждого терминала b из FOLLOW(A). Если e FIRST(u) и $ FOLLOW(A), добавить A -> u к M[A,$] .
Шаг 3. Положить все неопределенные входы равными error.
Пример 3.3. Применим алгоритм 3.4 к грамматике (*). Поскольку FIRST(TE`)=FIRST(T)={(,id} , в соответствии с правилом вывода E -> TE` входы M[E,(] и M[E,id] становятся равными E -> TE`. В соответствии с правилом вывода E` -> +TE` вход M[E`,+] равен E` -> +TE` . В соответствии с правилом вывода E` -> e входы M[E`,)] и M[E`,$] равны E` -> e , поскольку FOLLOW(E`)= { ),$} .
Таблица анализа, построенная алгоритмом 3.4, приведена на рис. 3.4.
3.2.4. Ll(1)-грамматики
Алгоритм 3.4 для построения таблицы анализа M может быть применен к любой грамматике. Однако для некоторых грамматик M может иметь неоднозначно определенные входы. Например, если грамматика леворекурсивна или неоднозначна, M будет иметь по крайней мере один неоднозначно определенный вход.
Грамматики, для которых таблицы анализа не имеют неоднозначно определенных входов, называются LL(1) . Первое L означает сканирование входа слева-направо, второе L означает, что строится левый вывод, 1 - что на каждом шаге для принятия решения используется один символ непросмотренной цепочки.
Можно показать, что алгоритм 3.4 для каждой LL(1) - грамматики G строит таблицы, по которым распознаются все цепочки из L(G) и только они.
LL(1) - грамматики имеют несколько отличительных свойств. Неоднозначная или леворекурсивная грамматика не может быть LL(1). Можно также показать, что грамматика G является LL(1) тогда и только тогда, когда для двух правил вида A -> u|v выполняется следующее:
- ни для какого терминала a одновременно из u и v не выводятся строки, начинающиеся с a ;
- только из одной из строк u или v может выводиться пустая строка;
- если v *e, то из u не выводится никакая строка, начинающаяся с терминала из FOLLOW(A).
Язык, для которого можно построить LL(1)- грамматику, называют LL(1)-языком.
Если таблица анализа имеет неоднозначно определенные входы, то грамматика не является LL(1). Примером может служить следующая грамматика:
Эта грамматика неоднозначна, что иллюстрируется рис.3.7. Поскольку грамматика неоднозначна, она не является LL(1). Проблема, порождает ли грамматика LL- язык, алгоритмически неразрешима.
Основная трудность при использовании предсказывающего анализа - это написание такой грамматики для входного языка, чтобы по ней можно было построить предсказывающий анализатор. Иногда с помощью некоторых простых преобразований не - LL(1) грамматику можно привести к LL(1)- виду. Среди этих преобразований наиболее очевидными являются левая факторизация и удаление левой рекурсии. Здесь необходимо сделать два замечания. Во-первых, не всякая грамматика после этих преобразований становится LL(1) и, во-вторых, после удаления левой рекурсии и левой факторизации получающаяся грамматика может стать трудно понимаемой.