CodeNet / Приложения / Алгоритмы / Разбор выражений. Компиляторы и интерпретаторы. / Основы компиляции
КС-языки и грамматики.
LL(k)-грамматики. Простейший LL(1)-компилятор.
Контекстно-свободные языки
Класс контекстно-свободных языков допускает распознавание с
помощью недетерминированного КА со стековой (или магазинной)
памятью.
Контекстно-зависимые языки - последний класс языков, которые
можно эффективно распознать с помощью ЭВМ. Специалисты скажут,
что они допускаются двусторонними недетерминированными линейно
ограниченными автоматами. Для допуска цепочек языка без ограни-
чений в общем случае требуется универсальный вычислитель (маши-
на Тьюринга, машина с неограниченным числом регистров и т.п.).
Контекстно-зависимые языки и языки без ограничений не использу-
ются при построении компиляторов и в дальнейшем рассматриваться
не будут.
Автомат со стековой памятью в отличие от обычного КА имеет
стек, в который можно помещать специальные т.н. "магазинные"
символы. Переход из одного состояния в другое зависит не только
от входного символа, но и от верхних символов магазина (на ри-
сунке в круглых скобках). В начале работы в магазине лежит спе-
циальный символ S.
При выполнении перехода из магазина удаляются верхние симво-
лы, соответствующие правилу, и добавляется цепочка символов,
соответствующих переходу (на рисунке изображены в квадратных
скобках, первый символ цепочки становится верхним символом ма-
газина). Допускаются также переходы, при которых входной символ
игнорируется (и, тем самым, будет входным символом при следу-
ющем переходе). Эти переходы называются e-переходами. Автомат
называется недетерминированным, если при одних и тех же состо-
янии, входном символе и вершине магазина возможен более чем
один переход. Если при окончании цепочки автомат находится в
одном из конечных состояний, а стек пуст, цепочка считается до-
пущенной (после окончания цепочки могут быть сделаны e-перехо-
ды).
-------¬0(S) ------¬1(0) -T---T¬
¦Начало+---->+ 1 +---->+¦ 2 ¦¦
L-------[0] LT---T- [] L+---+-
L-<-- L-<--
0(0)[00] 1(0)[]
Какие цепочки допускает этот автомат? - упражнение.
По контекстно-свободной грамматике легко строится недетерми-
нированный КА с магазинной памятью, который допускает цепочки
этого языка. Он использует только одно состояние и следующий
набор переходов:
e(A)[x] для каждого правила грамматики A:x
а(а)[] для каждого терминала а
Можно построить и другой автомат, который также содержит од-
но состояние и имеет следующие переходы:
а(е)[а] для каждого терминала а
е(x)[A] для каждого правила грамматики A:x
Удобно считать, что в начале разбора магазин этого автомата
пуст. Тогда в конце разбора в магазине останется символ S. Ка-
кие (правые или левые) выводы делают (для однозначной граммати-
ки) только что построенные автоматы? - упражнение.
По недетерминированному КА с магазинной памятью можно
построить КС-грамматику (упражнение). Таким образом класс
КС-языков и класс языков, допускаемых автоматами с магазинной
памятью, эквивалентны.
К сожалению, не каждый КС-язык допускает разбор с помощью
детерминированного автомата. Например, язык цепочек-палиндромов
из 0 и 1 не может быть допущен детерминированным КА с магазин-
ной памятью (как выглядит недетерминированный автомат, допуска-
ющий этот язык? - упражнение). Таким образом, недетерминирован-
ные автоматы со стеком могут распознавать более широкий класс
языков, чем детерминированные автоматы со стеком - в этом их
существенное отличие от КА. Практический интерес для реализации
компиляторов представляют детерминированные КС-языки -
собственное подмножество КС-языков, допускающее распознавание с
помощью детерминированных автоматов с магазинной памятью.
Два (недетерминированных) автомата, построенных выше для
КС-грамматики определяют два класса методов разбора КС-языков:
сверху-вниз снизу вверх.
В первом случае (пример - рекурсивный спуск) при просмотре
цепочки слева направо естественно будут получаться левые выво-
ды. При детерминированном разборе проблема будет состоять в
том, какое правило применить для раскрытия самого левого нетер-
минала.
Во втором случае детерминированный разбор удобно формализо-
вать в терминах "сдвиг" (перенос символа из входной цепочки в
магазин) и "свертка" (применение к вершине магазина какого-либо
правила грамматики). При просмотре входной цепочки слева напра-
во при этом будут получаться правые выводы. Проблема в этом
случае состоит в выборе между сдвигом и сверткой и в выборе
правила для свертки. Следующие лекции будут посвящены практи-
ческим методам разбора детерминированных КС-языков сверху вниз
и снизу-вверх.
Лемма о разрастании для КС-языков
Для каждого КС-языка существует такое число m, что любую
принадлежащую языку цепочку z : |z|>m можно разбить на 5 частей
n n
z = uvwxy : |vx| > 0, |vwx|<=m и цепочки вида uv wx y, n>=0
также принадлежат языку.
Доказательство: Пусть КС-грамматика языка содержит q нетер-
миналов, а самая длинная цепочка в правой части правил имеет
длину k. Рассмотрим дерево вывода для цепочки длины k**(2*q+3)
и оставим в нем только те ветвления, которые ведут к терминаль-
ным листьям (игнорируем e-правила). Утверждение: Существует
маршрут от корня до кроны, который имеет по крайней мере q+2
левых (или q+2 правых) ветвления (упражнение). Если все вершины
дерева пометить раскрытыми нетерминалами, то по крайней мере
один из них (например, A) встретится на этом маршруте два раза
(упражнение). При это крона дерева естественным образом разобь-
ется на 5 частей: S
/ ¦ \
/ A \
/ / ¦ \ \
/ / A \ \
/ / / \ \ \
--------------
u v w x y
Это и будет искомое разбиение цепочки, так как uvwxy будут
удовлетворять требованиям леммы (упражнение).
n n n
Упражнение: показать, что язык 0 1 2 не является контек-
стно-свободным.
Преобразование КС-грамматик.
Проблема эквивалентности двух языков, описываемых различными
КС-грамматиками, в общем случае неразрешима. Однако часто уда-
ется преобразовать грамматику к требуемому для того или иного
детерминированного разбора виду не "испортив" описываемый ею
язык.
Удаление бесполезных символов и правил
Назовем символ А бесполезным, если он не встречается ни в
одном выводе цепочки терминалов из начального символа граммати-
ки. Oчевидно, что бесполезные символы и все содержащие их пра-
вила могут быть удалены из грамматики. Например, в грамматике
S : a | A ; A : Ab ; B : b
из нетерминала A нельзя вывести ни одной терминальной цепочки,
а нетерминал B не может быть выведен из начального символа S.
Множество нетерминалов, из которых выводятся терминальные
цепочки легко вычислить:
K := { A | существует правило A:терминалы }; К1 := пусто;
цикл пока К != К1 выполнять
К1 := К
К := К U { A | существует правило
A:(нетерминалы из К1 и и терминалы) }
конец цикла
Следствие: проблема пустоты КС-языка разрешима - язык пуст,
если и только если S не принадлежит K.
После удаления из грамматики нетерминалов, не принадлежащих
К, несложно найти множество L небесполезных символов:
L := {S}; L1 := пусто;
цикл пока L != L1 выполнять
L1 := L
L := L U { B | сущ. правило A:..B.., и А принадлежит L1 }
конец цикла
После удаления дополнения L из грамматики, она не будет со-
держать бесполезных символов (доказательство - упражнение). Бу-
дут ли удалены все бесполезные символы из грамматики, если если
применить сначала второй, а затем первый алгоритм?
Устранение е-правил
Правило вида A:e будем называть e-правилом. Если язык не со-
держит пустой цепочки, то из грамматики можно удалить все
e-правила, в противном случае можно ввести новый начальный сим-
вол S1, правилo S1 : S | e, и удалить все остальные e-правила.
Описание алгоритма - упражнение. Указание: вычислить вначале
множество нетерминалов, из которых выводится пустая цепочка.
Следствие: КС-язык, не содержащий пустой цепочки, может быть
описан неукорачивающей грамматикой.
Устранение циклов и цепных правил
Обозначим символом :: выводимость одной цепочки из другой с
помощью непустой последовательности правил. Назовем циклом вы-
вод вида A::A... . Для устранения циклов можно удалить из грам-
матики все цепные правила вида A:B. Для каждого нецепного пра-
вила вида А:..., добавим в грамматику правила B:..., для всех
B, из которых с помощью цепных правил выводится А. После этого
удаление цепных правил не изменит языка. Грамматику без циклов,
e-правил и лишних символов называют приведенной.
Упражнение. Грамматика в нормальной форме Хомского содержит
только правила вида A:BC, A:a и S:e, если язык содержит пустую
цепочку. Покажите, что любой КС-язык можно описать грамматикой
в нормальной форме Хомского.
Устранение левой рекурсии
Нетерминал A называется рекурсивным, если существует вывод:
Если x=e, то A называется леворекурсивным, если y=e, то право-
рекурсивным.
A :: xAy
Упражнение: что можно сказать про язык, описанной граммати-
кой без рекурсивных нетерминалов?
Метод рекурсивного спуска не работал для леворекурсивных
грамматик. От левой рекурсии всегда можно избавится (Это не оз-
начает, что метод рекурсивного спуска применим к любому языку.)
Покажем вначале, как 8устранить прямую левую рекурсию, т.е.
правила вида A:A... . Пусть
A : Aa1|...|Aan | b1|...|bn
все A-правила грамматики, и ни одна из цепочек bi не начинается
с A. Тогда, применяя A-правила к самому левому нетерминалу, из
А можно вывести следующее регулярное множество цепочек:
(b1|...|bn)(a1|...|an)*
Это множество выводится и из преобразованной грамматики:
A : b1|...|bn | b1T|...|bnT
T : a1|...|an | a1T|...|anT
Устранить общую левую рекурсию можно с помощью следующего
процесса, напоминающего последовательное исключение переменных
при решении системы уравнений методом Гаусса.
цикл для i от 1 до n
инвариант: для всех k<i (сущ. правило Ak:Al...) => l>k
цикл для j от 1 до i-1
инвариант: для всех k<j (сущ. правило Ak:Al...) => l>k
каждое правила Ai:Aj... заменить на правила Ai:Lj...,
где Lj - все правые части Aj-правил
конец цикла
устранить прямую левую рекурсию для Ai
конец цикла
Упражнение. Грамматика в нормальной форме Грейбах содержит
только правила вида A:aB, где a-терминал, B - последователь-
ность (может быть пустая) нетерминалов, а также S:e, если язык
содержит пустую цепочку. Покажите, что любой КС-язык можно опи-
сать грамматикой в нормальной форме Грейбах.
Алгоритм Кока-Янгера-Касами
Даны: КС-грамматика и цепочка символов. Требуется опреде-
лить, выводима ли данная цепочка из грамматики. Напомним, что
для регулярных языков аналогичная проблема решалась за линейное
от длины цепочки время. Рассмотренный ниже алгоритм решает
проблему принадлежности цепочки КС-языку за полиномиальное от
длины цепочки время.
Вначале преобразуем грамматику в нормальную форму Хомского,
т.е. в грамматику с правилами вида A:BC и A:a. Пусть a1a2...an
- исходная цепочка символов. Построим треугольную таблицу Ti,j:
1<=i<=n, 1<=j<=n-i+1. Тi,j - множество нетерминалов, из которых
выводится цепочка терминалов aj...aj+i-1. (подцепочка длины i,
левый символ которой имеет индекс j).
| T1,j нетерминалы, из которых выводятся односимвольные цепочки
цикл для j от 1 до n
T1,j := { A | существует правило A:aj }
конец цикла
| первым шагом вывода из А i-символьной цепочки (i>1) может
| быть только применение правила A:BC, где из B выводится левая
| подцепочка, а из C - правая, причем обе подцепочки имеют дли-
| ну меньшую i. Так называемое "динамическое программирование":
цикл для i от 2 до n
цикл для j от 1 до n-i+1
Tij := пусто
цикл для k от 1 до i-1
Tij := Tij U { A | (существует правило A:BC)
и (B принадлежит Тk,j)
и (C принадлежит Тi-k,j+k) }
конец цикла
конец цикла
конец цикла
цепочка выводима из грамматики := S принадлежит Tn,1
Алгоритм требует времени порядка n**3 и памяти n**2, где n -
длина цепочки (докажите!). Это делает его малопригодным для
практических целей. На практике применяются специальные
подклассы КС-грамматик, для которых существуют линейные алго-
ритмы разбора.
LL(k) языки и грамматики
Рассмотрим дерево вывода в процессе получения левого вывода
цепочки. Промежуточная цепочка в процессе вывода состоит из це-
почки из терминалов w, самого левого нетерминала A, недовыве-
денной части x:
-S--
/ \
/ -А-x-\
/ ¦ \
-w-+-u----
Для продолжения разбора требуется заменить нетерминал A по
одному из правил вида A:y. Если требуется, чтобы разбор был де-
терминированным (без возвратов), это правило требуется выбирать
специальным способом. Говорят, что грамматика имеет свойство
LL(k), если для выбора правила оказывается достаточно рассмот-
реть только wAx и первые k символов непросмотренной цепочки u.
Первая буква L (Left, левый) относится к просмотру входной це-
почки слева направо, вторая - к используемому левому выводу.
Определим два множества цепочек:
FIRST(x) - множество терминальных цепочек, выводимых из x,
укороченных до k символов.
FOLLOW(A)- множество укороченных до k символов терминаль-
ных цепочек, которые могут следовать непос-
редственно за A в выводимых цепочках.
Грамматика имеет свойство LL(k), если из существования двух це-
почек левых выводов:
S :: wAx : wzx :: wu
S :: wAx : wtx :: wv
из условия FIRST(u)=FIRST(v) следует z=t.
В случае k=1 для выбора правила для А, достаточно знать
только нетерминал A и а - первый символ цепочки u:
следует выбрать правило A:x, если а входит в FIRST(x)
следует выбрать правило A:е, если а входит в FOLLOW(A)
Покажите, что такой выбор правил непротиворечив - упражнение.
Указание: Воспользуйтесь фактом, что для LL(1)-грамматики с
правилами A:x и A:y множества FIRST(xFOLLOW(A)) и
FIRST(yFOLLOW(A)) не пересекаются (упражнение). Для k>1 это ут-
верждение неверно (упражнение).
Упражнение: предложите алгоритм, вычисляющий множества FIRST
и FOLLOW для символов КС-грамматики
LL(к)-свойство накладывает довольно сильные ограничения на
грамматику. Например, LL(2) грамматика
S : aS | a
не обладает свойством LL(1), т.к. FIRST(aS)=FIRST(a)={a}. В
данном случае можно понизить величину k с помощью "факториза-
ции" (вынесения множителя за скобку):
S : aA
A : S | e
Любая LL(k)-грамматика однозначна. Леворекурсивная грамматика
не принадлежит классу LL(k) ни для какого k. (Доказательство
этих двух фактов - упражнение). Иногда удается преобразовать не
LL(1)-грамматику в эквивалентную ей LL(1)-грамматику с помощью
устранения левой рекурсии и факторизации. Однако проблема су-
ществования эквивалентной LL(k)-грамматики для произвольной не
LL(k)-грамматики неразрешима.
Существуют детерминированные языки, которые не являются
n n n 2n
LL(k) ни для какого k, например - {0 10 U 0 10 | n>=1}.
Пример
Грамматика для арифметических формул:
Ф : Т | Ф + Т
Т : М | Т * М
M : ( Ф ) | а
не является LL(1), т.к. правила для Ф и Т содержат прямую левую
рекурсию, устраним ее:
------------------------T------------T------------¬
¦ ¦ FIRST ¦ FOLLOW ¦
+-----------------------+------------+------------+
¦ Ф : Т Ф1 ¦ ( a ¦ ) e ¦
¦ Ф1 : е | + Т Ф1 ¦ + e ¦ ) e ¦
¦ Т : М Т1 ¦ ( a ¦ + ) e ¦
¦ Т1 : е | * М Т1 ¦ * e ¦ + ) e ¦
¦ M : ( Ф ) | а ¦ ( a ¦ * + ) e ¦
L-----------------------+------------+-------------
Пустые цепочки порождают только нетерминалы Ф1 и Т1. Более
одного правила имеется для нетерминалов Ф1 и Т1; множества
FIRST(Ф1), FOLLOW(Ф1) и FIRST(T1), FOLLOW(T1) не пересекаются.
Таким образом, преобразованная грамматика является LL(1).
Символы e, помещенные в множества FIRST и FOLLOW имеют раз-
ный смысл и не приводят к конфликтам: e в множестве FIRST ис-
пользуется для обозначения возможности вывода пустой цепочки из
данного нетерминала, e в множестве FOLLOW означает отсутствие
следующего символа в конце строки терминалов. На практике роль
e во втором случае может играть терминатор строки.
Простейший LL(1)-компилятор формул
Поскольку действия при LL(1)-разборе зависят только от пары
"очередной нетерминал-очередной символ", этот разбор легко зап-
рограммировать. Рекурсивный спуск - это один из способов коди-
ровки LL(1)-разбора. Другой способ кодировки таблиц использует-
ся в следующем компиляторе.
Компилятор преобразует цепочки языка, соответствующего грам-
матике:
S: T {+T}
Т: E {*Е}
Е: <операнд>|(S)
в постфиксную запись.
%{ /* Коды лексем и метасимволов */
#define ID 1 /* Лексема - идентификатор */
#define META 100 /* Метасимволы грамматики */
#define S (META+0)
#define T (META+1)
#define E (META+2)
/* Коды переходов */
#define NOGO 100 /* Коды завершения разбора */
#define OK (NOGO+1)
#define ERR 110 /* Коды ошибок */
%}
%%
"+"|"*"|"("|")" { return(*yytext); }
[A-Z0-9]+ { printf("%s ",yytext); return(ID); }
\n { }
. { printf("%s: ",yytext); error(0); }
%%
static lexcode, oldcode; /* Коды очередной и предыдущей лексем */
main() {
lexcode = yylex();
parse( S ); printf("\n");
if ( lexcode ) error(4); /* Завершился ли разбор по концу файла? */
}
/*
* LL(1)-таблицы состоят из четырех полей:
* - номер лексемы или метасимвола для сопоставления
* - номер действия при успехе (семантическая программа)
* - переход при успехе (номер строки/успех/неуспех/ошибка)
* - переход при неуспехе
*/
static char stable[] = { /* LL(1) - таблица для S */
/* 00 */ T, 0, 1, ERR+1,
/* 01 */ '+', 1, 2, OK,
/* 02 */ T, 2, 1, ERR+1,
};
static char ttable[] = { /* LL(1) - таблица для T */
/* 00 */ E, 0, 1, ERR+2,
/* 01 */ '*', 1, 2, OK,
/* 02 */ E, 2, 1, ERR+2,
};
static char etable[] = { /* LL(1) - таблица для E */
/* 00 */ ID, 0, OK, 1,
/* 01 */ '(', 0, 2, NOGO,
/* 02 */ S, 0, 3, ERR+1,
/* 03 */ ')', 0, OK, ERR+3,
};
/* Указатели на LL(1) - таблицы */
static char *blocks[] = { stable, ttable, etable, };
/*
* Интерпретатор LL(1)-таблиц
* Вход: m - лексема или метасимвол
* Результат: 1, когда сопоставление удалось
*/
parse (m) {
register char *block, *p, sign;
if ( m<META ) {
if (lexcode != m) return(0);
oldcode = lexcode; lexcode = yylex();
return(1);
}
p = block = blocks[m-META];
for(;;) {
if ( parse( *p++ ) ) {
switch ( *p++ ) { /* Семпы */
case 0: break;
case 1: sign = oldcode; break;
case 2: printf("%c ", sign); break;
default: error(1);
}
} else p += 2;
if ( *p < NOGO ) p = block+*p*4;
else if ( *p <= OK ) return (*p-NOGO);
else error(*p-ERR);
}
}
static char *ermsg[] = { /* Тексты сообщений об ошибках */
/* 00 */ "ошибочный символ", /* 01 */ "отказ",
/* 02 */ "не найден операнд", /* 03 */ "не хватает )",
/* 04 */ "не найден знак",
};
error(e) { printf ("%s\n", ermsg[e]); exit(1); }
yywrap() { return(1); }
Упражнение по программированию: интерпретатор LL(1)-таблиц
разбора интенсивно пользуется рекурсией, что делает парсер не
слишком эффективным. Реализуйте нерекурсивный интерпретатор
таблиц.
Оставить комментарий
Комментарии
1.
13 декабря 2016, 15:08:11
Кто сможет подсказать что означает follow кроме как следовать https://preply.com/question/ch...
Очень много слов тяжело переводить с обычным переводчиком, пора наверное учить англ с репетитором.
Очень много слов тяжело переводить с обычным переводчиком, пора наверное учить англ с репетитором.
2.
16 декабря 2006, 20:35:24
Гордеев, Молчанов "Системное программное обеспечние" примерно 478 стр =))