LL-разбор КС-грамматики автоматом с магазинной памятью

Пусть задана КС-грамматика. Построим по ней МПА, выполняющий грамматический LL-разбор. Множество входных символов Σ в МПА будет совпадать с множеством терминальных символов грамматики. Множество состояний Q будет состоять из единственного состояния q₀, оно же будет начальным и заключительным. Множество магазинных символов Γ будет содержать все терминальные и нетерминальные символы грамматики: Γ = Σ U N. Начальный магазинный символ Z₀ будет совпадать с начальным символом грамматики S. Правила перехода δ для МПА будем строить следующим образом. Для каждого порождающего правила вида A → γ будет правило перехода:

(λ, A, q₀) → (λ, γ^–1, q₀), (*)

где γ^–1 – правая часть правила γ в обратном порядке, а для каждого терминального символа a правило перехода:

(a, a, q₀) → (λ, λ, q₀). (**)

Этот МПА будет повторять левое каноническое порождение. Действительно, до начала работы в магазине находится единственный символ S – начальный символ грамматики, который при построении дерева помещается в корень. Далее S в магазине заменяется символами правой части правила порождения (по правилу вида (*)), при занесении в магазин их можно одновременно помещать в дерево порождения. Как только на вершине магазина появится терминальный символ, и если он совпадет с очередным входным символом, то он удаляется из магазина (по правилу вида (**)), при этом далее будет читаться следующий входной символ. Таким образом, МПА полностью повторяет левое каноническое порождение, и если получающиеся при этом терминальные символы совпадают с символами входной цепочки, то в конце работы магазин будет пуст, и вся цепочка прочитана. Это значит, что входная цепочка распознана. Если же входная цепочка не принадлежит языку, т.е. для нее не существует левого канонического порождения, то на каком-либо шаге работы верхний в магазине терминальный символ не совпадет с очередным входным символом, и МПА попадет в тупик.

Обычно в КС-грамматике имеются группы различных порождающих правил с одним и тем же нетерминалом в левой части. Тогда МПА будет недетерминированным, в этом случае он должен параллельно проверять все варианты левого канонического порождения. Если при этом некоторые из вариантов будут попадать в тупики, то работа по ним будет прекращаться. Если при этом хотя бы при одном варианте левого канонического порождения разбор дойдет до конца входной цепочки и стек будет пуст, то это значит, что найден такой вариант разбора, который соответствует этой входной цепочке.

Таким образом, входная цепочка будет распознана тогда и только тогда, когда для нее существует левое каноническое порождение. Заметим, что на КС-грамматику не накладывалось никаких дополнительных ограничений, в частности, она может быть даже неоднозначной. В этом случае НМПА отследит все варианты левого канонического порождения входной цепочки.

Пример 5. Пусть задана грамматика простых арифметических выражений (S – начальный нетерминал):

S → S + T | T

T → T * F | F

F → (S) | a

Пусть цепочка на входе: a + a. В табл. 6 представлен тот вариант шагов LL-разбора, который приводит к успешному распознаванию.

Табл. 6

В табл. 6 не приведены другие варианты шагов разбора, которые приводят в тупик или зацикливают. Для этого примера неудачных вариантов оказывается бесконечно много. Так, при применении переходов с многократным повторением одного и того же порождающего правила S → S + T содержимое магазина будет неограниченно увеличиваться: S, S + T, S + T + T, S + T + T + T, … Применение переходов с порождающими правилами S → T, T → F, F → a приведет к тому, что содержимое магазина будет изменяться так: S, T, F, a, λ. После этого во входной цепочке останутся непросмотренными символы: + a, т.е. возникнет тупик.

Конец примера.

Дата добавления: 2015-07-26; просмотров: 134; Нарушение авторских прав

Мы поможем в написании ваших работ!