|
Лекции по конструированию компиляторов - Часть 4
Автор: В.А.Серебряков Глава 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) каждый лист помечен либо a<-T, либо e;
(3) каждая внутренняя вершина помечена нетерминалом;
(4) если N - нетерминал, которым помечена внутренняя вершина
и X1,...,Xn - метки ее прямых потомков в указанном
порядке, то N->X1...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) q0<-Q - начальное состояние управляющего устройства;
(6) Z0<-Г - символ, находящийся в магазине в начальный
момент (начальный символ);
(7) F<=Q - множество заключительных состояний
Конфигурацией МП-автомата называется тройка (q,w,u)<-QxT*xГ*,
где
(1) q - текущее состояние управляющего устройства;
(2) w - неиспользованная часть входной цепочки; первый
символ цепочки w находится под входной головкой; если w
e, то считается, что вся входная лента прочитана;
(3) u - содержимое магазина; самый левый символ цепочки u
считается верхним символом магазина; если u=e, то магазин
считается пустым.
Такт работы МП-автомата P будем представлять в виде бинарного
отношения |-, определенного на конфигурациях. Будем писать
(q,aw,Zu)|-(q',w,vu)
если множество d(q,a,Z) содержит (q',v), где q, q'<-Q, a<-T U
{e}, w<-T*, Z<-Г, u,v<-Г*.
Начальной конфигурацией МП-автомата P называется конфигурация вида (q0,w,Z0), где w<-T*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в магазине есть только начальный символ Z0. Заключительная конфигурация - это конфигурация вида (q,e,u), где q<-F, u<-Г*. Говорят, что цепочка w допускается МП-автоматом P, если (q0,w,Z0)|-*(q,e,u) для некоторых q<-F и u<-Г*. Языком, определяемым (или допускаемым) автоматом P (обозначается L(P)), называют множество цепочек, допускаемых автоматом P. Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом P, если (q0,w,Z0)|-*(q,e,e). Эти определения эквивалентны. 3.2. Таблично-управляемый предсказывающий разбор 3.2.1. Алгоритм разбора сверху-вниз Основная проблема предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора (сверху-вниз) с точки зрения построения дерева разбора можно проиллюстрировать рис. 3.1. Фрагменты недостроенного дерева соответствуют сентенциальным формам вывода. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входного потока предсказывающий анализатор должен определить правило S->X1 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<-FIRST(Yi) и e принадлежит всем FIRST(Y1),...,FIRST(Yi-1), т.е. Y1...Yi-1=>*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), если e<-FIRST(X1),не e символы из FIRST(X3), если e принадлежит как FIRST(X1), так и FIRST(X2), и т.д. Наконец, добавим e к FIRST(X1X2...Xn), если e<-FIRST(Xi) для всех 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<-FIRTS(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 =>* 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 InSym<-FIRST(ui) {только одному!}
then if parse(ui)
then exit(N->ui)
else error()
end
else
Вариант 1: если имеется правило N->ui =>* e то
Вариант 1.1 : if InSym<-FOLLOW(N)
then exit(N->e)
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 InSym<>a
then return(false)
end
else {X-нетерминал B}
B;
end;
v:=z
end;
return(true)
end;
Рис. 3.9
|
Автор проекта: USU Software
Вы можете выкупить этот проект.