Построение таблицы разбора для LL (1) — грамматики

После построения множеств first и follow можно сформировать саму таблицу разбора следующим образом.

Для всех продукций, А грамматики выполняем:

• 1. Для всех терминалов а, принадлежащих first (), в клетку [А, а] таблицы разбора записываем продукцию А.
• 2. Если принадлежит first (), то для всех b, принадлежащих follow (А), в клетку [A, b] записываем продукцию А.

Во все остальные клетки таблицы записываем признак ошибки.

Алгоритм работы таблично-управляемого анализатора для LL (1)-грамматики

Алгоритм:

Вначале входной буфер содержит лексические знаки исходной программы. В стеке, на дне, лежит стартовый нетерминал. Алгоритм берет символ из вершины стека (Х), берет первый символ и входного буфера (а), и эта пара определяет дальнейшие действия. 3 варианта:

• 1) Х=а=$, тогда алгоритм успешно завершает работу.
• 2) Х=а$, тогда анализатор удаляет Х из стека и перемещает указатель входного буфера на следующий символ, иначе выдается ошибка.
• 3) если Х — нетерминал, тогда алгоритм обращается к ячейке М[Х, а]. Если в этой ячейке содержится продукция Х>UVW, то в стеке Х заменяется на UVW, причем U должно оказаться сверху. В этой ячейке содержится признак ошибки, тогда необходимо запустить процедуру выхода из ошибочной ситуации.