2004 г.

Глава 3. Синтаксический анализ

3.1. Основные понятия и определения

Пусть G - контекстно-свободная грамматика, где N- множество нетерминальных символов, T - множество терминальных символов, P - множество правил вывода и S - аксиома. Будем говорить, что uxv выводится за один шаг из uAv (и записывать это как uAv uxv ), если A->x - правило вывода u и v и -произвольные строки из (N T)* . Если u₁ u₂ ... u_n, будем говорить, что из u₁ выводится u_n, и записывать это как u₁ *u_n т.е.:

1. u *u для любой строки u,
2. если u *v и v *w , то u *w .

Аналогично, " + " означает выводится за один или более шагов. Если дана грамматика G с начальным символом S, отношение + можно использовать для определения L(G) - языка, порожденного G . Строки L(G) могут содержать только терминальные символы G. Строка терминалов w принадлежит L(G) тогда и только тогда, когда S +w . Строка w называется предложением в G.

Если S*w , где u может содержать нетерминалы, то u называется сентенциальной формой в G. Предложение - это сентенциальная форма, не содержащая нетерминалов.

Рассмотрим выводы, в которых в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала. Такой вывод называется левосторонним. Если S *u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определяется правосторонний вывод.

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

Дерево вывода в грамматике G=(N,T,P,S) - это помеченное упорядоченное дерево, каждая вершина которого помечена символом из множества NT{e}. Если внутренняя вершина помечена символом A, а ее прямые потомки - символами X₁,...,X_n , то A -> X₁X₂...X_n - правило этой грамматики.

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

1. корень дерева D помечен S;
2. каждый лист помечен либо aT , либо e;
3. каждая внутренняя вершина помечена нетерминалом;
4. если N - нетерминал, которым помечена внутренняя вершина и X₁,...,X_n - метки ее прямых потомков в указанном порядке, то N -> X₁...X_k - правило из множества P.

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

1. Q- конечное множество символов состояний, представляющих всевозможные состояния управляющего устройства;
2. T- конечный входной алфавит;
3. Г - конечный алфавит магазинных символов;
4. d- функция переходов - отображение множества Q x (T{e}) x Г в множество конечных подмножеств Q x Г* , т.е.d:Q x (T{e}) x Г -> {Q x Г*} ;
5. q₀ Q - начальное состояние управляющего устройства;
6. Z₀ Г- символ, находящийся в стеке в начальный момент (начальный символ);
7. F Q- множество заключительных состояний

Конфигурацией МП-автомата называется тройка (q,w,u) Q x T* x Г* , где

1. q- текущее состояние управляющего устройства;
2. w- неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если we, то считается, что вся входная лента прочитана;
3. u- содержимое стека; самый левый символ цепочки u считается верхним символом стека; если u=e, то стек считается пустым.

