Методы построения LL(1)-грамматики
Выбери формат для чтения
Статья: Методы построения LL(1)-грамматики
Загружаем конспект в формате doc
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
25. Методы построения LL(1)-грамматики
При построении синтаксического анализатора требуется определить компилируемый язык с помощью какой-то грамматики, допускающей детерминированный LL- или LR-разбор. Наиболее популярным считается нахождение LL(1)-грамматики, хотя это один из самых слабых методов. Однако мы ограничиваемся только им. Главная проблема, возникающая при этом – преобразование КС-грамматики, которая без особого труда находится по языку, в эквивалентную LL(1)-грамматику. Дело в том, что естественный перевод в форму Бэкуса-Наура обычно содержит особенности, в зародыше противоречащие условиям LL(1)-грамматики. Поэтому сначала требуется обсудить некоторые способы, помогающие (но не гарантирующие) перевод грамматики в нужную нам форму.
Пусть имеется КС-грамматика G=. Считаем, что в G нет бесполезных нетерминалов.
1. Левая факторизация. Речь идет о наиболее простом в распознавании и устранении признаке, который противоречит условиям LL(1)-грамматики. Допустим, что среди правил имеется два правила вида A ,A , где , T N, причем цепочка непустая. Обычно в такой ситуации First(). И тогда G не является LL(1)-грамматикой по той простой причине, что элементы First() входят как в Route(A) так и в Route(A). Чтобы устранить эту проблему, надо ввести в грамматику новый нетерминал (допустим B), обозначающий или , и правила
A , A
заменить на
AB, B| .
Естественно, слово надо подбирать максимально длинным – так, чтобы и не начинались с одной и той же буквы.
В общей ситуации метод левой факторизации заключается в поиске максимальных наборов правил вида
A1 , A2 ,…, An
где - непустая и все 1 ,2 ,…,n начинаются с разных букв. Вводится новый нетерминал B и указанные правила заменяются на
AB, B1 , B2 ,…, Bn
Процедура повторяется столько раз, сколько это возможно.
2. Устранение левой рекурсии.
Теорема 1. Если в КС-грамматике G для некоторых нетерминала AT и цепочки T N* выводимо AA, то G не является LL(1)-грамматикой.
( означает выводимость не менее, чем за одно применение правил грамматики)
Доказательство. Т.к. нетерминал A не является бесполезным, в грамматике возможен вывод какой-нибудь терминальной цепочки с участием фрагментов AA и AA. Пусть это
S* 1A21A2 1A2* .
Можно считать, что это левосторонний вывод и, в частности, 1 – терминальная цепочка. Значит = 11. Если 1 пустая, то налицо неоднозначность грамматики, чего не может быть в LL(1). Если 1 не пустая и начинается, с терминала a, то этот терминал и разбираемый нетерминал однозначно определяют применяемое правило. Отсюда последовательность шагов в 1A21A2 точно такая же, как в 1A2 1A2 и должна повторяться до бесконечности. Противоречие.
Грамматика, у которой имеется выводимость AA из формулировки теоремы, называется леворекурсивной. Оказывается, что все такие левые рекурсии можно легко устранить и тем самым сделать попытку преобразовать данную грамматику в эквивалентную LL(1)-грамматику.
В наиболее часто встречающейся ситуации левая рекурсия попадается в виде наличия продукций вида
AA |.
Здесь не совпадает с A. Наличие хотя бы одной такой альтернативы неизбежно. Иначе нетерминал A станет непродутивным. Указанную парочку теперь можно заменить на
AU, UU |,
где U – новый нетерминальный символ. Это не изменит языка грамматики. Более общая ситуация
Теорема 2. Пусть AA1|A2|…|Am|1|2|…|n все продукции грамматики с левым нетерминалом A; т,n1. Cлова 1, 2, …, n не начинаются с A. Если заменить в грамматике эти продукции на
A1U |2U |…|nU, U1U |2U |…|mU |
где U – новый нетерминал, то язык грамматики не изменится.
Доказательство. Рассмотрим вывод в прежней грамматике какой-нибудь сентенции. Допустим, что в выводе используется нетерминал A. Продукции Aj выводятся из новых правил. Допустим, что вывод использует продукции AAi. Рассмотрим последнее применение такого правила. Тогда следующее правило с данным вхождением нетерминала A имеет вид Aj. Вот фрагмент вывода
S …__ A____Ai__ …A j …
который, используя новые продукции, переделаем в.
S …__ A____jU ____jiU ____ji __ …j …
Аналогично избавляемся от остальных применений старых правил.
Обратно, пусть некоторая терминальная цепочка лежит в новой грамматике. Найдем в ее выводе первое применение правила вида AjU. Проследим вывод от этого места до момента исчезновения U с помощью правила U.
S …__ A____jU __ …
__U __ __iU __ …
__U ____kU __ …
…
__U ____tU __ …
__U __ …
Указанный фрагмент переделывается:
S …__ A____At __…__Aik…t ____jik…t __ …
__ik…t __ …
__k…t __ …
…
__t __ …
…
Аналогично заменяются остальные применения новых правил. Теорема доказана.
С помощью этой теоремы можно убрать из грамматики любую прямую левую рекурсию, т.е. избавиться от правил вида AA.. Именно, при наличии такой продукции мы заменяем это правило согласно конструкции в теореме за одним только возможным исключением: продукции вида UU не добавляем. Для того, чтобы избавиться от выводимостей вида AA, приходится иногда действовать тоньше.
Во-первых, договоримся, что правил вида AA в грамматике нет. Это, в частности означает, что при применении конструкции теоремы 2 слова 1,2,…,m всегда непустые.
Во-вторых, заметим, что если конструкция теоремы применяется к правилу AA, а -правило Aотсутствует (т.е. 1,2,…,n непустые), то новый нетерминал U никогда не станет началом правой части какой-либо продукции.
В общем случае алгоритм избавления от левой рекурсии состоит в следующем.
Продукции, левая часть которых есть нетерминал A, называем A-продукциями.
Шаг 0. Избавимся от -правил и далее считаем, что в исходной грамматике их нет.
Шаг 1. Избавимся от всех прямых левых рекурсий. (При этом могут появиться -правила)
Шаг 2. Расположим все нетерминалы грамматики в некотором порядке. Пусть их список есть A1, A2,…, Ak.
Шаг 3. Цикл
for A := A1 to Ak do
begin
for B := A1 to A-1 do
begin
Каждое правило грамматики вида AB заменим на
A1|2|…|n,
если B1|2|…|n – все B-продукции
end
Прямые левые рекурсии вида AA устраним как в теореме 2:
Продукции AA1|A2|…|Am|1|2|…|n
заменяем на A1U |2U |…|nU, U1U |2U |…|mU |
для нового нетерминала U
end
Докажем корректность алгоритма. Заметим, что при выполнении шагов 1 и 3 к грамматике все время добавляются новые нетерминалы. Далее их так и называем – новые. А те, что были в исходной грамматике – старые.
Заметим, что на шагах 3 и 4 работа все время идет со старыми нетерминалами A, B. Когда на шаге 3 выкинется продукция AB с A > B, у нас получится:
• либо количество правил вида AB уменьшится;
• либо очередное минимальное правило будет строго больше, чем AB. Это следует из того, что вместо правила AB может появиться, например, AC при BC. Но т.к. B B и все оставшиеся правила вида ACили BC больше, чем AB.
Таким образом в навой грамматике невозможно вывести AA так, что первыми нетерминалами слов вывода являются старые нетерминалы.
26. Программирование синтаксического анализатора
Рассмотрим для примера фрагмент языка Бейсик. Это конструкция из вложенных циклов следующего вида
For Id = C To Id
...
For Id = C To Id
statement: .. :statement
...
statement: .. :statement
Next Id
...
Next Id
Здесь Id – идентификаторы, C – константы, statement – простые операторы вида Id = Выражение, а Выражения построены из констант и идентификаторов с помощью операций сложения, умножения и вычитания.
Описываем указанный фрагмент на языке Бэкуса-Наура.
<Цикл> ::= For Id = C to Id r <Цикл> r Next Id
<Цикл> ::= For Id = C to Id r <Строки Операторов> Next Id
<Строки Операторов> ::=<Строка Операторов><Строки Операторов>|<Строка Операторов>
<Строка Операторов> ::= <Операторы> r
<Операторы> ::= <Оператор>|<Оператор>:<Операторы>
<Оператор> ::= Id = <Выражение>
<Элементарное выражение> ::= Id|C
<Терм> ::= <Элементарное выражение>|( <Выражение> )
<Произведение>::= <Терм>|<Терм>*<Произведение>
<Выражение> ::= <Произведение> | <Произведение> + <Выражение>|<Произведение> - <Выражение>
Сделаем некоторые пояснения.
1. Нетерминал r обозначает перевод строки. Для Бейсика он выступает как важный разделитель и должен вычленяться на этапе лексического анализа.
2. Все идентификаторы и константы также вычисляются на этапе лексического анализа, а сейчас считаются одинаковыми терминалами. Для построения дерева разбора совершенно не нужно прослеживать, какие из них совпадают, какие – нет. Но в реальном трансляторе о каждом идентификаторе или константе информация должна полностью сохраняться и использоваться в семантическом анализе (следующем этапе компиляции). Таким образом приводимая ниже программа, хотя и будет выполнять конкретную работу, все же должна пониматься как некий скелет, в который при необходимости надо добавлять необходимые функции.
Составляем список терминалов и нетерминалов. Для краткости присваиваем им обозначения привычным манером – малыми и большими латинскими буквами.
<Цикл> S
<Выражение> A
<Строки Операторов> C
<Строка Операторов> B
<Операторы> D
<Оператор> E
<Элементарное выражение> F
<Терм> T
<Произведение> M
For f
Id i
= e
to t
r r
Next n
: d
C c
( l
) p
* z
+ a
- m
Получаем грамматику
S fiectArSrni
S fiectArCni
C BC | B
B Dr
D E | EdD
E ieA
F i | c
T F| lAp
M T | TzM
A M | MaA | MmA
Грамматике явно требуется факторизация. После этого получим
S fiectArG
G Srni|Cni
C BH
H C|
B Dr
D EK
K dD|
E ieA
F i|c
T F|lAp
M TN
N zM|
A ML
L aA|mA|
First(A)
First()/
Follow(A)
Route(A)
S fiectArG
f
f
r
f
G Srni|Cni
f ,i
f | i
r
f | i
C BH
i
i
n
i
H C|
i
i | -
n
i | n,
B Dr
i
i
i,n
i
D EK
i
i
r
i
K dD|
d
d | -
r
d | r,
E ieA
i
i
d,r
i
F i|c
i,c
i | c
z
i | c
T F | lAp
l,i,c
i,c | l
z
i,c | l
M TN
l,i,c
l,i,c
a,m
l,i,c
N zM|
z
z | -
a,m
z | a,m,
A ML
l,i,c
l,i,c
t,r,d,p
l,i,c
L aA|mA|
a,m
a,m
t,r,d,p
a | m | t,r,d,p,
Прежде, чем приступать непосредственно к программированию, надо решить, в каком виде программа будет принимать исходные данные и что выдаст на выходе.
Исходными данными, понятно, является текстовый файл с фрагментом программы на языке Бейсик выбранного нами вида.
Сначала этот исходный текст подвергается лексическому анализу. Результатом лексического анализа должно быть или сообщение об ошибке или последовательность лексем вместе с соответствующими таблицами.
Будем считать, что каждая лексема есть пара чисел: , где t – тип лексемы согласно списка:
1. Служебные (ключевые) слова языка.
2. Арифметические, логические и прочие операции, отношения, присваивание.
3. Специальные символы (точка, точка с запятой, двоеточие, скобки и т.д.)
4. Идентификаторы.
5. Числовые константы.
n – номер лексемы в соответствующем типе.
В памяти лексема может представляется какой-то структурой tLex (допустим, из двух чисел). Список лексем есть массив Lex[]. После лексического анализа программа должна выдать этот массив и таблицы лексического анализа в текстовый файл.
Lex[] есть входная цепочка терминалов, которую на втором этапе должен распознать блок синтаксического анализа. В этом массиве могут присутствовать разные идентификаторы и разные константы. Напомним, что на этапе синтаксического анализа все константы отождествляются между собой и обозначаются единым символом c. Также все идентификаторы – это единый терминал i.
Единый список терминалов: f,i,e,t,r,n,d,c,l,p,z,a,m. Таблицы лексического анализа должны показать связь между ними и парами .
Список нетерминалов есть S,G,C,H,B,D,K,E,F,T,M,N,A,L. Он определяется на этапе построения грамматики. Ниже приведен основной модуль (каким он может быть). Этот модуль имитирует работу стекового автомата, который можно построить по последней таблице (ее первому и последнему столбцам). Пример такой таблицы приводился в предыдущем параграфе. На самом деле она нам не нужна. По той причине, что в ней нет принципиально новой информации по сравнению со списком продукций и столбиком направляющих символов.
enum tSymb { S,G,C,H,B,D,K,E,F,T,M,N,A,L,Nabla,
f,i,e,t,r,n,d,c,l,p,z,a,m,epsilon};
void PutInSteck(tSymb V,... ); //Кладет в стек все пераметры, начиная с первого
void ReplaceInSteck(tSymb V,... ); //заменяет в стеке верхний V остальными параметрами
tSymb TopSteck(); //Возвращает верхний символ стека
tSymb InputSymb(); //Возвращает текущий входной терминал или epsilon
void ToNextSymb(); //Перемещает указатель на следующую позицию
char *SteckToStr(); //Записывает содержимое стека в виде строки в
//каком-то буфере и возвращает на него указатель.
char *InputToStr(); //Записывает содержимое не считанной части ленты
//в виде строки в каком-то буфере и возвращает
//на него указатель.
char *CommandToStr(tSymb V,... ); //Записывает команду V->... в виде строки
//в каком-то буфере и возвращает на него указатель.
// Основной модуль
int Sintax(FILE *ou) // ou – указатель на открытый файл
{
int Err=-1;
tSymb V;
tSymb x;
fprintf(ou,"%-40s | %40s | ",SteckToStr(),InputToStr());
PutInSteck(Nabla, S);
do
{
fprintf(ou,"%-40s | %40s | ",SteckToStr(),InputToStr());
V = TopSteck();
x = InputSymb();
if((V==Nabla)&&(x==epsilon)) return 0;
if((x>Nabla)&&(x \r\n");
continue;
}
switch(V)
{
case S:
switch(x)
{
case f: ReplaceInSteck(V,G,r,t,A,e,i,f);//fieAtArG из первой строки таблицы
fprintf(ou," %s\r\n",CommandToStr(V,G,r,t,A,e,i,f));
break;
default: return Err;
}
break;
case G:
switch(x)
{
case f: ReplaceInSteck(V,i,n,i,S); //Srni из второй строки таблицы
fprintf(ou," %s\r\n",CommandToStr(V,i,n,i,S));
break;
case i: ReplaceInSteck(V,i,n,C); //Cni из второй строки таблицы
fprintf(ou," %s\r\n",CommandToStr(V,i,n,C));
break;
default: return Err;
}
break;
case C:
switch(x)
{
case f: ReplaceInSteck(V,H,B); //C -> BH
fprintf(ou," %s\r\n",CommandToStr(V,H,B));
break;
default: return Err;
}
break;
case H:
switch(x)
{
case i: ReplaceInSteck(V,C); //H -> C
fprintf(ou," %s\r\n",CommandToStr(V,C));
break;
case n: //H -> э
case epsilon:ReplaceInSteck(V,epsilon);
fprintf(ou," %s\r\n",CommandToStr(V,epsilon));
break;
default: return Err;
}
break;
case B:
switch(x)
{
case i: ReplaceInSteck(V,r,D); //B -> Dr
fprintf(ou," %s\r\n",CommandToStr(V,r,D));
break;
default: return Err;
}
break;
case D:
switch(x)
{
case i: ReplaceInSteck(V,K,E); //D -> EK
fprintf(ou," %s\r\n",CommandToStr(V,K,E));
break;
default: return Err;
}
break;
case K:
switch(x)
{
case d: ReplaceInSteck(V,D,d); //K -> dD
fprintf(ou," %s\r\n",CommandToStr(V,D,d));
break;
case r: //K -> э
case epsilon:ReplaceInSteck(V,epsilon);
fprintf(ou," %s\r\n",CommandToStr(V,epsilon));
break;
default: return Err;
}
break;
case E:
switch(x)
{
case i: ReplaceInSteck(V,A,e,i); //E -> ieA
fprintf(ou," %s\r\n",CommandToStr(V,A,e,i));
break;
default: return Err;
}
break;
case F:
switch(x)
{
case i: ReplaceInSteck(V,i); //F -> i
fprintf(ou," %s\r\n",CommandToStr(V,i));
break;
case c: ReplaceInSteck(V,c); //F -> c
fprintf(ou," %s\r\n",CommandToStr(V,c));
break;
default: return Err;
}
break;
case T:
switch(x)
{
case i:
case c: ReplaceInSteck(V,F); //T -> F
fprintf(ou," %s\r\n",CommandToStr(V,F));
break;
case l: ReplaceInSteck(V,p,A,l); //T -> lAp
fprintf(ou," %s\r\n",CommandToStr(V,p,A,l));
break;
default: return Err;
}
break;
case M:
switch(x)
{
case l:
case i:
case c: ReplaceInSteck(V,N,T); //M -> TN
fprintf(ou," %s\r\n",CommandToStr(V,N,T));
break;
default: return Err;
}
break;
case N:
switch(x)
{
case z: ReplaceInSteck(V,M,z); //N -> zM
fprintf(ou," %s\r\n",CommandToStr(V,M,z));
break;
case a:
case m:
case epsilon:ReplaceInSteck(V,epsilon);
fprintf(ou," %s\r\n",CommandToStr(V,epsilon));
break;
default: return Err;
}
break;
case A:
switch(x)
{
case l:
case i:
case c: ReplaceInSteck(V,L,M); //A -> ML
fprintf(ou," %s\r\n",CommandToStr(V,L,M));
break;
default: return Err;
}
break;
case L:
switch(x)
{
case a: ReplaceInSteck(V,A,a); //L -> aA
fprintf(ou," %s\r\n",CommandToStr(V,A,a));
break;
case m: ReplaceInSteck(V,A,m); //L -> mA
fprintf(ou," %s\r\n",CommandToStr(V,A,m));
break;
case t:
case r:
case d:
case p:
case epsilon: //L -> э
ReplaceInSteck(V,epsilon);
break;
default: return Err;
}
break;
default: return Err;
}
} while(true);
}
