LL(1)- разбор с использованием автоматов с магазинной памятью

Внутренние состояния автомата, выполняющего LL(1)- разбор, определяются нетерминальными символами грамматики, на основе которой выполняется построение автомата. Начальное внутреннее состояние определяется аксиомой. Выполняя команды управляющей таблицы, автомат осуществляет переходы между внутренними состояниями. В результате перехода символ текущего внутреннего состояния (нетерминальный символ) удаляется из вершины стека, а вместо него в стек может быть записано несколько символов, последний из которых, оказавшись в вершине стека, становится символом нового внутреннего состояния. Эти несколько символов, записываемые в стек, представляют собой правую часть правила грамматики для нетерминала, удаленного из стека. Таким образом, переход автомата из одного внутреннего состояние в другое, в случае LL(1)- разбора, - это замена в стеке левой части правила грамматики на правую часть этого правила, шаг так называемого нисходящего разбора. Поскольку правые части правил грамматики состоят не только из нетерминальных символов, в вершине стека может оказаться терминал. Если этот терминальный символ совпадает с текущим символом входной строки, такая ситуация может рассматриваться автоматом как промежуточная на пути к новому внутреннему состоянию, и автомат минует ее с помощью специальной команды (назовем ее «выброс»), удаляя терминал из вершины стека, а также перемещаясь к следующему символу по входной строке. Процесс распознавания считается успешно завершенным, т.е. входная строка считается принадлежащей языку, принимаемому автоматом, если эта входная строка полностью прочитана, а стек пуст. Вывод о некорректности входной строки делается автоматом по команде «ошибка», которая обнаруживается в управляющей таблице по окончании просмотра входной строки и невозможности при этом полностью очистить стек или при наличии запрета перехода из текущего внутреннего состояния под воздействием текущего символа входной строки.

Пример 3.

Рассмотрим процесс распознавания, например, строки i*i языка, заданного грамматикой:

1) < S >::=< E >

2) < E >::=< T >< X >

3) < X >::= + < E >

4) < T >::=< F >< Y >

5) < Y >::= * < T >

6) < F >::= i

7) < X >::= Λ

8) < Y >::= Λ

Аксиомой является символ < S >.

Управляющая таблица для автомата с магазинной памятью, выполняющего LL(1)- разбор для заданного языка, изображена на рис 9.

Рис. 9. Управляющая таблица автомата, выполняющего LL(1)-разбор

Символ $ используется для обозначений правого конца строки и дна стека. Таким образом, успешное окончание распознавания входной строки при завершении просмотра строки и пустом стеке должно произойти по команде «допуск», которая размещена в таблице по координатам ($, $). Целыми числами в таблице обозначены команды замены символа в вершине стека правой частью правила грамматики. Число является номером используемого командой правила. При исполнении таких команд правая часть правила помещается в стек таким образом, что ее первый символ оказывается в вершине стека, т.е. становится определяющим для нового внутреннего состояния автомата.

Поскольку, как уже было сказано, начальное состояние автомата определяется аксиомой грамматики, начальное содержание стека составляют маркер его дна и нетерминальный символ, являющийся аксиомой.

Процесс распознавания автоматом типа LL(1) строки i*i проиллюстрирован таблицей:

Содержание стека	Входная строка	Команда управляющей таблицы
< S > $	i * i $ ↑
< E > $	i * i $ ↑
< T > < X > $	i * i $ ↑
< F > < Y > < X > $	i * i $ ↑
i < Y > < X > $	i * i $ ↑	выброс
< Y > < X > $	i * i $ ↑
* < T > < X > $	i * i $ ↑	выброс
< T > < X > $	i * i $ ↑
< F > < Y > < X > $	i * i $ ↑
i < Y > < X > $	i * i $ ↑	выброс
< Y > < X > $	i * i $ ↑
< X > $	i * i $ ↑
$	i * i $ ↑	допуск

Процедуру решения задачи разбора можно рассматривать как построение дерева разбора для распознаваемой строки. Корнем такого дерева является аксиома, внутренними вершинами – нетерминальные символы, листьями – терминальные символы. Каждая внутренняя вершина дерева со своими непосредственными потомками соответствует применению в разборе одного из правил грамматики: нетерминал внутренней вершины – это левая часть, а ее непосредственные потомки – это правая часть правила грамматики.

В процессе LL(1)-разбора, можно сказать, выполняется построение дерева разбора для распознаваемой строки в направлении сверху вниз, от корня-аксиомы к листьям-символам входной строки. Поэтому LL(1)-разбор относится к классу нисходящих алгоритмов решения задачи разбора. В явном виде структура, хранящая дерево разбора целиком, алгоритмом не создается, но выполнение команды подстановки в стек правой части правила вместо левой как будто прорисовывает фрагмент дерева, состоящий из некоей внутренней вершины и ее непосредственных потомков.

В целом же, как выглядит дерево, соответствующее выполненному LL(1)-разбору, изображено на рис. 10.

< S >

|

< E >

/ \

< T > < X >

/ \ \

< F > < Y > Λ

| / \

i * < T >

/ \

< F > < Y >

| |

i Λ

Рис. 10. Дерево разбора строки i*i

Построение LL(1)-таблицы возможно только для грамматики, обладающей свойством LL(1). Необходимое условие наличия такого свойства у грамматики заключается в том, чтобы терминальные префиксы строк, выводимых из альтернативных правых частей правил для одного и того же нетерминала, были различными. Поскольку координаты ячейки таблицы, в которую помещается команда типа «номер правила», - это нетерминал из левой части правила (координата строки) и терминальный префикс строки, выводимой из правой части правила (координата столбца), наличие у грамматики свойства LL(1) обеспечивает размещение в ячейке таблицы единственной команды такого типа. Это значит, что решение задачи разбора с использованием LL(1)-таблицы не требует переборов и возвратов, т.е. является детерминированным.