Такт работы МП-автомата P будем представлять в виде бинарного отношения |-, определенного на конфигурациях. Будем писать (q,aw,zu)|-(q`,w,vu) если множество d(q,a,Z) содержит (d`,v) , где q, q`Q, aT{e}, wT*, ZГ, u, vГ*.

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

Говорят, что цепочка w допускается МП-автоматом P, если (q₀,w,Z₀)|-*(q,e,u) для некоторых qF и uГ* . Языком, определяемым (или допускаемым) автоматом P (обозначается L(P) ), называют множество цепочек, допускаемых автоматом P. Иногда допустимость определяют несколько иначе: цепочка допускается МП-автоматом P, если (q₀,w,Z₀)|-*(q,e,e). Эти определения эквивалентны.

3.2. Таблично-управляемый предсказывающий разбор

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

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

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

Таблично-управляемый предсказывающий анализатор имеет входной буфер, таблицу анализа и выход. Входной буфер содержит распознаваемую строку, за которой следует $ - правый концевой маркер, признак конца строки. Магазин содержит последовательность символов грамматики с $ на дне. Вначале стек содержит начальный символ грамматики на верхушке и $ на дне. Таблица анализа - это двумерный массив M[A,a] , где A - нетерминал, и a - терминал или символ $.

Анализатор управляется программой, которая работает следующим образом. Она рассматривает X - символ на верхушке стека и a - текущий входной символ. Эти два символа определяют действие анализатора. Имеются три возможности.

1. Если X=a=$ , анализатор останавливается и сообщает об успешном окончании разбора.
2. Если X=a#$ , анализатор удаляет X из стека и продвигает указатель входа на следующий входной символ.
3. Если X - нетерминал, программа заглядывает в таблицу M[X,a] . По этому входу хранится либо правило для X, либо ошибка. Если, например, M[X,a]=(X -> UVW) , анализатор заменяет X на верхушке стека на WVU {на верхушке U }. Будем считать, что анализатор в качестве выхода просто печатает использованные правила вывода. Если M[X,a]=error , анализатор обращается к подпрограмме анализа ошибок.

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

Алгоритм 3.1. Нерекурсивный предсказывающий анализ.

Repeat  X := верхний символ стека;
        if  X - терминал или $ 
        then if X  =  InSym
             then удалить X  из стека;
                  InSym  := очередной символ;
             else error()
             end
        else /*X = нетерминал*/
             if   M[X,InSym]=X -> Y1Y2...Yk
             then удалить X  из стека;
                  поместить Yk, Yk-1,...,Y1  в стек 
(Y1 на верхушку);
                  вывести правило  X -> Y1Y2...Yk
             else error() /*вход таблицы M пуст*/
             end 
        end
Until X = $  /*стек пуст*/

Рис. 3.3

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

Пример 3.1. Рассмотрим грамматику арифметических выражений:

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

На входе id+id*id предсказывающий анализатор совершает последовательность шагов, изображенную на рис.3.5. Указатель входа указывает на самый левый символ в колонке Вход. Если внимательно проанализировать действия анализатора, то видно, что он осуществляет левый вывод, т.е. правила применяются в соответствии с левым выводом. За уже просмотренными входными символами следуют символы грамматики в стеке (сверху вниз), что соответствует левым сентенциальным формам вывода. Дерево разбора приведено на рис. 3.6.

3.2.2. Множества FIRST и FOLLOW

При построении предсказывающего анализатора полезными оказываются две функции, связанные с грамматикой G . Эти функции, FIRST и FOLLOW, позволяют построить таблицу предсказывающего разбора для G, если, конечно, это возможно. Множества, даваемые этими функциями, могут, кроме того, быть использованы при восстановлении после ошибок.

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

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в некоторой сентенциальной форме, т.е. множество терминалов a таких, что существует вывод вида S*uAav для некоторых u и v . Отметим, что между A и a в процессе вывода могут появиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символом некоторой сентенциальной формы, то $ принадлежит FOLLOW(A). Для построения FIRST(X) для всех символов грамматики X применим следующий алгоритм.

Алгоритм 3.2. Построение множеств FIRST для символов грамматики.

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

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

Шаг 3. Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы или e: если X - нетерминал и имеется правило вывода X -> Y₁Y₂...Y_k , то включить a в FIRST(X), если для некоторого i a FIRST(Y₁) и e принадлежит всем FIRST(Y₁),..., FIRST(Y_i-1), т.е.Y₁...Y_i-1 *e . Если e принадлежит FIRST(Y_j) для всех , то добавить e к FIRST(X). Например, все, что принадлежит FIRST(Y₁)принадлежит также и FIRST(X). Если из Y₁ не выводится e, то ничего больше не добавляем к FIRST(X), но если Y₁ *e, то добавляем FIRST(Y₂), и т.д.

Теперь FIRST для любой строки X₁X₂...X_n можно вычислить следующим образом.

Шаг 1. Полагаем FIRST(X₁X₂...X_n)= {}.

Шаг 2. Добавим к FIRST(X₁X₂...X_n) все не e символы из FIRST(X₁). Добавим также не e символы из FIRST(X₂), если e FIRST(X₁), не e символы из FIRST(X₃), если e принадлежит как FIRST(X₁), так и FIRST(X₂), и т.д. Наконец, добавим e к FIRST(X₁X₂...X_n), если e FIRST(X_i) для всех i.

Для вычисления FOLLOW(A) для нетерминала A применим алгоритм 3.3.

Алгоритм 3.3. Построение FOLLOW(X) для всех X - нетерминалов грамматики.

Шаг 1. Положить FOLLOW(X)= {}.

Шаг 2. Поместить $ в FOLLOW(S), где S - начальный символ и $ - правый концевой маркер.

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

Шаг 4. Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X): eсли есть правило вывода A ->uB или A -> uBv, где FIRST(v) содержит e (т.е. v *e ), то все из FOLLOW(A) добавить к FOLLOW(B).

Пример 3.2. Рaссмотрим снова грамматику (*).

Для нее

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.

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

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 выполняется следующее:

1. ни для какого терминала a одновременно из u и v не выводятся строки, начинающиеся с a
2. только из одной из строк u или v может выводиться пустая строка;
3. если v *e, то из u не выводится никакая строка, начинающаяся с терминала из FOLLOW(A).

Эквивалентным является следующее определение:

КС-грамматика называется LL(1) - грамматикой, если из существования двух левых выводов

1. S *wAu wvu *wx ,
2. S *wAu wzu *wy,

для которых FIRST(x)=FIRST(y), вытекает, что v=z. Это означает, что для данной цепочки wAu и первого символа, выводящегося из Au (или $), существует не более одного правила, которое может быть применено к A, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w и продолжающейся этим первым символом.

Язык, для которого можно построить LL(1)- грамматику, называют LL(1)-языком.

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

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

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

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

Грамматика леворекурсивна, если в ней имеется нетерминал A такой, что существует вывод A + Au для некоторой строки u. Леворекурсивные грамматики не могут анализироваться методами сверху-вниз, поэтому необходимо удаление левой рекурсии. Непосредственную левую рекурсию, т.е. рекурсию вида A -> Au , можно удалить следующим способом. Сначала группируем A- правила:

где никакая из строк v_i не начинается с A. Затем заменяем A- правила на

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

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

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

Шаг 2. for  i := 1 to n do
    for  j := 1 to i-1  do
    пусть Aj -> v1|v2|...|vk  - все текущие правила для Aj ;
    заменить все правила вида Ai -> Aju 
 на правила  Ai -> v1u|v2u|...|vku
        end;
        удалить непосредственную левую рекурсию 
в правилах для  Ai;
       end

В результате на следующей итерации (по i ) внутренний цикл (по j) последовательно увеличивает нижнюю границу по m в любом правиле A_i -> A_mu, пока не будет . Затем, удаляя непосредственную левую рекурсию для A_i - правил, делаем m больше i.

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

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

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

Если A -> uv₁|uv₂ - два A - правила и входная строка начинается с непустой строки, выводимой из u, мы не знаем, разворачивать ли по uv₁ или по uv₂. Однако можно отложить решение, развернув A -> uA` . Тогда после анализа того, что выводимо из u, можно развернуть A` -> v₁ или A` -> v₂ . Левофакторизованные правила принимают вид:

