CodeNet / Приложения / Алгоритмы / Разбор выражений. Компиляторы и интерпретаторы. / Лекции по конструированию компиляторов
Лекции по конструированию компиляторов - Глава 3. Синтаксический анализ
3.1. Основные понятия и определения
Пусть G= - контекстно-свободная грамматика, где N -
множество нетерминальных символов, T - множество терминальных
символов, P - множество правил вывода и S - аксиома. Будем
говорить, что uxv выводится за один шаг из uAv (и записывать
это как uAv=>uxv), если A->x - правило вывода и u и v -
произвольные строки из (N U T)*. Если u1=>u2=>...=>un, будем
говорить, что из u1 выводится un, и записывать это как
u1=>*un. Т.е.:
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=>*u, где u может содержать нетерминалы, то u
называется сентенциальной формой в G. Предложение - это
сентенциальная форма, не содержащая нетерминалов.
Рассмотрим выводы, в которых в любой сентенциальной форме на
каждом шаге делается подстановка самого левого нетерминала.
Такой вывод называется левосторонним. Если S=>*u в процессе
левостороннего вывода, то u - левая сентенциальная форма.
Аналогично определяется правосторонний вывод.
Упорядоченным графом называется пара (V,E), где V обозначает
множество вершин, а E - множество линейно упорядоченных
списков дуг, каждый элемент которого имеет вид
((v,e1),(v,e2),...,(v,en)). Этот элемент указывает, что из
вершины a выходят n дуг, причем первой из них считается дуга,
входящая в вершину e1, второй - дуга, входящая в вершину e2, и
т.д.
Дерево вывода в грамматике G=(N,T,P,S) - это помеченное
упорядоченное дерево, каждая вершина которого помечена
символом из множества N U T U {e}. Если внутренняя вершина
помечена символом A, а ее прямые потомки - символами X1,...,
Xn, то A->X1X2...Xn - правило этой грамматики.
Упорядоченное помеченное дерево D называется деревом вывода
(или деревом разбора) в КС-грамматике G(S)=(N,T,P,S), если
выполнены следующие условия:
(1) корень дерева D помечен S;
(2) каждый лист помечен либо aX1...Xk - правило из множества P.
Автомат с магазинной памятью (сокращенно МП-автомат) - это
семерка P=(Q,T,Г,d,q0,Z0,F), где
(1) Q - конечное множество символов состояний,
представляющих всевозможные состояния управляющего
устройства;
(2) T - конечный входной алфавит;
(3) Г - конечный алфавит магазинных символов;
(4) d - функция переходов - отображение множества Qx(T U
{e})xГ в множество конечных подмножеств QxГ*, т.е. d:Qx(T
U {e})xГ -> {QxГ*};
(5) q0X1 X2 ..., которое должно быть применено к S. Затем
необходимо определить правило, которое должно быть применено к
X1, и т.д., до тех пор, пока в процессе такого построения
сентенциальной формы, соответствующей левому выводу, не будет
применено правило Y->a .... Этот процесс затем применяется для
следующего самого левого нетерминального символа
сентенциальной формы.
S S S
/ | \ / | \
X1 X2... X1 X2...
/ / |
........... .............
/ / |
Y Y |
/|\ /|\ Z
/ ... / ... /|\
a..........$ a...........$ a........b.......$
а) б) в)
Рис. 3.1
На рис. 3.2 приведена структура предсказывающего анализатора,
который определяет очередное правило из таблицы. Такую таблицу
множно построить непосредственно из грамматики.
+---------------+
Вход | a | + | b | $ |
+---------------+
^
|
+-+ +----------------------+
|X| | Программа предсказы- | Выход
Магазин |-|
|Y| +----------------------+
|Z| |
|-| v
|$| +---------------------+
+-+ | Таблица анализатора |
+---------------------+
Рис. 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. Рассмотрим грамматику арифметических выражений:
E -> T E'
E' -> + T E' | e
T -> F T' (*)
T' -> * F T' | e
F -> ( E ) | id
Таблица предсказывающего анализатора для нее изображена на
рис. 3.4. Здесь пустые клетки - входы ошибок. Непустые дают
правила, по которым делается развертка нетерминала.
---------------------------------------------------
Нетер-| Входной символ
|--------------------------------------------
минал | id | + | * | ( | ) | $
------+------+--------+--------+------+-----+------
E |E->TE'| | |E->TE'| |
E' | |E'->+TE'| | |E'->e|E'->e
T |T->FT'| | |T->FT'| |
T' | |T'->e |T'->*FT'| |T'->e|T'->e
F |F->id | | |F->(E)| |
-----------------------------------------------------
Рис. 3.4
----------------------------------
Магазин | Вход | Выход
--------+-----------+-------------
$E | id+id*id$ |
$E'T | id+id*id$ | E->TE'
$E'T'F | id+id*id$ | T->FT'
$E'T'id | id+id*id$ | F->id
$E'T' | +id*id$ | E
$E' | +id*id$ | T'->e / \
$E'T+ | +id*id$ | E'->+TE' / \
$E'T | id*id$ | T E'
$E'T'F | id*id$ | T->FT' /| / | \
$E'T'id | id*id$ | F->id F T' + T E'
$E'T' | *id$ | | / |
$E'T'F* | *id$ | T'->*FT' id / |
$E'T'F | id$ | F T'
$E'T'id | id$ | F->id | /|\
$E'T' | $ | id * F T'
$E' | $ | T'->e |
$ | $ | E'->e id
----------------------------------
Рис. 3.5 Рис. 3.6
На входе 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-
>Y1Y2...Yk, то включить a в FIRST(X), если для
некоторого i a*e. Если e
принадлежит FIRST(Yj) для всех j=1,2,...,k, то добавить
e к FIRST(X). Например, все, что принадлежит FIRST(Y1)
принадлежит также и FIRST(X). Если из Y1 не выводится
e, то ничего больше не добавляем к FIRST(X), но если
Y1=>*e, то добавляем FIRST(Y2), и т.д.
Теперь FIRST для любой строки X1X2...Xn можно вычислить
следующим образом.
Шаг 1. Полагаем FIRST(X1X2...Xn)={}.
Шаг 2. Добавим к FIRST(X1X2...Xn) все не e символы из
FIRST(X1). Добавим также не e символы из FIRST(X2), если
euBv, то все из 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*e. В этом случае нужно развернуть A в u,
если текущий входной символ принадлежит FOLLOW(A) или если
достигнут $ и $u грамматики выполнить шаги 1 и 2
Шаг 1. Для каждого терминала a из FIRST(u) добавить A->u к
M[A,a].
Шаг 2. Если eu к M[A,b] для каждого
терминала b из FOLLOW(A). Если eu к 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 =>* w A u => w v u =>* wx,
(2) S =>* w A u => w z u =>* wy,
для которых FIRST(x)=FIRST(y), вытекает, что v=z. Это
означает, что для данной цепочки wAu и первого символа,
выводящегося из Au (или $), существует не более одного
правила, которое может быть применено к A, чтобы получить
вывод какой-нибудь терминальной цепочки, начинающейся с w и
продолжающейся этим первым символом.
Язык, для которого можно построить LL(1)-грамматику,
называют LL(1)-языком.
Если таблица анализа имеет неоднозначно определенные входы,
то грамматика не является LL(1). Примером может служить
следующая грамматика:
St -> if Ex then St
| if Ex then St else St
| Cont
Ex -> ...
Эта грамматика неоднозначна, что иллюстрируется рис. 3.7.
Поскольку грамматика неоднозначна, она не является LL(1).
Проблема, порождает ли грамматика LL-язык, алгоритмически
неразрешима.
St St
/|\ /| \
/ | \ / | \
/ St \ / St ...
/ / \ \ / / \ \
/ / \ \ / / \ \
if E then if E then S else S if E then if E then S else S
а) б)
Рис. 3.7
3.2.5. Удаление левой рекурсии
Основная трудность при использовании предсказывающего анализа
- это написание такой грамматики для входного языка, чтобы по
ней можно было построить предсказывающий анализатор. Иногда с
помощью некоторых простых преобразований не LL(1)-грамматику
можно привести к LL(1)-виду. Среди этих преобразований
наиболее очевидными являются левая факторизация и удаление
левой рекурсии. Здесь необходимо сделать два замечания. Во-
первых, не всякая грамматика после этих преобразований
становится LL(1) и, во-вторых, после удаления левой рекурсии и
левой факторизации получающаяся грамматика может стать трудно
понимаемой.
Грамматика леворекурсивна, если в ней имеется нетерминал A
такой, что существует вывод A=>+Au для некоторой строки u.
Леворекурсивные грамматики не могут анализироваться методами
сверху-вниз, поэтому необходимо удаление левой рекурсии.
Непосредственную левую рекурсию, т.е. рекурсию вида A->Au,
можно удалить следующим способом. Сначала группируем A-
правила:
A -> Au1 | Au2 | ... | Aum | v1 | v2 | .... | vn
где никакая из строк vi не начинается с A. Затем заменяем A-
правила на
A -> v1A' | v2A' | .... | vnA'
A'-> u1A' | u2A' | .... | umA' | e
Нетерминал 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-1)-й итерации внешнего цикла на шаге 2 для любого
правила вида Ak->Alu, где kk. В результате
на следующей итерации (по i) внутренний цикл (по j)
последовательно увеличивает нижнюю границу по m в любом
правиле Ai->Amu, пока не будет m>=i. Затем, удаляя
непосредственную левую рекурсию для Ai-правил, делаем m больше
i.
Алгоритм 3.5 применим, если грамматика не имеет циклов
(выводов вида A=>+A) и e-правил (правил вида A->e). Как циклы,
так и e-правила могут быть удалены предварительно.
Получающаяся грамматика без левой рекурсии может иметь e-
правила.
3.2.6. Левая факторизация
Oсновная идея левой факторизации в том, что, когда неясно,
какую из двух альтернатив надо использовать для развертки
нетерминала A, нужно переделать A-правила так, чтобы отложить
решение до тех пор, пока не будет досточно информации, чтобы
принять правильное решение.
Если A->uv1 | uv2 - два A-правила и входная строка
начинается с непустой строки, выводимой из u, мы не знаем,
разворачивать ли по uv1 или по uv2. Однако можно отложить
решение, развернув A->uA'. Тогда после анализа того, что
выводимо из u, можно развернуть A'->v1 или A'->v2.
Левофакторизованные правила принимают вид
A -> u A'
A' -> v1 | v2
Алгоритм 3.6. Левая факторизация грамматики.
Для каждого нетерминала A ищем самый длинный префикс u, общий
для двух или более его альтернатив. Если u#e, т.е. существует
нетривиальный общий префикс, заменяем все A-правила A->uv1 |
uv2 | ... | uvn | z, где z - все альтернативы, не начинающиеся
с u, на
A -> uA' | z
A' -> v1 | v2 | ... | vn
Здесь A' - новый нетерминал. Повторно применяем это
преобразование, пока никакие две альтернативы не будут иметь
общего префикса.
Пример 3.4. Рассмотрим вновь грамматику условных операторов:
St -> if Ex then St
| if Ex then St else St
| Cont
Ex -> ...
После левой факторизации грамматика принимает вид
St -> if Ex then St St'
| Cont
St' -> else St | e
Ex -> ...
К сожалению, грамматика остается неоднозначной, а значит, и не
LL(1), что иллюстрируется рис. 3.8.
St
/ | \
/ | \ St
/ St St' / | \
/ / \\ / | \
/ / \ \ / St St'
/ / \ St' / / | \ \
/ / \ | / / | \ \
if E then if E then S else S if E then if E then S S' else S
а) б)
Рис. 3.8
3.2.7. Рекурсивный спуск
Выше был рассмотрен таблично-управляемый вариант
предсказывающего анализа, когда магазин явно использовался в
процессе работы анализатора. Можно предложить другой вариант
предсказывающего анализатра, когда каждому нетерминалу
сопоставляется, вообще говоря, рекурсивная процедура и магазин
образуется неявно при вызовах этих процедур. Процедуры
рекурсивного спуска могут быть записаны, как это изображено на
рис. 3.9. В процедуре N для случая, когда имеется альтернатива
N->ui->*e (не может быть более одной альтернативы, из которой
выводится e!), приведены два варианта 1.1 и 1.2. В варианте
1.1 делается проверка, принадлежит ли следующий входной символ
FOLLOW(N). Если нет - выдается ошибка. Во втором варианте
этого не делается, так что анализ ошибки откладывается на
процедуру, вызвавшую N.
procedure N;{N -> u1 | u2 | ... | uk}
begin if InSymui)
else error()
end
else
Вариант 1: если имеется правило N->ui =>* e то
Вариант 1.1 : if InSyme)
else error()
end;
Вариант 1.2: exit(N->e)
Вариант 2: нет правила N->ui =>*e
error()
end end;
procedure parse(u);
{из u не выводится e!}
begin v:=u;
while v#e do
{v=Xz}
if X-терминал a
then if InSyma
then return(false)
end
else {X-нетерминал B}
B;
end;
v:=z
end;
return(true)
end;
Рис. 3.9
3.2.8. Диаграммы переходов для рекурсивного спуска
Как правило, непосредственное программирование рекурсивного
спуска из грамматики приводит к большому числу процедур. Число
этих процедур можно уменьшить, заменив в некоторых правилах
рекурсию циклом. Для этого можно воспользоваться диаграммой
переходов грамматики, которая строится следующим образом.
Пусть имеется LL(1)-грамматика. Тогда для каждого
нетерминала построение диаграммы включает следующие шаги.
Шаг 1. Вводим начальное и заключительное состояния.
Шаг 2. Для каждого правила вывода A->X1X2...Xn строим путь
из начального в конечное состояние с дугами, помеченными
X1,...,Xn. Если анализатор, построенный по диаграмме
переходов, оказывается в состоянии s и дуга, помеченная
терминалом a, ведет в состояние t, то если очередной входной
символ равен a, анализатор продвигает вход на одну позицию
вправо и переходит в состояние t. Если же дуга помечена
нетерминалом A, анализатор входит в начальное состояние для A
без продвижения входа. После того как он достигает
заключительного состояния для A, он переходит в состояние t,
что означает "чтение" A из входа при переходе из состояния s в
состояние t. Наконец, если есть дуга из s в t, помеченная e,
то анализатор переходит из s в t, не читая входа.
Если следовать программе рекурсивного спуска, то переход по
e должен всегда выбираться в качестве последней альтернативы.
Диаграммы переходов могут быть упрощены подстановкой одной в
другую. Рассмотрим, например, диаграммы для арифметических
выражений на рис. 3.10.
+---+ T +---+ E'+-----+ +---+ + +---+ T +---+ E'+-----+
E:| 0 |-->| 1 |-->|| 2 ||E':| 3 |-->| 4 |-->| 5 |-->|| 6 ||
+---+ +---+ +-----+ +---+ +---+ +---+ +-----+
| ^
| e |
+------------------------+
+---+ T +---+ E'+-----+ +----+ + +----+ T +----+ E'+----+
E:| 7 |-->| 8 |-->|| 9 ||E':| 10 |-->| 11 |-->| 12 |-->||13||
+---+ +---+ +-----+ +----+ +----+ +----+ +----+
| ^
| e |
+---------------------------+
51
+----+ ( +----+ E +----+ ) +------+
F: | 14 |---->| 15 |---->| 16 |---->|| 17 ||
+----+ +----+ +----+ +------+
| ^
| id |
+---------------------------------+
Рис. 3.10
e
+---------------------+ +---------+
| | | T |
v | v |
+---+ + +---+ T +-----+ +---+ + +---+
E': | 3 |----->| 4 |---->|| 5 || => E':| 3 |---->| 4 |
+---+ +---+ +-----+ +---+ +---+
|e |e
| +-----+ | +-----+
+-------->|| 6 || +----->|| 6 ||
+-----+ +-----+
+-------+ +---------+
| T | | + |
v | v | e
+---+ T +---+ + +---+ +---+ T +---+ +-----+
E: | 0 |-->| 3 |-->| 4 | => E: | 0 |---->| 3 |-->|| 6 ||
+---+ +---+ +---+ +---+ +---+ +-----+
| e +-----+
+--->|| 6 ||
+-----+
Рис. 3.11
+---------+ +---------+
| + | | * |
v | e v | e
+---+ T +---+ +-----+ +---+ F +---+ +------+
E: | 0 |---->| 3 |---->|| 6 || T: | 7 |---->| 8 |--->|| 13 ||
+---+ +---+ +-----+ +---+ +---+ +------+
+----+ ( +----+ E +----+ ) +------+
F: | 14 |---->| 15 |---->| 16 |---->|| 17 ||
+----+ +----+ +----+ +------+
| ^
| e |
+---------------------------------+
Рис. 3.12
На рис 3.11 приведена эквивалентная диаграмма переходов для
E'. Можно подставить диаграмму для E' рис.3.11 в диаграмму для
E рис. 3.10. Получится диаграмма рис. 3.11 для E. Наконец,
видно, что в этой диаграмме нулевая и четвертая вершины
эквивалентны и их можно слить. Так же можно поступить с
диаграммами для T и T'. В результате получится набор диаграмм
рис. 3.12.
Такое преобразование эквивалентно описанию грамматики
расширенными формулами Бэкуса-Наура, в которых помимо
собственно рекурсивных определений допускаются описания
повторений. При программировании рекурсивного спуска такая
диаграмма для E записывается очевидным образом:
procedure E; repeat T; until InSymPLUS;
3.2.9. Восстановление после синтаксических ошибок
В приведенных программах рекурсивного спуска использовалась
процедура реакции на синтаксические ошибки error(). В
простейшем случае эта процедура выдает диагностику и завершает
работу анализатора. Но можно попытаться некоторым разумным
образом продолжить работу. Для разбора сверху вниз можно
предложить следующий простой алгоритм.
Если в момент обнаружения ошибки на верхушке магазина
оказался нетерминальный символ N и для него нет правила,
соответствующего входному символу, то сканируем вход до тех
пор, пока не встретим символ либо из FIRST(N), либо из
FOLLOW(N). В первом случае разворачиваем N по соответствующему
правилу, во втором - удаляем N из магазина.
Если на верхушке магазина терминальный символ, то можно
выкинуть все терминальные символы с верхушки магазина вплоть
до первого (сверху) нетерминального символа и продолжать так,
как это было описано выше.
3.3. Разбор снизу-вверх типа сдвиг-свертка
3.3.1. Основа
В процессе разбора снизу-вверх типа сдвиг-свертка строится
дерево разбора входной строки, начиная с листьев (снизу) к
корню (вверх). Этот процесс можно рассматривать как "свертку"
строки w к начальному символу грамматики. На каждом шаге
свертки подстрока, которую можно сопоставить правой части
некоторого правила вывода, заменяется символом левой части
этого правила вывода, и если на каждом шаге выбирается
правильная подстрока, то в обратном порядке прослеживается
правосторонний вывод (рис. 3.13).
S S S
/ | \
X1 X2...
/ |
.............
/ |
Y Y |
/|\ /|\ Z
/ ... / ... /|\
a.........$ a...........$ a........b.......$
а) б) в)
Рис. 3.13
Пример 3.5. Рассмотрим грамматику арифметических выражений,
приведенную на рис. 3.14 а). Строка а+b*c может быть сведена к
S, как показано на рис. 3.14.б). Дерево этой строки приведено
на рис. 3.14 в).
В строке a+b*c ищется подстрока, которую можно сопоставить с
правой частью некоторого правила вывода. Этому удовлетворяют
подстроки a, b и c. Если выбрать самое левое a и заменить его
на F - левую часть правила F->id, то получим строку F+b*c.
Теперь правой части того же правила можно сопоставить
подстроки b и c. Эти свертки представляют собой в обратном
порядке правосторонний вывод:
E->E+T->E+T*F->E+T*c->E+F*c->E+b*c->T+b*c->F+b*c->a+b*c
--- --- - - - - - -
E -> E + T а+b*c E
E -> T F+b*c /+\
T -> T*F T+b*c E T
T -> F E+b*c | |\
F -> id E+F*c T T F
E+T*c | | \
E+T*F F F id
E+T | | c
E a b
а) б) в)
Рис. 3.14
Подстрока сентенциальной формы, которая может быть
сопоставлена правой части некоторого правила вывода, свертка
по которому к левой части правила соответствует одному шагу в
обращении правостороннего вывода, называется основой строки. В
приведенном выше выводе основы подчеркнуты. Самая левая
подстрока, которая сопоставляется правой части некоторого
правила вывода 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->v в позиции,
следующей за u, это основа строки uvw. Строка w справа от
основы содержит только терминальные символы. Вообще говоря,
грамматика может быть неоднозначной, поэтому не единственным
может быть правосторонний вывод uvw и не единственной может
быть основа. Если грамматика однозначна, то каждая правая
сентенциальная форма грамматики имеет в точности одну основу.
Замена основы в сентенциальной форме на нетерминал левой части
называется отсечением основы. Обращение правостороннего вывода
может быть получено с помощью повторного применения отсечения
основы, начиная с разбираемой строки w. Если w - слово в
рассматриваемой грамматике, то w=Zn, n-я правая сентенциальная
форма еще неизвестного правого вывода
S = Z0 => Z1 => Z2 => ... => Zn-1 => Zn =w.
Чтобы восстановить этот вывод в обратном порядке, выделяем
основу Vn в Zn и заменяем Vn на левую часть некоторого правила
вывода An -> Vn, получая (n-1)-ю правую сентенциальную форму
Zn-1. Затем повторяем этот процесс, т.е. выделяем основу Vn-1
в Zn-1 и сворачиваем эту основу, получая правую сентенциальную
форму Zn-2. Если, повторяя этот процесс, мы получаем правую
сентенциальную форму, состоящую только из начального символа
S, то останавливаемся и сообщаем об успешном завершении
разбора. Обращение последовательности правил, использованных в
свертках, есть правый вывод входной строки.
Таким образом, главная задача анализатора типа сдвиг-свертка
- это выделение и отсечение основы.
3.3.2. LR(k)-анализаторы
В названии LR(k) символ L означает, что разбор осуществляется
слева-направо, R - что строится правый вывод в обратном
порядке, k - число входных символов, на которые заглядывает
вперед анализатор при разборе. Когда k опущено, имеют в виду
1.
LR-анализ привлекателен по нескольким причинам:
- LR-анализ - наиболее мощный метод анализа без возвратов
типа сдвиг-свертка;
- LR-анализ может быть реализован довольно эффективно;
- практически LR-анализаторы могут быть построены для всех
конструкций языков программирования;
- класс грамматик, которые могут быть проанализированы LR-
методом, строго включает класс грамматик, которые могут
быть анализированы предсказывающими анализаторами (сверху
вниз типа LL).
+------------------------------+
Вход | A1 | ... | Ai | ... | An | $ |
+------------------------------+
^
|
+------+ +-------------+ Выход
Магазин | Sm |
|------| | анализатор |
| Xm | +-------------+
|------| |
| Sm-1 | |
|------| +--------+
| Xm-1 | | |
|------| v v
| .... | +---------------+
|------| | action | goto |
| S0 | +---------------+
+------+
Рис. 3.15
Схематически структура LR-анализатора изображена на рис. 3.15.
Он состоит из входа, выхода, магазина, управляющей программы и
таблицы анализа, которая имеет две части - действий и
переходов. Управляющая программа одна и та же для всех
анализаторов, разные анализаторы различаются таблицами
анализа. Программа анализатора читает символы из входного
буфера по одному за шаг. В процессе анализа используется
магазин, в котором хранятся строки вида S0X1S1X2S2...XmSm (Sm
- верхушка магазина). Каждый Xi - символ грамматики
(терминальный или нетерминальный), а Si - символ, называемый
состоянием. Каждый символ состояния выражает информацию,
содержащуюся в магазине ниже него, а комбинация символа
состояния на верхушке магазина и текущего входного символа
используется для индексации таблицы анализа и определяет
решение о сдвиге или свертке. В реализации символы грамматики
не обязательно должны размещаться в магазине. Однако их
использование удобно для упрощения понимания поведения LR-
анализатора.
Таблица анализа состоит из двух частей: действия (action) и
переходов (goto). Начальное состояние этого ДКА - это
состояние, помещенное на верхушку магазина LR-анализатора в
начале работы.
Конфигурация-LR анализатора - это пара, первая компонента
которой - содержимое магазина, а вторая - непросмотренный
вход:
(S0 X1 S1 X2 S2 ... Xm Sm, Ai Ai+1 ... An $)
Эта конфигурация соответствует правой сентенциальной форме
X1 X2 ... Xm Ai Ai+1 ... An
Префиксы правых сентенциальных форм, которые могут появиться в
магазине анализатора, называются активными префиксами.
Активный префикс - это такой префикс правой сентенциальной
формы, который не переходит правую границу основы этой формы.
Очередной шаг анализатора определяется текущим входным
символом Ai и символом состояния на верхушке магазина Sm.
Элемент таблицы действий action[Sm,Ai] для состояния Sm и
входа Ai, может иметь одно их четырех значений:
1) shift S, сдвиг, где S - состояние,
2) reduce A->w, свертка по правилу грамматики A -> w,
3) accept, допуск,
4) error, ошибка.
Конфигурации, получающиеся после каждого из четырех типов
шагов, следующие
1. Если action[Sm,Ai]=shift S, то анализатор выполняет шаг
сдвига, переходя в конфигурацию
(S0 X1 S1 X2 S2 ... Xm Sm Ai S, Ai+1 ... An $)
В магазин помещаются как входной символ Ai, так и следующее
состояние S, определяемое action[Sm,Ai]. Текущим входным
символом становится Ai+1.
2. Если action[Sm,Ai]=reduce A->w, то анализатор выполняет
свертку, переходя в конфигурацию
(S0 X1 S1 X2 S2 ... Xm-r Sm-r A S, Ai Ai+1 ... An $)
где S=goto[Sm-r,A] и r - длина w, правой части правила вывода.
Функция goto таблицы анализа, построенная по грамматике G, -
это функция переходов детерминированного конечного автомата,
распознающего активные префиксы G. Анализатор сначала удаляет
из магазина 2r символов (r символов состояния и r символов
грамматики), так что на верхушке оказывается состояние Sm-r.
Затем анализатор помещает в магазин как A - левую часть
правила вывода, так и S - содержимое таблицы goto[Sm-r,A]. На
шаге свертки текущий входной символ не меняется. Для LR-
анализаторов Xm-r+1 ... Xm - последовательность символов
грамматики, удаляемых из магазина, всегда соответствует w -
правой части правила вывода, по которому делается свертка.
После осуществления шага свертки генерируется выход LR-
анализатора, т.е. исполняются семантические действия,
связанные с правилом, по которому делается свертка, например
печатаются номера правил, по которым делается свертка.
3. Если action[Sm,Ai]=accept, то разбор завершен.
4. Если action[Sm,Ai]=error, анализатор обнаружил ошибку, то
выполняются действия по диагностике и восстановлению.
Ниже приведен алгоритм LR-анализа. Все LR-анализаторы ведут
себя одинаково. Разница между ними заключается в различном
содержании таблиц действий и переходов.
Алгоритм 3.7. Алгоритм LR-анализа.
loop Пусть S - состояние на верхушке магазина;
if action[S,InSym]=shift S'
then поместить InSym и затем S'
на верхушку магазина;
прочитать в InSym следующий
входной символ
else if action[S,InSym]=reduce N->w
then удалить из магазина
2*|w| символов;
пусть теперь на верхушке магазина
состояние S';
поместить на верхушку магазина N, а
затем состояние goto[S',InSym];
вывести правило N->w
else if action[S,InSym]=accept
then return
else error()
end end end end;
Вначале в магазине помещено начальное состояние S0, а в буфере
w$, InSym содержит первый символ w$; Анализатор выполняет
приведенную ниже программу до тех пор, пока будет достигнуто
либо состояние accept, либо состояние error.
+--------------------------------------+
|Состо-| action | goto |
| яния |------------------+------------|
| | id + * $ | E T F |
|------+------------------+------------|
| 0 | S6 | 1 2 3 |
| 1 | S4 acc | |
| 2 | R2 S7 R2 | |
| 3 | R4 R4 R4 | |
| 4 | S6 | 5 3 |
| 5 | R1 S7 R1 | |
| 6 | R5 R5 R5 | |
| 7 | S6 | 8 |
| 8 | R3 R3 R3 | |
+--------------------------------------+
Рис. 3.16
Пример 3.6. На рис. 3.16 изображены функции action и goto LR-
таблиц для грамматики арифметических выражений с бинарными
операциями + и * примера 3.5. Здесь Si означает сдвиг и
помещение в магазин состояния i, Rj - свертку по правилу номер
j, acc - допуск, пустая клетка - ошибку.
Значение goto[S,A] для терминала A ищется в поле действия,
связанном с действием сдвига по входу A в состоянии S. Поле
перехода дает goto[S,A] для нетерминалов A.
На входе id+id*id последовательность состояний магазина и
входа показаны на рис. 3.17. Например, в первой строке LR-
анализатор находится в нулевом состоянии и читает первый
входной символ id. Действие S6 в нулевой строке и столбце id в
поле action рис. 3.17 означает сдвиг и помещение S6 на
верхушку магазина. Это и изображено во второй строке: первый
символ id и символ состояния S6 помещаются в магазин и id
удаляется из входной строки.
Текущим входным символом становится +, и действием в
состоянии 6 на вход + является свертка по F->id. Из магазина
удаляются два символа (один символ состояния и один символ
грамматики). Теперь анализируется нулевое состояние Поскольку
goto в нулевом состоянии по символу F - это 3, F и 3
помещаются в магазин. Теперь имеем конфигурацию,
соответствующую третьей строке. Остальные шаги определяются
аналогично.
+---------------------------------------------------------+
|Активный| Магазин | Вход | Действие|
|префикс | | | |
|--------+-----------------------+--------------+---------|
| |0 |id + id * id $| сдвиг |
| id |0 id 6 | + id * id $| F -> id |
| F |0 F 3 | + id * id $| T -> F |
| T |0 T 2 | + id * id $| E -> T |
| E |0 E 1 | + id * id $| сдвиг |
| E+ |0 E 1 + 4 | id * id $| сдвиг |
| E+id |0 E 1 + 4 id 6 | * id $| F -> id |
| E+F |0 E 1 + 4 F 3 | * id $| T -> F |
| E+T |0 E 1 + 4 T 5 | id $| сдвиг |
| E+T* |0 E 1 + 4 T 5 * 7 | id $| сдвиг |
| E+T*id |0 E 1 + 4 T 5 * 7 id 6 | $| F -> id |
| E+T*F |0 E 1 + 4 T 5 * 7 F 8 | $| T -> T*F|
| E+T |0 E 1 + 4 T 5 | $| E -> E+T|
| E |0 E 1 | | допуск |
+---------------------------------------------------------+
Рис. 3.17
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 - последнее правило, использованное в правом выводе
цепочки uvw, то правило 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).
S
/|\
/ | \
/ A \
/ /\ \
/ / \ \
y u v a...
---- ----
z w
Рис. 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.
function closure(I);/*I - множество ситуаций*/
begin repeat для каждой ситуации [A->u.Bv,a] из I,
каждого правила вывода B->w из G' и каждого
терминала b из FIRST(va), такого, что [B->.w,b]
нет в I
do добавить [B->.w,b] к I;
until к I нельзя добавить новых ситуаций;
return I;
end;
В анализаторах типа LR(0) при построении closure не
учитываются терминалы из FIRST(va).
Если I - множество ситуаций, допустимых для некоторого
активного префикса z, то goto(I,X) - множество ситуаций,
допустимых для активного префикса zX.
function goto(I,X);/*I - множество ситуаций;
X - символ грамматики*/
begin Пусть [A->u.Xv,a] принадлежит I;
Рассмотрим J - множество ситуаций [A-uX.v,a];
return closure(J)
end;
Работа алгоритма построения множества LR(1)-ситуаций
начинается с того, что берется C - множество ситуаций
{closure({[S'->.S,$]})}. Затем из имеющегося множества с
помощью операции goto() строятся новые множества ситуаций. По-
существу, goto(I,X) - переход конечного автомата из состояния
I по символу X.
procedure items(G'); begin C:={closure({[S'->.S,$]})};
repeat для каждого множества ситуаций I из C
и каждого символа грамматики X
такого, что goto(I,X) не пусто
и не принадлежит C
do добавить goto(I,X) к C
until к C нельзя больше добавить множеств ситуаций end;
Пример 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.
В каждый момент анализа в магазине находится активный
префикс, который соответствует последовательности переходов из
начального состояния (I0) в текущее. Свертка - это замена
суффикса префикса и переход в новое состояние, т.е. как бы
возврат по части пути, соответствующей основе, и замена этой
части переходом, соответствующим левой части.
Рассмотрим теперь, как по множеству LR(1)-ситуаций строятся
функции действия и переходов LR(1)-анализатора. Функции
действия и переходов представляются таблицей.
+-------------+ E +-------------+ + +-------------+
| I0 |--->| I1 |--->| I4 |
| E'-> .E, $ | | E'-> E., $ | | E -> E+.T,$ |
| E -> .E+T,$ | | E -> E.+T,$ | | E -> E+.T,+ |
| E -> .T, $ | | E -> E.+T,+ | | T -> .T*F,$ |
| T -> .T*F,$ | +-------------+ | T -> .F, $ |
| T -> .F, $ | T +-------------+ | T -> .T*F,+ |
| F -> .id, $ |--->| I2 | | T -> .F, + |
| E -> .E+T,+ | | E -> T., $ | | F -> .id, $ |
| E -> .T, + | | T -> T.*F,$ | | F -> .id, + |
| T -> .T*F,+ | | E -> T., + | | T -> .T*F,* |
| T -> .F, + | | T -> T.*F,+ | | T -> .F, * |
| T -> .T*F,* | | T -> T.*F,* | | F -> .id, * |
| T -> .F, * | +-------------+ +-------------+
| F -> .id, * | | F| | |
| F -> .id, + |-------+---+ +-------------+ | |
+-------------+ | F | | T | | id
| +-------------+ | | | +------+
+-+ | * | | | |
| v v v v |
| +-------------+ +-----------+ +-------------+ |
| | I7 | | I3 | | I5 | |
| | T -> T*.F,$ | | T -> F.,$ | | E -> E+T.,$ | |
| | T -> T*.F,+ | | T -> F.,+ | | E -> E+T.,+ | |
| | T -> T*.F,* | | T -> F.,* | | T -> T.*F,$ | |
| | F -> .id, $ | +-----------+ * | T -> T.*F,+ | |
| | F -> .id, + | T.*F,* | |
| | F -> .id,* | id +-------------+ |
| +-------------+ +----+
| | F | id |
| id | +---------------------------------+ |
+------+----------------------------------+ | |
| | | |
v v v v
+-------------+ F +------------+
| I8 | | I6 |
| T -> T*F.,$ | | F -> id.,+ |
| T -> T*F.,+ | | F -> id.,* |
| T -> T*F.,* | | F -> id.,$ |
+-------------+ +------------+
Рис. 3.19
Алгоритм 3.9. Построение канонических таблиц LR анализатора.
Шаг1. Строим набор множеств LR(1)- ситуаций C={I0,I1,...,In}
для G'.
Шаг 2. Состояние i анализатора строится из Ii. Действия
анализатора для состояния i определяются следующим
образом:
а) если [A->u.av,b] принадлежит Ii и goto(Ii,a)=Ij, то
полагаем action[i,a]="shift j". Здесь a - терминал;
б) если [A->u.,a] принадлежит Ii, A#S', то полагаем
action[i,a]="reduce A->u";
в) если [S'->S.,$] принадлежит Ii, полагаем
action[i,$]="accept".
Шаг 3. Переходы для состояния i определяются следующим
образом: если goto(Ii,A)=Ij, то 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:
St -> if Ex then St
| if Ex then St else St
| ...
Если анализатор типа сдвиг-свертка находится в конфигурации
Магазин Вход
... if Ex then St 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.
При более детальной проработке реакции на ошибки можно в
каждой пустой клетке анализатора поставить обращение к своей
подпрограмме. Такая подпрограмма может вставлять или удалять
входные символы или символы магазина, менять порядок входных
символов.