Синтаксический анализ

4. Лекция: Синтаксический анализ
В данной лекции рассматривается понятие синтаксического анализа. Приводятся определения понятий упорядоченного графа, дерева вывода, автомата с магазинной памятью и его конфигурации. Приведены примеры задач, алгоритмов и доказательства теорем синтаксического анализа.

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

Пусть G = (N, T, P, S) - КС-грамматика. Введем несколько важных понятий и определений.

Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S^* u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определим правосторонний вывод. Обозначим шаги левого (правого) вывода _l (_r).

Упорядоченным графом называется пара (V,E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v₁), (v, v₂), ... , (v, v_n)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v₁, второй - дуга, входящая в вершинуv₂, и т.д.

Упорядоченным помеченным деревом называется упорядоченный граф (V,E), основой которого является дерево и для которого определена функция f : V F (функция разметки) для некоторого множества F.

Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:

(1) корень дерева D помечен S;

(2) каждый лист помечен либо , либо e;

Рекомендуемые материалы

(3) каждая внутренняя вершина помечена нетерминалом ;

(4) если X - нетерминал, которым помечена внутренняя вершина и X₁, ... , X_n - метки ее прямых потомков в указанном порядке, то X X₁ ... X_k - правило из множества P;

(5) Цепочка, составленная из выписанных слева направо меток листьев, равна w.

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

Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.

Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что для некоторой цепочки R существует вывод A ⁺ A.

Автомат с магазинной памятью (МП-автомат) - это семерка M = (Q, T, Γ, D, q₀, Z₀, F), где

(1) Q - конечное множество состояний, представляющих всевозможные состояния управляющего устройства;

(2) T - конечный входной алфавит;

(3) Γ - конечный алфавит магазинных символов;

(4) D - отображение множества Q x (T {e}) x Γ в множество конечных подмножеств Q x Γ^*, называемое функцией переходов;

(5) - начальное состояние управляющего устройства;

(6) - символ, находящийся в магазине в начальный момент (начальный символ магазина);

(7) - множество заключительных состояний.

Конфигурация МП-автомата - это тройка (q, w, u), где

(1) - текущее состояние управляющего устройства;

(2) - непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = e, то считается, что вся входная лента прочитана;

(3) - содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считается пустым.

Такт работы МП-автомата M будем представлять в виде бинарного отношения , определенного на конфигурациях.

Будем писать

если множество D(q, a, Z) содержит (p, v), где и (верхушка магазина слева).

Начальной конфигурацией МП-автомата M называется конфигурация вида (q₀, w, Z₀), где , то есть управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине имеется только начальный символ Z₀.

>Заключительной конфигурацией называется конфигурация вида (q, e, u), где , то есть управляющее устройство находится в одном из заключительных состояний, а входная цепочка целиком прочитана.

Введем транзитивное и рефлексивно-транзитивное замыкание отношения , а также его степень k > 0 (обозначаемые , и соответственно).

Говорят, что цепочка w допускается МП-автоматом M, если для некоторых и .

Множество всех цепочек, допускаемых автоматом M называется языком, допускаемым (распознаваемым, определяемым) автоматом M (обозначается L(M)).

Пример 4.1. Рассмотрим МП-автомат

M = ({q₀, q₁, q₂}, {a, b}, {Z, a, b}, D, q₀, Z, {q₂}),

у которого функция переходов D содержит элементы:

D(q0, a, Z) = {(q0, aZ)},

D(q0, b, Z) = {(q0, bZ)},

D(q0, a, a) = {(q0, aa), {q1, e)},

D(q0, a, b) = {(q0, ab)},

D(q0, b, a) = {(q0, ba)},

D(q0, b, b) = {(q0, bb), (q1, e)},

D(q1, a, a) = {(q1, e)},

D(q1, b, b) = {(q1, e)},

D(q1, e, Z) = {(q2, e)}.

Нетрудно показать, что , где w^R обозначает обращение ("переворачивание") цепочки w.

Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если для некоторого . В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедлива

Теорема 4.1. Язык допускается МП-автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом) опустошением магазина.

Доказательство. Пусть L = L(M) для некоторого МП- автомата M = (Q, T, Γ, D, q₀, Z₀, F). Построим новый МП- автомат M', допускающий тот же язык опустошением магазина.

Пусть , где функция переходов D' определена следующим образом:

1. Если , то для всех и (моделирование М),
2. (начало работы),
3. Для всех и множество D'(q, e, Z) содержит (q_e, e) (переход в состояние сокращения магазина без продвижения),
4. D'(q_e, e, Z) = {(q_e, e)} для всех , (сокращение магазина).

Автомат сначала переходит в конфигурацию соответственно определению D' в п.2, затем в ,

соответственно п.1, затем в соответственно п.3, затем в (q_e, e, e) соответственно п.4. Нетрудно показать по индукции, что (где ) выполняется для автомата M тогда и только тогда, когда выполняется для автомата M'. Поэтому L(M) = L', где L' - язык, допускаемый автоматом M' опустошением магазина.

Обратно, пусть M = (Q, T, Γ, D, q₀, Z₀, ) - МП - автомат, допускающий опустошением магазина язык L. Построим автомат M', допускающий тот же язык по заключительному состоянию.

Пусть , где D' определяется следующим образом:

1. - переход в "режим M",
2. Для каждого определим - работа в "режиме M" ,
3. Для всех - переход в заключительное состояние.

Нетрудно показать по индукции, что L = L(M'). Одним из важнейших результатов теории контекстно-свободных языков является доказательство эквивалентности МП-автоматов и КС-грамматик.

Теорема 4.2. Язык является контекстно-свободным тогда и только тогда, когда он допускается МП-авто- матом.

Доказательство. Пусть G = (N, T, P, S) - КС-граммати- ка. Построим МП-автомат, допускающий язык L(G) опустошением магазина.

Пусть M = ({q}, T, N T, D, q, S, ), где D определяется следующим образом:

1. Если , то ,
2. D(q, a, a) = {(q, e)} для всех .

Фактически, этот МП-автомат в точности моделирует все возможные выводы в грамматике G. Нетрудно показать по индукции, что для любой цепочки вывод S ⁺w в грамматике G существует тогда и только тогда, когда существует последовательность тактов автомата M.

Наоборот, пусть дан M = (Q, T, Γ , D, q₀, Z₀, ) - МП- автомат, допускающий опустошением магазина язык L.

Построим грамматику G, порождающую язык L.

Пусть , где P состоит из правил следующего вида:

1. для всех .
2. Если ,
3. Если , то

Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левосторонний вывод w в грамматике G.

Индукцией по числу шагов вывода в G или числу тактов M нетрудно показать, что тогда и только тогда, когда [qAp] ⁺ w.

Тогда, если , то S [q₀Z₀q] ⁺ w для некоторого . Следовательно, и поэтому . Аналогично, если , то . Значит, S [q₀Z₀q] ⁺ w, и поэтому .

МП-автомат M = (Q, T, Γ, D, q₀, Z₀, F) называется детерминированным (ДМП-автоматом), если выполнены два следующих условия:

(1) Множество D(q, a, Z) содержит не более одного элемента для любых ;

(2) Если D(q, e, Z) , то D(q, a, Z) = для всех

Допускаемый ДМП-автоматом язык называется детерминированным КС-языком.

Так как функция переходов ДМП-автомата содержит не более одного элемента для любой тройки аргументов, мы будем пользоваться записью D(q, a, Z) = (p, u) для обозначения D(q, a, Z) = {(p, u)}.

Пример 4.2. Рассмотрим ДМП-автомат

M = ({q₀, q₁, q₂}, {a, b, c}, {Z, a, b}, D, q₀, Z, {q₂}),

функция переходов которого определяется следующим образом:

Нетрудно показать, что этот детерминированный МП-автомат допускает язык .

К сожалению, ДМП-автоматы имеют меньшую распознавательную способность, чем МП-автоматы. Доказано, в частности, что существуют КС-языки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).