В рассматриваемом примере LL(1)-грамматики для каждого из нетерминалов, за исключением < X > и < Y >, имеется только по одному правилу. Так, нетерминал < S > определяется только правилом с номером 1. Правая часть этого правила содержит один символ - < E >. Из этого символа различными подстановками можно вывести бесконечное множество строк терминальных и нетерминальных символов. Но все те из этих строк, у которых первым символом является терминальный, в качестве этого терминального символа имеют символ i. Иными словами, терминальным префиксом всех строк, выводимых из правой части правила номер 1, является символ i. Поэтому номер 1 размещается в ячейке таблицы с координатами (< S >, i). Несколько более сложным является вопрос о размещении в таблице правил с номерами 7 и 8. Правые части этих правил – пустые строки, у которых, конечно, не может быть никаких терминальных префиксов. Столбцы управляющей таблицы, в которые помещаются Λ -правила (правила с пустой правой частью), определяются из следующих соображений. Если нетерминал, находящийся в вершине стека, подлежит замене на пустую строку, то во входной строке в этой ситуации должен наблюдаться символ, который может следовать после этого нетерминала в какой-либо сентенциальной форме. Такой терминальный символ называется символом-следователем для соответствующего нетерминала и номер Λ -правила должен быть помещен в ячейку управляющей таблицы с координатами: нетерминальный символ левой части правила и символ-следователь для этого нетерминального символа. Символом-следователем для нетерминала < X > является $. Обнаружить это позволяют правила грамматики с номерами 2 и 1. Поскольку < X > занимает последнюю позицию в правой части правила для < E >, а < E >, в свою очередь, – последнюю позицию в правой части правила для < S >, у нетерминалов < X >, < E > и < S > – общие символы-следователи. Для аксиомы грамматики, помимо возможных прочих, всегда символом-следователем является $. Это даже явно следует из начального содержания стека. Поскольку в правых частях правил рассматриваемой грамматики аксиома < S > не упоминается, $ – это единственный символ-следователь для < S >, а значит – и для < X >. Поэтому номер правила 7 следует поместить в ячейку таблицы с координатами (< X >, $). Для правила с номером 8 можно провести аналогичные рассуждения в поисках символов-следователей для < Y >. Нетерминал < Y > занимает последнюю позицию в правой части правила для нетерминала < T >. Следовательно, у < Y > и < T > – общие символы-следователи. В правой части правила с номером 2 после < T > следует символ < X >, который не может считаться символом-следователем, поскольку является нетерминалом, необходимо рассмотреть всевозможные подстановки вместо < X >. Подстановка, в соответствии с правилом 7, пустой строки делает < T > последним в определении < E >, и значит, для < T > и < Y >, по указанной выше причине, символом-следователем является $. Подстановка же вместо < X > правой части правила с номером 3 обнаруживает в качестве символа-следователя для < T > и < Y > терминальный символ +. Поэтому номер правила 8 следует поместить в две ячейки таблицы: с координатами (< Y >, $) и с координатами (< Y >, +). Таким образом, для каждого из двух правил с < X > в левой части и для каждого из двух правил с < Y > в левой части нашлись отдельные ячейки управляющей таблицы, что позволяет сделать вывод о наличии свойства LL(1) у рассмотренной грамматики.

Обобщая формулировки процедуры анализа грамматики и алгоритма построения управляющей таблицы типа LL(1), можно сказать следующее. Необходимым и достаточным условием наличия у КС-грамматики свойства LL(1) является попарная непересекаемость множеств терминальных префиксов альтернативных правых частей правил для одного и того же нетерминала и непересекаемость этих же множеств со множеством символов-следователей этого же нетерминала, если для него имеется Λ -правило. При заполнении управляющей таблицы номер правила, имеющего вид U::=α, заносится в ячейки с координатами (U,x) для всех x, являющихся терминальными префиксами строк, выводимых из α, или являющихся символами-следователями для U, если α = Λ. Ячейки, имеющие одинаковые терминальные координаты строки и столбца, заполняются командой «выброс», в ячейку с координатами ($, $) заносится команда «допуск». Остальные ячейки управляющей таблицы заполняются командой «ошибка».

Если грамматика не обладает свойством LL(1), в некоторых случаях ее можно преобразовать к другой грамматике, обладающей этим свойством и описывающей тот же язык.

Одно из преобразований позволяет избавиться от так называемых леворекурсивных правил, т.е. таких у которых нетерминал из левой части правила в правой части правила занимает крайнюю слева позицию. Если в общем виде леворекурсивная конструкция выглядит так: U::= U α, а нерекурсивный вариант определения того же нетерминала – U::= x, то очевидно, что эти два правила претендуют на размещение в одной и той же ячейке управляющей таблицы, ячейке с координатами (U, x) (для упрощения записи предположим, что x – терминальный символ). Эти два правила можно заменить следующими тремя: U::= x Z, Z::= α Z, Z::= Λ. Левая рекурсия, таким образом, устранена, а из нетерминала U, по-прежнему, выводится строка, начинающаяся с символа x, после которого может следовать произвольное количество символов (или строк) α.

Другое преобразование заключается в устранении правил с одинаковыми префиксами в правой части и одинаковыми левыми частями. Если два таких правила имеют вид: U::= xWα и U::= xWβ, то их, очевидно, можно заменить следующими тремя: U::= xWZ, Z::= α, Z::= β.

Как уже было сказано, LL(1)-языки составляют подмножество КС-языков. Поэтому надо иметь в виду, что подобные преобразования не всегда позволяют получить LL(1)-описание для заданного языка, иногда это может оказаться принципиально невозможным.