A -> uA`

A` -> v₁|v₂

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

Для каждого нетерминала A ищем самый длинный префикс u, общий для двух или более его альтернатив. Если u#e, т.е. существует нетривиальный общий префикс, заменяем все A - правила A -> uv₁|uv₂|...|uv_n|z , где z - все альтернативы, не начинающиеся с u, на

A -> uA`|z

A` -> v₁|v₂|...|v_n

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

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

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

К сожалению, грамматика остается неоднозначной, а значит, и не , что иллюстрируется рис.3.8.

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

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

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

Рис. 3.9

3.2.8. Диаграммы переходов для рекурсивного спуска

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

Пусть имеется LL(1) - грамматика. Тогда для каждого нетерминала построение диаграммы включает следующие шаги:

Шаг 1. Вводим начальное и заключительное состояния.

Шаг 2. Для каждого правила вывода A -> X₁X₂...X_n строим путь из начального в конечное состояние с дугами, помеченными X₁X₂...X_n. Если анализатор, построенный по диаграмме переходов, оказывается в состоянии s и дуга, помеченная терминалом a, ведет в состояние t, то если очередной входной символ равен a, анализатор продвигает вход на одну позицию вправо и переходит в состояние t. Если же дуга помечена нетерминалом A, анализатор входит в начальное состояние для A без продвижения входа. После того как он достигает заключительного состояния для A, он переходит в состояние t, что означает "чтение" A из входа при переходе из состояния s в состояние t. Наконец, если есть дуга из s в t, помеченная e, то анализатор переходит из s в t, не читая входа.