Рассмотрим еще один важный вид МП-автомата.

Расширенным автоматом с магазинной памятью назовем семерку M = (Q, T, Γ , D, q₀, Z₀, F), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечного подмножества множества Q x(T {e}) x Γ^* во множество конечных подмножеств множества Q x Γ^*. Все остальные определения (конфигурации, такта, допустимости) для расширенного МП-автомата остаются такими же, как для обычного.

Теорема 4.3. Пусть M = (Q, T, Γ, D, q₀, Z₀, F) - расширенный МП-автомат. Тогда существует МП- автомат M', такой, что L(M') = L(M).

Расширенный МП-автомат M = (Q, T, Γ, D, q₀, Z₀, F) называется детерминированным, если выполнены следующие условия:

(1) Множество D(q, a, u) содержит не более одного элемента для любых ,

(2) Если D(q, a, u) , D(q, a, v) и u v, то не существует цепочки x такой, что u = vx или v = ux,

(3) Если D(q, a, u) , D(q, e, v) , то не существует цепочки x такой, что u = vx или v = ux.

Теорема 4.4. Пусть M = (Q, T, Γ, D, q₀, Z₀, F) - расширенный ДМП-автомат. Тогда существует ДМП- автомат M', такой, что L(M') = L(M).

ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе, соответственно, LL- и LR-анализаторов.

Определение. Говорят, что КС-грамматика находится в нормальной форме Хомского, если каждое правило имеет вид:

(1) либо A BC, A, B, C - нетерминалы,

(2) либо A a, a - терминал,

(3) либо S e и в этом случае S - не встречается в правых частях правил.

Утверждение. Любую КС-грамматику можно преобразовать в эквивалентную ей в нормальной форме Хомского.

Утверждение. Если КС-грамматика находится в нормальной форме Хомского, тогда для любой цепочки , если и m - высота дерева вывода с кроной , || 2^m-1.

Теорема 4.5. (Лемма о разрастании для контекстно- свободных языков). Для любого КС-языка L существуют такие целые l и k, что любая цепочка , представима в виде R = uvwxy, где

(1) |vwx| k

(2) vx e

(3) для любого i 0.

Доказательство. Пусть L = L(G), где G = (N, Σ, P, S) - контекстно- свободная грамматика в нормальной форме Хомского. Обозначим через n число нетерминалов, т.е. n = |N|, и рассмотрим l = 2ⁿ и k = 2ⁿ⁺¹.

Для доказательства того, что l и k удовлетворяют условию теоремы, рассмотрим произвольную цепочку , для которой || > l = 2n. В силу Утверждения получаем, что высота дерева с кроной больше n + 1 и есть путь по дереву (обозначим его через P), который проходит более чем через n + 1 вершин. Отсюда по определению дерева вывода имеем, что P содержит более n вершин, помеченных нетерминалами. Таким образом, существует нетерминал, который метит не менее двух вершин пути P. Среди всех таких нетерминалов пусть A - такой, что его вхождение, ближайшее к листу, не содержит других нетерминалов, обладающих этим свойством (если бы это было не так, то выбрали бы этот другой). Пусть q - вхождение A, ближайшее к листу, p - расположенное выше. Представим крону в виде uvwxy, где w - крона поддерева D₁ с корнем q и vwx - крона поддерева D₂ с корнем p. Тогда высота поддерева D₂ не более (n - 1) + 2 + 1 = n + 2, так что |vwz| 2ⁿ⁺¹.

Также очевидно, что vx e, поскольку в силу определения нормальной формы Хомского p имеет двух сыновей, помеченных нетерминалами, из которых не выводится пустая цепочка.

Кроме того, S ^* u Ay ^* uvAxy ^* uvwxy, а также A ^* vAx ^* vwx. Отсюда получаем A ^* vⁱwxⁱ для всех i 0 и S ^* uvⁱwxⁱy для всех i 0.

Пример. Покажем, что язык L = {aⁿbⁿcⁿ|n1} не является контекстно-свободным языком.

Если бы он был КС-языком, то мы взяли бы константу k, которая определяется в лемме о разрастании. Пусть z = a^kb^kc^k. Тогда z = uvwxy. Так как |vwx| k, то в цепочке vwx не могут быть вхождения каждого из символов a, b и c. Таким образом, цепочка uwy, которая по лемме о разрастании принадлежит L, содержит либо k символов a, либо k символов c. Но она не может иметь k вхождений каждого из символов a, b и c, потому, что |uwy| < 3k. Значит, вхождений какого-то из этих символов в uwy больше, чем другого и, следовательно, uwy L. Полученное противоречие позволяет заключить, что L - не КС-язык.

Преобразования КС-грамматик

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

Назовем символ недостижимым в КС- грамматике G = (N, T, P, S), если X не появляется ни в одной выводимой цепочке этой грамматики. Иными словами, символ X является недостижимым, если в G не существует вывода S ^* Xβ ни для каких .

Назовем символ несводимым (бесплодным) в той же грамматике, если в ней не существует вывода вида X ^* xwy, где w, x, y принадлежат T^*.

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

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

Алгоритм 4.1. Устранение недостижимых символов.

Вход. КС-грамматика G = (N, T, P, S).