Если следовать программе рекурсивного спуска, то переход по e должен всегда выбираться в качестве последней альтернативы. Диаграммы переходов могут быть упрощены подстановкой одной в другую. Рассмотрим, например, диаграммы для арифметических выражений на рис 3.10.

Рис. 3.12

На рис.3.11 приведена эквивалентная диаграмма переходов для E`. Можно подставить диаграмму для E` рис.3.11 в диаграмму для E рис.3.10. Получится диаграмма рис.3.11 для E. Наконец, видно, что в этой диаграмме нулевая и четвертая вершины эквивалентны и их можно слить. Так же можно поступить с диаграммами для T и T`. В результате получится набор диаграмм рис.3.12.

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

procedure E; 
  repeat T; until InSym  PLUS;
end;

3.2.9. Восстановление после синтаксических ошибок

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

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

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

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

3.3.1. Основа

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

Пример 3.5. Рассмотрим грамматику арифметических выражений, приведенную на рис.3.14 а). Строка a+b*c может быть сведена к S, как показано на рис.3.14.б). Дерево этой строки приведено на рис.3.14 в).

В строке a+b*c ищется подстрока, которую можно сопоставить с правой частью некоторого правила вывода. Этому удовлетворяют подстроки a, b и c. Если выбрать самое левое a и заменить его на F - левую часть правила F -> id , то получим строку F+b*c . Теперь правой части того же правила можно сопоставить подстроки b и c. Эти свертки представляют собой в обратном порядке правосторонний вывод:

Подстрока сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой строки. В приведенном выше выводе основы подчеркнуты. Самая левая подстрока, которая сопоставляется правой части некоторого правила вывода A -> v , не обязательно является основой, поскольку свертка по правилу A -> v может дать строку, которая не может быть сведена к аксиоме. Если, скажем, в примере 3.5 заменить a на F и b на F, то получим строку F+F*c , которая не может быть сведена к S.

Формально, основа правой сентенциальной формы z - это правило вывода A -> v и позиция в z, в которой может быть найдена строка v такие, что в результате замены v на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S *uAw uvw , то A -> w в позиции, следующей за u, это основа строки uvw. Строка w справа от основы содержит только терминальные символы. Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод uvw и не единственной может быть основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу.

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

S z₀ z₁ z₂ ...z_n-1 z_n =w

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

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

3.3.2. LR(k)-анализаторы

В названии LR(k) символ L означает, что разбор осуществляется слева-направо, R - что строится правый вывод в обратном порядке, k - число входных символов, на которые заглядывает вперед анализатор при разборе. Когда k опущено, имеют в виду 1. LR -анализ привлекателен по нескольким причинам:

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

Схематически структура -анализатора изображена на рис.3.15.

Он состоит из входа, выхода, стека, управляющей программы и таблицы анализа, которая имеет две части - действий и переходов. Управляющая программа одна и та же для всех анализаторов, разные анализаторы различаются таблицами анализа. Программа анализатора читает символы из входного буфера по одному за шаг. В процессе анализа используется стек, в котором хранятся строки вида S₀XS₁X₂S₂...X_mS_m (S_m - верхушка стека). Каждый Xi - символ грамматики (терминальный или нетерминальный), а S_i - символ, называемый состоянием. Каждый символ состояния выражает информацию, содержащуюся в стеке ниже него, а комбинация символа состояния на верхушке стека и текущего входного символа используется для индексации таблицы анализа и определяет решение о сдвиге или свертке. В реализации символы грамматики не обязательно должны размещаться в стеке. Однако их использование удобно для упрощения понимания поведения LR - анализатора.

Таблица анализа состоит из двух частей: действия (action) и переходов (goto). Начальное состояние этого ДКА - это состояние, помещенное на верхушку стека LR -анализатора в начале работы.

Конфигурация LR -анализатора - это пара, первая компонента которой - содержимое стека, а вторая- непросмотренный вход: (S₀XS₁X₂S₂...X_mS_m,A_iA_i+1...A_n$) . Эта конфигурация соответствует правой сентенциальной форме X₁X₂...X_mA_iA_i+1...A_n

Префиксы правых сентенциальных форм, которые могут появиться в стеке анализатора, называются активными префиксами. Активный префикс- это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы. Очередной шаг анализатора определяется текущим входным символом A_i и символом состояния на верхушке стека S_m. Элемент таблицы действий action[S_m,A_i] для состояния S_m и входа A_i, может иметь одно их четырех значений:

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

Конфигурации, получающиеся после каждого из четырех типов шагов, следующие

1. Если action[S_m,A_i]=shift S, то анализатор выполняет шаг сдвига, переходя в конфигурацию (S₀XS₁X₂S₂...X_mS_m,A_iA_i+1...A_n$). В стек помещаются как входной символ A_i, так и следующее состояние S , определяемое action[S_m,A_i]. Текущим входным символом становится A_i+1 .
2. Если action[S_m,A_i]=reduce A -> w, то анализатор выполняет свертку, переходя в конфигурацию (S₀XS₁X₂S₂...X_mS_m,A_iA_i+1...A_n$), где S=goto[S_m-r,A] и r - длина w, правой части правила вывода. Функция goto таблицы анализа, построенная по грамматике G, - это функция переходов детерминированного конечного автомата, распознающего активные префиксы G. Анализатор сначала удаляет из стека 2r символов ( r символов состояния и r символов грамматики), так что на верхушке оказывается состояние S_m-r . Затем анализатор помещает в стек как A - левую часть правила вывода, так и S - содержимое таблицы goto[S_m-r,A]. На шаге свертки текущий входной символ не меняется. Для LR - анализаторов X_m-r+1...X_m - последовательность символов грамматики, удаляемых из стека, всегда соответствует w - правой части правила вывода, по которому делается свертка. После осуществления шага свертки генерируется выход LR - анализатора, т.е. исполняются семантические действия, связанные с правилом, по которому делается свертка, например печатаются номера правил, по которым делается свертка.
3. Если action[S_m,A_i]=accept, то разбор завершен.
4. Если action[S_m,A_i]=error , анализатор обнаружил ошибку, то выполняются действия по диагностике и восстановлению.

Ниже приведен алгоритм LR -анализа. Все LR-анализаторы ведут себя одинаково. Разница между ними заключается в различном содержании таблиц действий и переходов.

Вначале в стеке помещено начальное состояние S₀, а в буфере w$, InSym содержит первый символ w$; Анализатор выполняет приведенную ниже программу до тех пор, пока будет достигнуто либо состояние accept, либо состояние error.

Пример 3.6. На рис.3.16 изображены функции action и goto LR - таблиц для грамматики арифметических выражений с бинарными операциями + и * примера 3.5. Здесь S_i означает сдвиг и помещение в стек состояния i, R_j - свертку по правилу номер j, acc - допуск, пустая клетка - ошибку.

Значение goto[S,A] для терминала A ищется в поле действия, связанном с действием сдвига по входу A в состоянии S. Поле перехода дает goto[S,A] для нетерминалов A.

На входе id+id*id последовательность состояний стека и входа показаны на рис.3.17. Например, в первой строке LR - анализатор находится в нулевом состоянии и читает первый входной символ id. Действие S₆ в нулевой строке и столбце id в поле action рис.3.17 означает сдвиг и помещение S₆ на верхушку стека. Это и изображено во второй строке: первый символ id и символ состояния S₆ помещаются в стек и id удаляется из входной строки.

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

3.3.3. LR-грамматики

Грамматики, для которых можно построить таблицу LR - разбора, называются LR-грамматиками. Есть КС-грамматики, не являющиеся LR-грамматиками, однако практически для описания языков программирования достаточно класса LR. Чтобы грамматика была LR, анализатор, работающий слева-направо по типу сдвиг-свертка, должен уметь распознавать основы на верхушке стека. Но если возможно распознать основу, зная только символы грамматики в стеке, то существует конечный автомат, который может, читая символы грамматики в стеке, начиная с верхушки, определить эту основу. Функцией переходов этого конечного автомата является таблица переходов LR-анализатора. Чтобы не просматривать стек на каждом шаге анализа, на верхушке стека всегда хранится то состояние, в котором должен оказаться этот конечный автомат после того, как он прочитал символы грамматики в стеке от дна к верхушке. Для принятия решения о сдвиге или свертке анализатор просматривает очередные k входных символов. Практический интерес представляют случаи k=0 и k=1 . Например, в таблице действий рис.3.16 используется один символ. Грамматика, которая может быть проанализирована LR анализатором, заглядывая на k входных символов на каждом шаге, называется LR(k) - грамматикой. Можно дать другое определение LR(k) -грамматики. Пополненной грамматикой для данной грамматики G называется КС-грамматика, в которой введена новая аксиома S` и правило вывода S` -> S . Это дополнительное правило вводится для того, чтобы определить, когда анализатор должет остановить разбор и зафиксировать допуск входа. Таким образом, допуск имеет место тогда и только тогда, когда анализатор осуществляет свертку по правилу S` -> S. Пополненная грамматика называется LR(k) для k 0., если из условий:

1. S` * uAw uvw ,
2. S` * zBx uvy,
3. FIRST(w)=FIRST(y)

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

Согласно этому определению, если uvw и uvy - правовыводимые цепочки пополненной грамматики, у которых FIRST(w)=FIRST(y)и A ->v - последнее правило, использованное в правом выводе цепочки , то правило A -> v должно применяться и в правом разборе при свертке uvy к uAy . Так как A дает v независимо от w, то LR(k) условие означает, что в FIRST(w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики. Кроме того, для LR(k) грамматики известно, когда допускается входная цепочка. Основная разница между LL - и LR - грамматиками заключается в следующем. Чтобы грамматика была LR(k), необходимо распознавать вхождение правой части правила вывода, просмотрев все, что выведено из этой правой части и заглянув на k входных символов вперед. Это требование существенно менее строгое, чем требование для LL(k) грамматики, когда необходимо определить применимое правило, видя только первые k символов, выводимых из его правой части. Класс LL-грамматик является собственным подклассом LR. Рассмотрим теперь конструирование таблиц LR -анализатора. LR(1) ситуацией называется пара [A -> u v,a], где A -> uv - правило грамматики, а a - терминал или правый концевой маркер $. "1" указывает на длину второй компоненты ситуации, которая называется аванцепочкой ситуации. Аванцепочка не играет роли в ситуациях вида [A -> u v,a], где v e, но ситуация вида [A -> u , a] ведет к свертке по правилу A -> u только если следующим входным символом является a. Таким образом, свертка по правилу A -> u требуется только для тех входных символов a, для которых [A -> u , a] является LR(1) ситуацией в состоянии на верхушке стека. Будем говорить, что LR(1) -ситуация [A -> u v,a] допустима для активного префикса z, если существует вывод S * yAw yuvw, где z = yu и либо a - первый символ w, либо (w=e)_^(a=$) (рис.3.18).

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

Пример 3.7. Рассмотрим грамматику

S -> BB
B -> aB|b

Существует правосторонний вывод S * aaBab aaaBab. Ситуация [B -> a B,a] допустима для активного префикса z=aaa , если в определении выше положить y=aa, A=B, w=ab, u=a, v=B. Существует также правосторонний вывод S * BaB BaaB. Из этого вывода видно, что для активного префикса Baa допустима ситуация [B -> a B,$].

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

Для конструирования набора множеств допустимых LR(1) - ситуаций будут применяться пополненная G` грамматика и процедуры-функции closure и goto.

Рассмотрим ситуацию вида [A -> u Bv,a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S * yAax yuBvax, где z=yu. Предположим, что из vax выводится терминальная строка bw. Тогда для некоторого правила вывода вида B -> q имеется вывод S * zBbw zqbw . Таким образом [B -> q,b] допустима для z. Здесь либо b может быть первым терминалом, выводимым из v, либо из v выводится e в выводе vax * bw и тогда b равно a, т.е. b FIRST(vax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает процедура closure. Aлгоритм построения множеств LR(1)- ситуаций приведен ниже. Алгоритм 3.8. Конструирование множеств LR(1)-ситуаций.

Алгоритм заключается в выполнении главной программы items, которая вызывает процедуры closure и goto

В анализаторах типа LR(0) при построении closure не учитываются терминалы из FIRST(va).

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

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

Пример 3.8. Рассмотрим пополненную грамматику примера 3.5.

E` -> E

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

Множество ситуаций и переходов для этой грамматики приведены на рис.3.19.

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

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

Алгоритм 3.9. Построение канонических таблиц LR анализатора.

Шаг 1. Строим набор множеств LR(1) C={I₀,I₁,...,I_n}- ситуаций для G`.

Шаг 2. Состояние i анализатора строится из I_i. Действия анализатора для состояния i определяются следующим образом:

a. если ([A -> u av,b]I_i) & (goto(I_i,a) = I_j) , то полагаем action[i,a]="shift j". Здесь a - терминал;
b. если ([A -> u ,a] I_i) & (A S`), то полагаем action [i,a]="reduce A -> u";
c. если [S` -> S $] I_i , полагаем action[i,$]= accept".

Шаг 3. Переходы для состояния i определяются следующим образом: если goto(I_i,A)=I_j , то goto[i,A]=j (здесь A - нетерминал).

Шаг 4. Все входы, не определенные шагами 2 и 3, полагаем равными "error".

Шаг 5. Начальное состояние анализатора строится из множества, содержащего ситуацию [S` -> S,$]. Если при применении этих правил возникает конфликт, т.е. в одном и том же множестве может быть более одного варианта действий (либо сдвиг/свертка, либо свертка/свертка), говорят, что грамматика не является LR(1) , и алгоритм завершается неуспешно.

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

3.3.4. Конфликты разбора типа сдвиг-свертка

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

Пример 3.9. Рассмотрим вновь следующую грамматику оператора if-then-else:

то нельзя определить, является ли if Ex then St основой, вне зависимости от того, что лежит в стеке ниже. Это конфликт сдвиг/свертка. В зависимости от того, что следует на входе за else, правильной может быть свертка по St -> if Ex then St или сдвиг else, а затем разбор другого St и завершение альтернативы if Ex then St else St. Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не LR(1). Эта грамматика может быть преобразована к LR(1) - виду следующим образом:

St -> CondSt | UnCondSt
CondSt -> IfThenSt | IfThenElseSt
FullSt -> IfThenElseSt | UnCondSt
IfThenElseSt -> if Ex then FullSt else St
IfThenSt -> if Ex then St

3.3.5. Восстановление после синтаксических ошибок

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

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

Назад Вперед