Выход. КС-грамматика G' = (N', T', P', S) без недостижимых символов, такая, что L(G') = L(G).

Метод. Выполнить шаги 1-4:

(1) Положить V₀ = {S} и i = 1,

(2) Положить V_i = {X | в P есть A Xβ и ,

(3) Если V_i V_i-1, положить i = i + 1 и перейти к шагу 2, в противном случае перейти к шагу 4,

(4) Положить N' = V_i N, T' = V_i T. Включить в P' все правила из P, содержащие только символы из V_i.

Алгоритм 4.2. Устранение несводимых символов.

Вход. КС-грамматика G = (N, T, P, S).

Выход. КС-грамматика G' = (N', T', P', S) без несводимых символов, такая, что L(G') = L(G).

Метод. Выполнить шаги 1-4:

(1) Положить N' = T и i = 1,

(2) Положить ,

(3) Если N_i N_i-1, положить i = i + 1 и перейти к шагу 2, в противном случае положить N_e = N_i и перейти к шагу 4,

(4) Положить G₁ = ((N N_e) {S}, T, P₁, S), где P₁ состоит из правил множества P, содержащих только символы из N_e T,

Чтобы устранить все бесполезные символы, необходимо применить к исходной грамматике сначала Алгоритм 4.2, а затем Алгоритм 4.1.

Пример. Все символы следующей грамматики

S AS | b

A AB

B a

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

КС-грамматика без бесполезных символов называется приведенной. Легко видеть, что для любой КС-грамматики существует эквивалентная приведенная. В дальнейшем будем предполагать, что все рассматривамые грамматики - приведенные.

Алгоритм Кока-Янгера-Касами

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

Алгоритм Кока-Янгера-Касами

Вход. КС-грамматика G = (N, T, P, S) в нормальной форме Хомского и входная цепочка .

Выход. Таблица разбора Tab для w такая, что тогда и только тогда, когда A ⁺ a_ia_i+1 ... a_i+j-1.

Метод.

(1) Положить для каждого i. Так что, если , то A ⁺ a_i.

(2) Пусть t_ij вычислено для 1in и 1 j' < j. Положим t_ij = {A| для некоторого 1 k < j правило .

Так как 1 k < j, то k < j и j - k < j. Так что t_ik и t_i+k,j-k вычисляются раньше, чем t_ij . Если , то A BC ⁺ a_i a_i+k-1 C ⁺ a_I ... a_i+k-1a_i+k ... a_i+j-1.

(3) Повторять шаг 2 до тех пор, пока не станут известны t_ij для всех 1 i n и 1 j n-i+1.

Алгоритм нахождения левого разбора по таблице разбора Tab.

Вход. КС-грамматика G = (N, T, P, S) в нормальной форме Хомского с правилами, занумерованными от 1 до p, входная цепочка и таблица разбора Tab.

Выход. Левый разбор цепочки w или сигнал ошибка.

Метод. Процедура gen(i, j, A):

(1) Если j = 1 и A a_i = p_m, выдать m.

(2) Пусть j > 1 и k - наименьшее из чисел от 1 до j-1, для которых существует и правило pm = A BC. Выдать m и выполнить gen(i, k, B), затем gen(i + k, j - k, C).

Выполнить gen(1, n, S), если , иначе ошибка.

Разбор сверху-вниз (предсказывающий разбор)

Алгоритм разбора сверху-вниз

Пусть дана КС-грамматика G = (N; T; P; S). Рассмотрим разбор сверху-вниз (предсказывающий разбор) для грамматики G.

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

Фрагменты недостроенного дерева соответствуют сентенциальным формам. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входной цепочки предсказывающий анализатор должен определить правило S X₁X₂ ... ; которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X₁, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу, не будет применено правило Y a ... : Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.

На рис. 4.2 условно показана структура предсказывающего анализатора, который определяет

Рис. 4.1.

очередное правило с помощью таблицы. Такую таблицу можно построить и непосредственно по грамматике. Таблично-управляемый предсказывающий анализатор имеет входную ленту, управляющее устройство (программу), таблицу анализа, магазин (стек) и выходную ленту. Входная лента содержит анализируемую строку, заканчивающуюся символом $ - маркером конца строки. Выходная лента содержит последовательность примененных правил вывода.

Рис. 4.2.

Таблица анализа - это двумерный массив M[A; a], где A - нетерминал, и a - терминал или символ $. Значением M[A; a] может быть некоторое правило грамматики или элемент "ошибка".

Магазин может содержать последовательность символов грамматики с $ на дне. В начальный момент магазин содержит только начальный символ грамматики на верхушке и $ на дне.

Анализатор работает следующим образом. Вначале анализатор находится в конфигурации, в которой магазин содержит S$, на входной ленте w$ (w - анализируемая цепочка), выходная лента пуста. На каждом такте анализатор рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти два символа определяют действия анализатора. Имеются следующие возможности.

1. Если X=a=$, анализатор останавливается, сообщает об успешном окончании разбора и выдает содержимое выходной ленты.
2. Если X= a $, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.
3. Если X - терминал, и X a, то анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.
4. Если X - нетерминал, анализатор заглядывает в таблицу M[X; a]. Возможны два случая:
1. Значением M[X; a] является правило для X. В этом случае анализатор заменяет X на верхушке магазина на правую часть данного правила, а само правило помещает на выходную ленту. Указатель входа не передвигается.
2. Значением M[X; a] является "ошибка". В этом случае анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку. Работа анализатора может быть задана следующей программой:

Поместить '$', затем S в магазин;

do

   {X=верхний символ магазина;

if (X - терминал)

   if (X==InSym)

      {удалить X из магазина;

      InSym=очередной символ;

      }

   else {error(); break;}

else if (X - нетерминал)

   if (M[X,InSym]=="X->Y1Y2...Yk")

    {удалить X из магазина;

     поместить Yk,Yk-1,...Y1 в магазин

      (Y1 на верхушку);

     вывести правило X->Y1Y2...Yk;

    }

   else {error(); break;} /*вход таблицы M пуст*/

 }

while (X!='$'); /*магазин пуст*/

if (InSym != '$') error(); /*Не вся строка прочитана*/

Пример 4.3. Рассмотрим грамматику арифметических выражений G=({E; E', T, T', F}, {id, +, *, (, )}, P, E) с правилами:

В таблица 4.3 приведена предсказывающего анализатора для этой грамматики. Пустые клетки таблицы соответствуют элементу "ошибка".

При разборе входной цепочки id + id * id$ анализатор совершает последовательность шагов, изображенную в таблица 4.4. Заметим, что анализатор осуществляет в точности левый вывод. Если за уже просмотренными входными символами поместить символы грамматики в магазине, то можно получить в точности левые сентенциальные формы вывода. Дерево разбора для этой цепочки приведено на рис. рис. 4.3.

Функции FIRST и FOLLOW

При построении таблицы предсказывающего анализатора нам потребуются две функции - FIRST и FOLLOW.

Пусть G = (N, T, P, S) - КС-грамматика. Для - произвольной цепочки, состоящей из символов грамматики, определим FIRST() как множество терминалов, с которых

Рис. 4.3.

начинаются строки, выводимые из . Если ^* e, то e также принадлежит FIRST().

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме грамматики, то есть множество терминалов a таких, что существует вывод вида S ^* Aaβ для некоторых . Заметим, что между A и a в процессе вывода могут находиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символом некоторой сентенциальной формы, то $ также принадлежит FOLLOW(A).

Рассмотрим алгоритмы вычисления функции FIRST.

Алгоритм 4.3. Вычисление FIRST для символов КС- грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X) для каждого символа .

Метод. Выполнить шаги 1-3:

(1) Если X - терминал, то положить FIRST(X) = {X}; если X - нетерминал, положить FIRST(X) = .

(2) Если в P имеется правило X e, то добавить e к FIRST(X).

(3) Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы, выполнять:

do { continue = false;

  Для каждого нетерминала X

   Для каждого правила X  Y₁Y₂...Yk

   {i=1; nonstop = true;

   while (i  k && nonstop)

    {добавить FIRST(Y_i) n {e} к FIRST(X);

    if (Были добавлены новые элементы)

      continue = true;

    if (e  FIRST (Y_i)) nonstop = false;

    else i+ = 1;

    }

    if (nonstop) {добавить e к FIRST(X);

      continue = true;

  } } }

while (continue);

Алгоритм 4.4. Вычисление FIRST для цепочки.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество .

Метод. Выполнить шаги 1-3:

(1) При помощи алгоритма 4.3. вычислить FIRST(X) для каждого .

(2) Положить FIRST(X₁X₂ ... X_n) = .

(3)

 {i = 1; nonstop = true;

   while (i  && nonstop)

    {добавить FIRST(X_i) n {e} к FIRST(u);

      if (e  FIRST(X_i)nonstop = false;

        else i+ = 1;

    }

if (nonstop) {добавить e к FIRST(u);

    } }

Рассмотрим алгоритм вычисления функции FOLLOW.

Алгоритм 4.5. Вычисление FOLLOW для нетерминалов грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FOLLOW(X) для каждого символа .

Метод. Выполнить шаги 1-4:

(1) Положить FOLLOW(X) = для каждого символа .

(2) Добавить $ к FOLLOW(S).

(3) Если в P eсть правило вывода A Bβ, где , то все элементы из FIRST(β), за исключением e, добавить к FOLLOW(B).

(4) Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X), выполнять:

если в P есть правило A B или A Bβ, , где FIRST(β) содержит e (β*e), то все элементы из FOLLOW(A) добавить к FOLLOW(B).

Пример 4.4. Рассмотрим грамматику из примера 4.3. Для нее

FIRST(E) = FIRST(T) = FIRST(F) = {(, id}

FIRST(E') = {+, e}

FIRST(T') = {*, e}

FOLLOW(E) = FOLLOW(E') = { ), $}

FOLLOW(T) = FOLLOW(T') = {+, ), $}

FOLLOW(F) = {+, *, ), $}

Например, id и левая скобка добавляются к FIRST(F) на шаге 3 при i = 1, поскольку FIRST(id) = {id} и FIRST("(") = {"("} в соответствии с шагом 1. На шаге 3 при i = 1, в соответствии с правилом вывода T FT', к FIRST(T) добавляются также id и левая скобка. На шаге 2 в FIRST(E') включается e.

Также при вычислении множеств FOLLOW на шаге 2 в FOLLOW(E) включается $. На шаге 3, на основании правила F (E), к FOLLOW(E) добавляется также правая скобка. На шаге 4, примененном к правилу E TE', в FOLLOW(E') включаются $ и правая скобка. Поскольку , они также попадают и во множество FOLLOW(T). В соответствии с правилом вывода E TE', на шаге 3 в FOLLOW(T) включаются и все элементы из FIRST(E'), отличные от e.

Определим теперь функцию FIRSTk(R), где k - натуральное число и .

либо |w| < k и , либо для некоторого .

Если , то FIRST_k() = {w}, где w - это первые k символов цепочки при || k и w = при || < k.

Приведем алгоритм вычисления функции FIRST_k(β), где .

Определение. Пусть Σ - некоторый алфавит. Если L₁ и L₂ - подмножества Σ^*, то положим

Лемма 4.1. Для любой КС-грамматики G = (N, Σ, P, S) и любых

Доказательство оставляем читателю в качестве упражнения.

Aлгоритм 4.6. Вычисление функции FIRST_k().

Вход. КС-грамматика G = (N, Σ, P, S) и цепочка .

Выход. FIRST_k(β).

Метод. Так как по последней лемме

то достаточно показать, как найти FIRST_k(X) для .

Если , то очевидно, что FIRST_k(X) = {X}.

Определим множества F_i(X) для каждого и возрастающих значений i 0:

(1) F_i(a) = {a} для всех и i 0:

(2) и существует правило A x из P, для которого либо |x| = k, либо |x| < k и = e}.

(3) Допустим, что F₀, F₁..., F_i-1 уже определены для всех . Тогда

F_i(A) = F_i-1(A) {x|A Y₁...Y_n принадлежит P и

(4) Так как для всех A и i, то в конце концов мы дойдем до такого i, что F_i-1(A) = F_i(A) для всех . Тогда положим FIRST_k(A) = F_i(A) для этого значения i.

Конструирование таблицы предсказывающего анализатора

Для конструирования таблицы предсказывающего анализатора по грамматике G может быть использован алгоритм, основанный на следующей идее. Предположим, что A - правило вывода грамматики и . Тогда анализатор делает развертку A по , если входным символом является a. Трудность возникает, когда = e или . В этом случае нужно развернуть A в , если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и .

Алгоритм 4.7. Построение таблицы предсказывающего анализатора.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Таблица M[A; a] предсказывающего анализатора, .

Метод. Для каждого правила вывода A грамматики выполнить шаги 1 и 2. После этого выполнить шаг 3.

(1) Для каждого терминала a из FIRST(R) добавить AR к M[A; a].

(2) Если , добавить A R к M[A; b] для каждого терминала b из FOLLOW(A). Кроме того, если и , добавить A к M[A; $].

(3) Положить все неопределенные входы равными "ошибка".

Пример 4.5. Применим алгоритм 4.7 к грамматике из примера 4.3. Поскольку 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') = { ), $}.

Таблица анализа, построенная по алгоритму 4.7. для этой грамматики, приведена в таблица 4.3.

LL(1)-грамматики

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

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

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

Справедлив также следующий критерий LL(1)-граммати- ки. Грамматика G = (N, T, P, S) является LL(1)-грамматикой тогда и только тогда, когда для каждой пары правил A , A β из P

(то есть правил с одинаковой левой частью) выполняются следующие 2 условия:

(1)

(2) Если , то FIRST(β) FOLLOW(A)= .

Язык, для которого существует порождающая LL(1)- грамматика, называют LL(1)-языком. Доказано, что проблема определения, порождает ли грамматика LL-язык, является алгоритмически неразрешимой.

Пример 4.6. Неоднозначная грамматика не является LL(1). Примером может служить следующая грамматика

 

G = ({S, E}, {if, then, else, a, b}, P, S) с правилами:

   S  if E then S | if E then S else S | a

   E  b

Эта грамматика является неоднозначной, что иллюстрируется на рис. 4.4.

LL(k)-грамматики

Определение. КС-грамматика G = (N, Σ, P, S) называется LL(k)-грамматикой для некоторого фиксированного k, если из

(1)

(2) для которых

и

FIRST_k(x) = FIRST_k(y), вытекает, что β = γ.

Говоря менее формально, G будет LL(k)- грамматикой, если для данной цепочки и первых k символов (если они есть), выводящихся из A, существует не более одного правила, которое можно применить к A, чтобы получить вывод какой-нибудь терминальной цепочки,

Рис. 4.4.

начинающейся с ω и продолжающейся упомянутыми k терминалами.

Грамматика называется LL(k)-грамматикой, если она LL(k)-грамматика для некоторого k.

Пример 4.7. Рассмотрим грамматику G = ({S, A, B}, {0, 1, a, b}, P, S), где P состоит из правил

   S  A | B,

   A  aAb | 0,

   B  aBbb | 1.

Здесь L(G) = aⁿ0bⁿ | n 0 aⁿ1b²ⁿ | n 0. G не является LL(k)-грамматикой ни для какого k. Интуитивно, если мы начинаем с чтения достаточно длинной цепочки, состоящей из символов a, то не знаем, какое из правил S A и S B было применено первым, пока не встретим 0 или 1.

Обращаясь к точному определению LL(k)-грамматики, положим ω = = e; β = A; γ = B; x = a^k0b^k и y = a^k1b^2k. Тогда выводы

соответствуют выводам (1) и (2) определения. Первые k символов цепочек x и y совпадают. Однако заключение β = γ ложно. Так как k здесь выбрано произвольно, то G не является LL-грамматикой.

Следствия определения LL(k)- грамматики

Теорема 4.6. КС-грамматика G = (N, Σ, P, S) является LL(k)-грамматикой тогда и только тогда, когда для двух различных правил A β и A γ из Р пересечение FIRST_k(β) FIRST_k(γ) пусто при всех таких ωA, что .

Доказательство. Необходимость. Допустим, что ω, A, , β и γ удовлетворяют условиям теоремы, а FIRST_k(β) FIRST_k(γ) содержит x. Тогда по определению FIRST для некоторых y и z найдутся выводы

(Заметим, что здесь мы использовали тот факт, что N не содержит бесполезных нетерминалов, как это предполагается для всех рассматриваемых грамматик.) Если |x| < k; то y = z = e. Так как β γ, то G не LL(k)-грамматика.

Достаточность. Допустим, что G не LL(k)-грамматика.

Тогда найдутся такие два вывода

что цепочки x и y совпадают в первых k позициях, но β γ. Поэтому A β и A γ - различные правила из P и каждое из множеств FIRSTk(β) и FIRSTk(γ) содержит цепочку FIRST_k(x), совпадающую с цепочкой FIRST_k(y).

Пример 4.8. Грамматика G, состоящая из двух правил S aS | a, не будет LL(1)-грамматикой, так как

FIRST₁(aS) = FIRST₁(a) = a.

Интуитивно это можно объяснить так: видя при разборе цепочки, начинающейся символом a, только этот первый символ, мы не знаем, какое из правил S aS или S a надо применить к S. С другой стороны, G - это LL(2)-грамматика. В самом деле, в обозначениях только что представленной теоремы, если , то A = S и = e. Так как для S даны только два указанных правила, то β = aS и γ = a. Поскольку FIRST2(aS) = aa и FIRST2(a) = a, то по последней теореме G будет LL(2)-грамматикой.

Удаление левой рекурсии

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

Непосредственную левую рекурсию, то есть рекурсию вида AA, можно удалить следующим способом. Сначала группируем A-правила:

A A₁ |A₂| ... |A_m|β₁|β₂| ... |β_n;

где никакая из строк β_i не начинается с A. Затем заменяем этот набор правил на

где A' - новый нетерминал. Из нетерминала A можно вывести те же цепочки, что и раньше, но теперь нет левой рекурсии. С помощью этой процедуры удаляются все непосредственные левые рекурсии, но не удаляется левая рекурсия, включающая два или более шага. Приведенный ниже алгоритм 4.8 позволяет удалить все левые рекурсии из грамматики.

Алгоритм 4.8. Удаление левой рекурсии.

Вход. КС-грамматика G без e-правил (вида A e).

Выход. КС-грамматика G' без левой рекурсии, эквивалентная G.

Метод. Выполнить шаги 1 и 2.

(1) Упорядочить нетерминалы грамматики G в произвольном порядке.

(2) Выполнить следующую процедуру:

После (i-1)-й итерации внешнего цикла на шаге 2 для любого правила вида A_k A_s, где k < i, выполняется s > k. В результате на следующей итерации (по i) внутренний цикл (по j) последовательно увеличивает нижнюю границу по m в любом правиле A_i A_m, пока не будет m i. Затем, после удаления непосредственной левой рекурсии для A_i-правил, m становится больше i.

Алгоритм 4.8 применим, если грамматика не имеет e- правил (правил вида A e). Имеющиеся в грамматике e- правила могут быть удалены предварительно. Получающаяся грамматика без левой рекурсии может иметь e-правила.

Левая факторизация

Oсновная идея левой факторизации в том, что в том случае, когда неясно, какую из двух альтернатив надо использовать для развертки нетерминала A, нужно изменить A-правила так, чтобы отложить решение до тех пор, пока не будет достаточно информации для принятия правильного решения.

Если A β₁ | β₂ - два A-правила и входная цепочка начинается с непустой строки, выводимой из , мы не знаем, разворачивать ли по первому правилу или по второму. Можно отложить решение, развернув A A'. Тогда после анализа того, что выводимо из , можно развернуть по A' β₁ или по A' β₂. Левофакторизованные правила принимают вид

AA'

A'β₁|β₂

Алгоритм 4.9. Левая факторизация грамматики.

Вход. КС-грамматика G.

Выход. Левофакторизованная КС-грамматика G', эквивалентная G.

Метод. Для каждого нетерминала A найти самый длинный префикс , общий для двух или более его альтернатив. Если e, то есть существует нетривиальный общий префикс, заменить все A-правила

A β₁|β₂| ... |β_n|z,

где z обозначает все альтернативы, не начинающиеся с , на

A A'|z

A'β₁|β₂| ... |β_n

где A' - новый нетерминал. Применять это преобразование, пока никакие две альтернативы не будут иметь общего префикса.

Пример 4.9. Рассмотрим вновь грамматику условных операторов из примера 4.6:

  S  if E then S | if E then S else S | a

  E  b

После левой факторизации грамматика принимает вид

  S  if E then SS' | a

  S'  else S | e

  E  b

К сожалению, грамматика остается неоднозначной, а значит, и не LL(1)-грамматикой.

Рекурсивный спуск

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

В процедуре A для случая, когда имеется правило A u_i, такое, что (напомним, что не может быть больше одного правила, из которого выводится e), приведены два варианта - 1.1 и 1.2. В варианте 1.1 делается проверка, принадлежит ли следующий входной символ FOLLOW(A): Если нет - выдается ошибка. В варианте 1.2 этого не делается, так что анализ ошибки откладывается на процедуру, вызвавшую A.

Восстановление процесса анализа после синтаксических ошибок

В приведенных программах рекурсивного спуска была использована процедура реакции на синтаксические ошибки error(). В простейшем случае эта процедура выдает диагностику и завершает работу анализатора. Но можно попытаться некоторым разумным образом продолжить работу. Для разбора сверху вниз можно предложить следующий простой алгоритм.

Если в момент обнаружения ошибки на верхушке магазина оказался нетерминальный символ A и для него нет правила, соответствующего входному символу, то сканируем вход до тех пор, пока не встретим символ либо из FIRST(A), либо из FOLLOW(A). В первом случае разворачиваем A по соответствующему правилу, во втором - удаляем A из магазина.

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

Разбор снизу-вверх типа сдвиг- свертка

Основа

В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной цепочки, начиная с листьев (снизу) к корню (вверх). Этот процесс можно рассматривать как "свертку" цепочки w к начальному символу грамматики. На каждом шаге свертки подцепочка, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подцепочка, то в обратном порядке прослеживается правосторонний вывод (рис. 4.5) Здесь ко входной цепочке, так же как и при анализе LL(1)-грамматик, приписан концевой маркер $.

Рис. 4.5.

Основой цепочки называется подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода. Самая левая подцепочка, которая сопоставляется правой части некоторого правила вывода A γ, не обязательно является основой, поскольку свертка по правилу A γ может дать цепочку, которая не может быть сведена к аксиоме.

Формально, основа правой сентенциальной формы z - это правило вывода A γ и позиция в z, в которой может быть найдена цепочка γ такие, что в результате замены γ на A получается предыдущая сентенциальная форма в правостороннем выводе z. Так, если , то A γ в позиции, следующей за , это основа цепочки γβ. Подцепочка β справа от основы содержит только терминальные символы.

Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод γβ и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с исходной цепочки w. Если w - слово в рассматриваемой грамматике, то w = _n, где _n - n-я правая сентенциальная форма еще неизвестного правого вывода .

Чтобы восстановить этот вывод в обратном порядке, выделяем основу γ_n в _n и заменяем γ_n на левую часть некоторого правила вывода A_n γ_n, получая (n - 1)-ю правую сентенциальную форму _n-1. Затем повторяем этот процесс, то есть выделяем основу γ_n-1 в _n-1 и сворачиваем эту основу, получая правую сентенциальную форму _n-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый вывод входной строки.

Таким образом, главная задача анализатора типа сдвиг- свертка - это выделение и отсечение основы.

LR(1)-анализаторы

В названии LR(1) символ L указывает на то, что входная цепочка читается слева-направо, R - на то, что строится правый вывод, наконец, 1 указывает на то, что анализатор видит один символ непрочитанной части входной цепочки.

LR(1)-анализ привлекателен по нескольким причинам:

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

Схематически структура LR(1)-анализатора изображена на рис. 4.4. Анализатор состоит из входной ленты, выходной ленты, магазина, управляющей программы и таблицы анализа (LR(1)-таблицы), которая имеет две части - функцию действий (Action) и функцию переходов (Goto). Управляющая программа одна и та же для всех LR(1)-анализаторов, разные анализаторы отличаются только таблицами анализа.

Анализатор читает символы на входной ленте по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S₀X₁S₁X₂S₂ ... X_mS_m (S_m - верхушка магазина). Каждый X_i - символ грамматики (терминальный или нетерминальный), а S_i - символ состояния.

Заметим, что символы грамматики (либо символы состояний) не обязательно должны размещаться в магазине. Однако, их использование облегчает понимание поведения LR-анализатора.

Элемент функции действий Action[S_m; a_i] для символа состояния S_m и входа , может иметь одно из четырех значений:

1. shift S (сдвиг), где S - символ состояния,
2. reduce A γ (свертка по правилу грамматики A γ),
3. accept (допуск),
4. error (ошибка).

Элемент функции переходов Goto[S_m; A] для символа состояния S_mи входа , может иметь одно из двух значений:

Рис. 4.6.

1. S, где S - символ состояния,
2. error (ошибка).

Конфигурацией LR(1)-анализатора называется пара, первая компонента которой - содержимое магазина, а вторая - непросмотренный вход:

(S₀X₁S₁X₂S₂ ... X_mS_m, a_ia_i+1 ... a_n$)

Эта конфигурация соответствует правой сентенциальной форме

X₁X₂ ... X_ma_ia_i+1 ... a_n

Префиксы правых сентенциальных форм, которые могут появиться в магазине анализатора, называются активными префиксами. Основа сентенциальной формы всегда располагается на верхушке магазина. Таким образом, активный префикс - это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы.

Когда анализатор начинает работу, в магазине находится только символ начального состояния S₀, на входной ленте - анализируемая цепочка с маркером конца.

Каждый очередной шаг анализатора определяется текущим входным символом a_i и символом состояния на верхушке магазина S_m следующим ниже образом.

Пусть LR(1)-анализатор находится в конфигурации

(S₀X₁S₁X₂S₂ ... X_mS_m, a_ia_i+1 ... a_n$)

Анализатор может проделать один из следующих шагов:

1. Если Action[S_m, a_i] = shift S, то анализатор выполняет сдвиг, переходя в конфигурацию

То есть, в магазин помещаются входной символ a_i и символ состояния S, определяемый Action[S_m, a_i]. Текущим входным символом становится a_i+1.

1. Если Action[S_m, a_i] = reduce A γ, то анализатор выполняет свертку, переходя в конфигурацию

где S = Goto[S_m-r; A] и r - длина γ, правой части правила вывода. Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние S_m-r. Затем анализатор помещает в магазин A - левую часть правила вывода, и S - символ состояния, определяемый Goto[S_m-r, A]. На шаге свертки текущий входной символ не меняется. Для LR(1)- анализаторов последовательность символов грамматики X_m-r+1 ... Xm, удаляемых из магазина , всегда соответствует γ - правой части правила вывода, по которому делается свертка. После осуществления шага свертки генерируется выход LR(1)-анализатора, то есть исполняются семантические действия, связанные с правилом, по которому делается свертка, например, печатаются номера правил, по которым делается свертка. Заметим, что функция Goto таблицы анализа, построенная по грамматике G, фактически представляет собой функцию переходов детерминированного конечного автомата, распознающего активные префиксы G.

1. Если Action[S_m, a_i] = accept, то разбор успешно завершен.
2. Если Action[S_m, a_i] = error, то анализатор обнаружил ошибку, и выполняются действия по диагностике и восстановлению.

Пример 4.10. Рассмотрим грамматику арифметических выражений G = ({E, T, F}, {id, +, *}, P, E) с правилами:

1. E E + T
2. E T
3. T T * F
4. T F
5. F id

На рис. 4.7 изображены функции Action и Goto, образующие LR(1)-таблицу для этой грамматики. Элемент Si функции Action означает сдвиг и помещение в магазин состояния с номером i, Rj - свертку по правилу номер j, acc - допуск, пустая клетка - ошибку. Для функции Goto символ i означает помещение в магазин состояния с номером i, пустая клетка - ошибку.

На входе id + id * id последовательность состояний магазина и входной ленты показаны на рис. 4.8. Например, в первой строке LR-анализатор находится в нулевом состоянии и "видит" первый входной символ id. Действие S6 в нулевой строке и столбце id в поле Action (рис. 4.7) означает сдвиг и помещение символа состояния 6 на верхушку магазина. Это и изображено во второй строке: первый символ id и символ состояния 6 помещаются в магазин, а id удаляется со входной ленты.

Текущим входным символом становится +, и действием в состоянии 6 на вход + является свертка по F id. Из магазина удаляются два символа (один символ состояния и один символ грамматики). Затем анализируется нулевое состояние. Поскольку Goto в нулевом состоянии по символу F - это 3, F и 3 помещаются в магазин. Теперь имеем конфигурацию, соответствующую третьей строке. Остальные шаги определяются аналогично.

Конструирование LR(1)-таблицы

Рассмотрим алгоритм конструирования таблицы, управляющей LR(1) - анализатором.

Пусть G = (N, T, P, S) - КС-грамматика. Пополненной грамматикой для данной грамматики G называется КС- Состояния Action Goto

Рис. 4.7.

Рис. 4.8.

грамматика

то есть эквивалентная грамматика, в которой введен новый начальный символ S' и новое правило вывода S' S.

Это дополнительное правило вводится для того, чтобы определить, когда анализатор должен остановить разбор и зафиксировать допуск входа. Таким образом, допуск имеет место тогда и только тогда, когда анализатор готов осуществить свертку по правилу S' S.

LR(1)-ситуацией называется пара [A .β, a], где A β - правило грамматики, a - терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

Будем говорить, что LR(1)-ситуация [A .β, a] допустима для активного префикса +, если существует вывод , где + = γ и либо a - первый символ w, либо w = e и a = $.

Будем говорить, что ситуация допустима, если она допустима для какого-либо активного префикса.

Пример 4.11. Дана грамматика G = ({S, B}, {a, b}, P, S) с правилами

S BB

B aB | b

Существует правосторонний вывод . Легко видеть, что ситуация [B a.B, a] допустима для активного префикса + = aaa, если в определении выше положить γ = aa, A = B, w = ab, = a, β = B. Существует также правосторонний вывод . Поэтому для активного префикса Baa допустима ситуация [B a.B, $].

Центральная идея метода заключается в том, что по грамматике строится детерминированный конечный автомат, распознающий активные префиксы. Для этого ситуации группируются во множества, которые и образуют состояния автомата. Ситуации можно рассматривать как состояния недетерминированного конечного автомата, распознающего активные префиксы, а их группировка на самом деле есть процесс построения детерминированного конечного автомата из недетерминированного.

Анализатор, работающий слева-направо по типу сдвиг- свертка, должен уметь распознавать основы на верхушке магазина. Состояние автомата после прочтения содержимого магазина и текущий входной символ определяют очередное действие автомата. Функцией переходов этого конечного автомата является функция переходов LR-анализатора.

Чтобы не просматривать магазин на каждом шаге анализа, на верхушке магазина всегда хранится то состояние, в котором должен оказаться этот конечный автомат после того, как он прочитал символы грамматики в магазине от дна к верхушке. Рассмотрим ситуацию вида [A .Bβ, a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод , где z = y. Предположим, что из βax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B q имеется вывод . Таким образом [B .q, b] также допустима для z и ситуация [A B.β, a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из β, либо из β выводится e в выводе и тогда b равно a. То есть b принадлежит FIRST(β ax). Построение всех таких ситуаций для данного множества ситуаций, то есть его замыкание, делает приведенная ниже функция closure.

Система множеств допустимых LR(1)-ситуаций для всевозможных активных префиксов пополненной грамматики называется канонической системой множеств допустимых LR(1)-ситуаций. Алгоритм построения канонической системы множеств приведен ниже.

Алгоритм 4.10. Конструирование канонической системы множеств допустимых LR(1)-ситуаций.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Каноническая система C множеств допустимых LR(1)-ситуаций для грамматики G.

Метод. Выполнить для пополненной грамматики G' процедуру items, которая использует функции closure и goto.

function closure(I){ /* I - множество ситуаций */

 do{

  for (каждой ситуации [A  .Bβ, a] из I,

  каждого правила вывода B  γ из G',

  каждого терминала b из FIRST(βa),

  такого, что [B .γ, b] нет в I)

  добавить [B .γ, b] к I;

 }

 while (к I можно добавить новую ситуацию);

 return I;

}

function goto(I,X){ /* I - множество ситуаций;

                  X - символ грамматики */

  Пусть J = {[A  X.β; a] | [A  .Xβ, a] in I};

  return closure(J);

 }

 

procedure items(G'){ /* G' - пополненная

               грамматика */

  I' = closure({[S'  .S, $]});

  C = {I₀};

  do{

    for (каждого множества ситуаций I из

     системы C, каждого символа грамматики X

      такого, что goto(I, X) не пусто

     и не принадлежит C)

     добавить goto(I, X) к системе C;

   }

   while (к C можно добавить новое множество

         ситуаций);

  

Если I - множество ситуаций, допустимых для некоторого активного префикса +, то goto(I, X) - множество ситуаций, допустимых для активного префикса +X.

Работа алгоритма построения системы C множеств допустимых LR(1)-ситуаций начинается с того, что в C помещается начальное множество ситуаций I₀ = closure({[S' .S, $]}). Затем с помощью функции goto вычисляются новые множества ситуаций и включаются в C.

По-существу, goto(I, X) - переход конечного автомата из состояния I по символу X.

Рассмотрим теперь, как по системе множеств LR(1)-ситу- аций строится LR(1)-таблица, то есть функции действий и переходов LR(1)-анализатора.

Алгоритм 4.11. Построение LR(1)-таблицы.

Вход. Каноническая система C = {I₀, I₁, ... , I_n} множеств допустимых LR(1)-ситуаций для грамматики G.

Выход. Функции Action и Goto, составляющие LR(1)- таблицу для грамматики G.

Метод. Для каждого состояния i функции Action[i, a] и Goto[i, X] строятся по множеству ситуаций I_i:

1. Значения функции действия (Action) для состояния i определяются следующим образом:
1. если (a - терминал) и goto(I_i, a)= I_j , то полагаем Action[i, a] = shift j;
2. если , причем A S', то полагаем Action[i, a] = reduce A ;
3. если , то полагаем Action[i, $] = accept.
2. Значения функции переходов для состояния i определяются следующим образом: если goto(I_i, A) = I_j , то Goto[i, A] = j (здесь A - нетерминал).
3. Все входы в Action и Goto, не определенные шагами 2 и 3, полагаем равными error.
4. Начальное состояние анализатора строится из множества, содержащего ситуацию [S' .S, $].

Таблица на основе функций Action и Goto, полученных в результате работы алгоритма 4.11., называется канонической LR(1)-таблицей. Работающий с ней LR(1)-анализатор, называется каноническим LR(1)-анализатором.

Пример 4.12. Рассмотрим следующую грамматику, являющуюся пополненной для грамматики из примера 4.8.:

(0) E' E

(1) E E + T

(2) E T

(3) T T * F

(4) T F

(5) F id.

Множества ситуаций и переходы по goto для этой грамматики приведены на рис. 4.9. LR(1)-таблица для этой грамматики приведена на рис. 4.7.

Проследим последовательность создания этих множеств более подробно.

1. Вычисляем I₀ = closure({[E' .E, $]}).
1. Ситуация [E' .E, $] попадает в него по умолчанию как исходная.
2. Если обратиться к обозначениям функции closure, то для нее

Значит, для терминала $ добавляем ситуации на основе правил со знаком E в левой части правила. Это правила

и соответствующие им ситуации

1. Просматриваем получившиеся ситуации. Для ситуации [E .E + T, $] β = +, поэтому first(βa) = first(+$) = {+}. На основе этого добавляем к I₀ [E E + .T, +] и [E .T, +].
2. Для ситуации [E .T, $] β = e, first(βa) = {$}. Поэтому добавляем к I₀ [T . T * F, $] и [T .F, $].
3. Подобно этому для ситуации [E .T, +] β = e, first(βa) = {+}. Поэтому добавляем к I₀ [T .T * F, +] и [T .F, +].
4. Из ситуации [T . T * F, +] β = *, first(βa) = {*}: Поэтому добавляем к I₀

увеличить изображение
Рис. 4.9.

[T .T * F, *] и [T .F, *]

1. Далее из ситуации [T .F, *] получаем ситуацию [F . id, *]. из ситуации [T . F, $] - ситуацию [F . id, $], а из ситуации [T . F, +] - [F . id, *].

Таким образом, все 14 искомых ситуаций I₀ получены.

Возвращаемся в головную функцию items, включаем I₀ в множество C и исследуем непустые итоги применения функции goto(I₀; X), где .

Если посмотреть на вид правил в функции goto(I₀; X), то видно, что X должен встретиться в правой части хотя бы одного правила. Для E0 таких правил у нас нет, поэтому значение функции goto(I₀, E') пусто.

Возьмем goto(I0; E). E встречается после точки в правых частях двух ситуаций из I0, значит берем эти два правила и переносим в них точки на один символ вправо (пока есть куда - не уперлись в запятую), получаем:

[E' E., $]

и

[E E. + T, $|+]

Вычислим от каждой из этих ситуаций функцию closure. Но, поскольку справа от точки здесь либо пустая цепочка, либо терминал, то никаких новых ситуаций не возникает. Дальше отслеживаем, может ли куда-то сдвинуться точка дальше на право и по какому символу. Если может, строим соответствующее множество (рис. 4.9). И т.д.

LR(1)-грамматики

Если для КС-грамматики G функция Action, полученная в результате работы алгоритма 4.11., не содержит неоднозначно определенных входов, то грамматика называется LR(1)- грамматикой.

Язык L называется LR(1)-языком, если он может быть порожден некоторой LR(1)-грамматикой.

Иногда используется другое определение LR(1)-грамматики. Грамматика называется LR(1), если из условий

3. FIRST(w)=FIRST(y)

следует, что uAy = zBx (то есть u = z, A = B и x = y).

Согласно этому определению, если uvw и uvy - правовыводимые цепочки пополненной грамматики, у которых FIRST(w) = FIRST(y) и A β - последнее правило, использованное в правом выводе цепочки uvw, то правило A β должно применяться и в правом разборе при свертке uvy к uAy. Так как A дает β независимо от w, то LR(1)-условие означает, что в FIRST(w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.

Можно доказать, что эти два определения эквивалентны. Дадим теперь определение LR(k)-грамматики.

Определение. Пусть G = (N, Σ, P, S) - КС-грамматика и G' = (N', Σ, P', S') - полученная из нее пополненная грамматика. Будем называть G LR(k)-грамматикой для k 0, если из условий

(1)

(2)

(3)FIRST_k(w) = FIRST_k(y)

следует, что Ay = γBx (т.е. = γ, A = B и x = y):

Грамматика G называется LR-грамматикой, если она LR(k)-грамматика для некоторого k 0:

Интуитивно это определение говорит о том, что если βw и βy - правовыводимые цепочки пополненной грамматики, у которых FIRST_k(w) = FIRST_k(y), и A β - последнее правило, использованное в правом выводе цепочки βw, то правило A β должно использоваться также в правом разборе при свертке βy к Ay. Так как A даeт β независимо от w, то LR(k)-условие говорит о том, что в FIRSTk(w) содержится информация, достаточная для определения того, что β за один шаг выводится из A. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики. Кроме того, работая с LR(k)-грамматикой, мы всегда знаем, допустить ли данную входную цепочку или продолжать разбор.

Пример 4.13. Рассмотрим грамматику G с правилами

S Sa|a

Согласно определению, G не LR(0)-грамматика, так как из трeх условий

(1)

(2)

(3)FIRST₀(e) = FIRST₀(a) = e

не следует, что S'a = S: Применяя определение к этой ситуации, имеем = e; β = S; ω = e; γ = e; A = S', B = S; x = e и y = a. Проблема здесь заключается в том, что нельзя установить, является ли S основой правовыводимой цепочки Sa, не видя символа, стоящего после S (т.е. наблюдая "нулевое" количество символов). В соответствии с интуицией G не должна быть LR(0)- грамматикой и она не будет ею, если пользоваться первым определением. Это определение мы и будем использовать далее.

Пример 4.14. Пусть G - леволинейная грамматика с правилами

Заметим, что G не является LR(k)-грамматикой ни для какого k.

Допустим, что G - LR(k)-грамматика. Рассмотрим два правых вывода в пополненной грамматике G':

Эти два вывода удовлетворяют условию из определения LR(k)- грамматики при = e, β = e, ω = a^kb, γ = e и y = a^kc: Но так как заключение неверно, т.е. A B, то G - не LR(k)-грамматика. Более того, так как LR(k)-условие нарушается для всех k, то G - не LR-грамматика.

Если грамматика не является LR(1), то анализатор типа сдвиг-свертка при анализе некоторой цепочки может достигнуть конфигурации, в которой он, зная содержимое магазина и следующий входной символ, не может решить, делать ли сдвиг или свертку (конфликт сдвиг/свертка), или не может решить, какую из нескольких сверток применить (конфликт свертка/свертка).

В частности, неоднозначная грамматика не может быть LR(1). Для доказательства рассмотрим два различных правых вывода

(1)

(2)

Нетрудно заметить, что LR(1) - условие (согласно второму определению LR(1)-грамматики) нарушается для наименьшего из чисел i, для которых u_n-i v_m-i.

Пример 4.15. Рассмотрим ещe раз грамматику условных операторов:

Если анализатор типа сдвиг-свертка находится в конфигурации, такой, что необработанная часть входной цепочки имеет вид else ... $, а в магазине находится ... if E then S, то нельзя определить, является ли if E then S основой, вне зависимости от того, что лежит в магазине ниже. Это конфликт сдвиг/свертка. В зависимости от того, что следует на входе за else, правильной может быть свертка по S if E then S или сдвиг else, а затем разбор другого S и завершение основы if E then S else S. Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не является LR(1).

Эта грамматика может быть преобразована к LR(1)-виду следующим образом:

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

Справедливы также следующие утверждения [2].

Теорема 4.7. Каждый LR(1)-язык является детерминированным КС-языком.

Теорема 4.8. Если L - детерминированный КС-язык, то существует LR(1)-грамматика, порождающая L.

Теорема 4.9. Для любой LR(k)-грамматики для k > 1 существует эквивалентная ей LR(k Gamma 1)-грамматика.

Доказано, что проблема определения, порождает ли грамматика LR-язык, является алгоритмически неразрешимой.

Восстановление процесса анализа после синтаксических ошибок

Одним из простейших методов восстановления после ошибки при LR(1)-анализе является следующий. При синтаксической ошибке просматриваем магазин от верхушки, пока не найдем состояние s с переходом на выделенный нетерминал A. Затем сканируются входные символы, пока не будет найден такой, который допустим после A. В этом случае на верхушку магазина помещается состояние Goto[s, A] и разбор продолжается. Для нетерминала A может иметься несколько таких вариантов. Обычно A - это нетерминал, представляющий одну из основных конструкций языка, например оператор.

В лекции "2 - Клеточная оболочка" также много полезной информации.

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

Варианты LR-анализаторов

Часто построенные таблицы для LR(1)-анализатора оказываются довольно большими. Поэтому при практической реализации используются различные методы их сжатия. С другой стороны, часто оказывается, что при построении для языка синтаксического анализатора типа "сдвиг-свертка" достаточно более простых методов. Некоторые из этих методов базируются на основе LR(1)-анализаторов.

Одним из способов такого упрощения является LR(0)- анализ - частный случая LR-анализа, когда ни при построении таблиц, ни при анализе не учитывается аванцепочка.

Еще одним вариантом LR-анализа являются так называемые SLR(1)-анализаторы (Simple LR(1)). Они строятся следующим образом. Пусть C = {I₀, I₁, ... , I_n} - набор множеств допустимых LR(0)-ситуаций. Состояния анализатора соответствуют I_i. Функции действий и переходов анализатора определяются следующим образом.

1. Если , то определим Action[i, a] = shift j.
2. Если , то, для всех , A S', определим Action[i, a] = reduce A u
3. Если , то определим Action[i, $] = accept.
4. Если goto(I_i, A) = I_j , где , то определим Goto[i, A] = j.
5. Остальные входы для функций Action и Goto определим как error.
6. Начальное состояние соответствует множеству ситуаций, содержащему ситуацию [S' .S]

Распространенным вариантом LR(1)-анализа является также LALR(1)-анализ. Он основан на объединении (слиянии) некоторых таблиц. Назовем ядром множества LR(1)-ситуаций множество их первых компонент (то есть во множестве ситуаций не учитываются аванцепочки). Объединим все множества ситуаций с одинаковыми ядрами, а в качестве аванцепочек возьмем объединение аванцепочек. Функции Action и Goto строятся очевидным образом. Если функция Action таким образом построенного анализатора не имеет конфликтов, то он называется LALR(1)-анализатором (LookAhead LR(1)).Если грамматика является LR(1), то в таблицах LALR(1) анализатора могут появиться конфликты типы свертка-свертка (если одно из объединяемых состояний имело ситуации [A , a] и [B β, b], а другое [A , b] и [B β a], то в LALR(1) появятся ситуации [A , {a, b}] и [B β, {b, a}]). Конфликты типа сдвиг-свертка появиться не могут, поскольку аванцепочка для сдвига во внимание не принимается.