CodeNet / Приложения / Алгоритмы / Разбор выражений. Компиляторы и интерпретаторы. / Основы компиляции
Языки и грамматики. Простейший компилятор.
Алфавит - это любое множество символов. Понятие символа не
определяется. Цепочка символов 0,1,2 записывается как "012"
(или 012). Другие обозначения:
R
x - цепочка x с символами в обратном порядке
n
x - цепочка x, повторенная n раз
x* - цепочка x, повторенная 0 или более раз
x+ - цепочка x, повторенная 1 или более раз
xy - сцепление (конкатенация) цепочек x и y
|x| - длина (число символов) цепочки x
e - пустая цепочка
Цепочку из одного символа будем обозначать самим символом.
Буквы x,y,z,u,v,w,t будем применять для обозначения цепочек.
Множество всех цепочек из элементов множества E естественно
обозначить через E*. Язык - это подмножество E*. Примеры язы-
n n
ков: Си, русский, { 0 1 | n >= 0 }.
Язык можно задать:
- перечислив все цепочки;
- написав программу-распознаватель, которая получает на вход
цепочку символов и выдает ответ "да", если цепочка принадлежит
языку и "нет" в противном случае;
- с помощью механизма порождения - грамматики.
Чтобы задать грамматику, требуется указать:
- множество символов алфавита (или терминальных символов) E.
Будем обозначать их строчными символами алфавита и цифрами;
- множество нетерминальных символов (или метасимволов), не пе-
ресекающееся с E со специально выделенным начальным символом
S. Будем обозначать их прописными буквами;
- множество правил вывода, определяющих правила подстановки
для цепочек. Каждое правило состоит из двух цепочек (напри-
мер, x и y), причем x должна содержать по крайней мере один
нетерминал; и означает, что цепочку x в процессе вывода мож-
но заменить на y. Вывод цепочек языка начинается с нетерми-
нала S. Правило грамматики будем записывать в виде x : y.
(Также употребляется запись x ::= y или x -> y)
Более строго, определим понятие выводимой цепочки:
- S - выводимая цепочка;
- если xyz - выводимая цепочка и в грамматике имеется правило
y:t, то xtz - выводимая цепочка;
- определяемый грамматикой язык состоит из выводимых цепочек,
содержащих только терминальные символы.
Примеры:
а) S : e б) S : e
S : 0S1 S : (S)
S : SS
Для сокращения записи принято использовать символ "или" - "|".
Короткая форма записи предыдущих примеров:
а) S : e | 0S1 б) S : e | (S) | SS
Более сложный пример:
в) S : aSBC | abC
CB : BC
bB : bb
cC : cc
bC : bc
n n n
Эта грамматика порождает язык a b c (доказательство этого факта
- упражнение).
Грамматики в свою очередь образуют т.н. метаязык. Выше была
описана "академическая" форма записи метаязыка. На практике
применяется также другая форма записи, традиционно называемая
нормальными формами Бэкуса-Наура (НФБН). Терминалы в НФБН запи-
сываются как обычные символы алфавита, а нетерминалы - как име-
на в угловых скобках <>. Например, грамматику целых чисел без
знака можно записать в виде:
<число> : <цифра> | <цифра> <число>
<цифра> : 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Лирическое отступление. Можно ли записать грамматику какого-ли-
бо метаязыка на нем самом? Ответ - да. Решение - упражнение.
Рассмотрим язык простейших арифметических формул:
<формула> : (<формула>) | <число> | <формула><знак><формула>
<знак> : + | *
Почему "3+5*2" является формулой? Приведем последовательность
преобразований цепочек (так называемый "разбор" или "вывод"):
<формула> : <формула> <знак><формула> :
<формула><знак><формула><знак><формула> :
<число> <знак><формула><знак><формула> :
3 <знак><формула><знак><формула> :
3 + <формула><знак><формула> :
3 + <число> <знак><формула> :
3 + 5 <знак><формула> :
3 + 5 * <формула> :
3 + 5 * <число> :
3 + 5 * 2
Сокращенно наличие вывода (цепочки преобразований) будем за-
писывать в виде <формула>::3+5*2. Большинство грамматик допус-
кают несколько различных выводов для одной и той же цепочки из
языка. Постройте другой вывод для цепочки "3+5*2" - упражнение.
Если в процессе вывода цепочки правила грамматики применяют-
ся только к самому левому нетерминалу, говорят, что получен ле-
вый вывод цепочки. Аналогично определяется правый вывод. Какой
вывод построен в предыдущем примере?
Изобразим выполняемые замены цепочек в виде т.н. "дерева
разбора" (или дерева вывода). По традиции дерево изображается
"вверх ногами":
<формула>
/ \ \
<формула> \ <формула>
/ | \ \ |
<формула> <знак> <формула> | |
/ | | | |
| | | | |
<число> <знак> <число> <знак> <число>
| | | | |
3 + 5 * 2
Нарисованное дерево имеет ветви (линии) и узлы (помечены терми-
налами и нетерминалами), из которых растут ветви. Конечные узлы
(терминалы) называются листьями. Понятия "поддерево", "корень
дерева", видимо, не нуждаются в определении.
Одно и то же дерево разбора может описывать различные выводы
(в дереве не фиксирован порядок применения правил). Однако,
между левыми (или правыми) выводами и деревьями разбора для
цепочек существует однозначное соответствие (упражнение).
Если для одной и той же цепочки можно изобразить два разных
дерева разбора (или, что то же самое, построить, два разных
правых вывода), грамматика называется неоднозначной. Описанная
грамматика неоднозначна (почему? - упражнение). Тот же самый
язык можно описать однозначной грамматикой:
<формула> : <терм> | <терм><знак><формула>
<терм> : (<формула>) | <число>
<знак> : + | *
Как изменится дерево разбора? - упражнение. Дерево разбора оп-
ределяет некоторую структуру цепочки языка. Так, мы видим, что
подцепочка "3+5" является "формулой". Это противоречит нашим
(интуитивным) понятиям о смысле исходной формулы: 3+5 в отличие
от 5*2 не является подвыражением. Мы можем учесть приоритет
операций, изменив грамматику:
<формула> : <терм> | <формула> + <терм>
<терм> : <элемент> | <терм> * <элемент>
<элемент> : (<формула>) | <число>
Как добавить в язык операции вычитания и деления? - упражнение.
Кроме привычной формы записи арифметических формул (т.н.
"инфиксной", т.е. со знаком операции между операндами), широко
распространена "постфиксная" (или обратная польская) форма за-
писи, в которой операция расположена после операндов. Примеры:
2+3 2 3 +
2*3+4 2 3 * 4 +
2*(3+4) 2 3 4 + *
В обратной польской записи скобки не требуются, а значение фор-
мулы очень легко вычислить при использовании стека чисел - уп-
ражнение.
Перевод с одного языка на другой называется трансляцией или
компиляцией. Так как любую инфиксную формулу можно переписать в
постфиксную запись с сохранением порядка следования чисел (до-
казательство - упражнение), то для компиляции формулы из ин-
фиксной в постфиксную запись следует выделить внешнюю операцию,
записать в постфиксной форме оба операнда и записать операцию
вслед за ними. Для перевода операнда в постфиксную запись можно
рекурсивно обратиться к программе перевода формулы. Однако
следование правилам грамматики при компиляции формулы за один
ее просмотр слева направо приводит к следующему фрагменту:
CompForm() {
CompForm()
...
выполнение которого, конечно же, никогда не завершится. Пробле-
ма возникла из-за того, что цепочки в левой и правой частях
правила начинаются с одного нетерминала (говорят, что граммати-
ка леворекурсивна).
Если устранить левую рекурсию:
<формула> : <терм> | <терм><плюс минус><формула>
<терм> : <элемент> | <элемент><умножить разделить><терм>
<плюс минус> : + | -
<умножить разделить> : * | /
то описанная проблема исчезнет, рекурсивный компилятор можно
будет написать, однако появятся новые трудности (какое дерево
разбора будет соответствовать цепочке "5-3-2"? - упражнение).
Фактически, преобразовав грамматику, мы изменили порядок
свертки операций. Традиционно операции одного приоритета выпол-
няются слева направо (говорят, что операции левоассоциативны),
а только что написанная грамматика определяет операции как пра-
воассоциативные.
Наиболее просто решить эту проблему можно, добавив в мета-
язык НФБН символы итерации {} "повторить 0 или более раз". С
применением новых обозначений грамматика легко запишется без
левой рекурсии:
<формула> : <терм> { <плюс минус> <формула> }
<терм> : <элемент> { <умножить разделить> <элемент> }
Написанный по этой грамматике рекурсивный компилятор также бу-
дет выглядеть просто:
char *infix, *postfix; /* указатели на входную и выход-
ную цепочки */
CompForm() { /* компилировать формулу */
register char sign;
CompTerm();
while ( (sign = *infix) == '+' || sign == '-' ) {
++infix;
CompTerm();
*postfix++ = sign;
*postfix++ = ' ';
}
}
CompTerm() { /* компилировать терм */
register char sign;
CompEl();
while ( (sign = *infix) == '*' || sign == '/' ) {
++infix;
CompEl();
*postfix++ = sign;
*postfix++ = ' ';
}
}
CompEl () { /* компилировать элемент */
if ( *infix == '(' ) {
++infix;
CompForm();
if ( *infix++ != ')' ) error();
} else {
if ( !isdigit(*infix) ) error();
while ( isdigit( *infix ) ) *postfix++ = *infix++;
*postfix++ = ' ';
}
}
Использованная нами при написании компилятора техника носит
название рекурсивного спуска. Входную цепочку мы просматриваем
слева направо, дерево вывода проходим сверху вниз (т.е. от на-
чального нетерминала <формула>).
Функция error в компиляторе служит для вывода сообщения о
том, что предъявленная цепочка не входит в язык арифметических
формул. Если компилятор при получении на вход цепочки не выдает
сообщения об ошибке, говорят, что эта цепочка допущена. Приве-
дите примеры не входящих в язык арифметических формул цепочек,
допускаемых компилятором - упражнение.
Если разбор цепочки-программы сопровождается не переводом ее
в другое представление для дальнейшего выполнения, а немедлен-
ным исполнением (в нашем случае - вычислением значения), гово-
рят, что программа интерпретируется.
Задачи и упражнения:
1. Какой язык описывает грамматикa, является ли данная грамма-
тика однозначной?
- S : e | 0 S 0 | 1 S 1
- S : 0 S 1 | 0 1
- S : S S '+' | S S '*' | 'a'
- S : '+' S S | '-' S S | 'a'
- S : S '(' S ')' S | e
- S : 'a' S 'b' S | 'b' S 'a' S | e
- S : 'a' | S '+' S | S S | S '*' | '(' S ')'
2. Описать язык однозначной грамматикой:
- обратная польская(постфиксная) запись арифметической формулы
- префиксная арифметической формулы
- арифметическое выражение из целых констант, имен переменных,
бинарных операций '+', '-', '*', '/' и унарной операции '-'
- левоассоциативный список имен, разделенных запятыми
- правоассоциативный список имен, разделенных запятыми
- римские цифры
3. Доказать, что двоичные числа, описываемые грамматикой
n : 1 1 | 1 0 0 1 | n 0 | n n
делятся на 3. Порождает ли данная грамматика все двоичные числа
кратные трем?
4. Показать, что грамматика
stmt : IF expr THEN stmt
| IF expr THEN stmt ELSE stmt
| OTHER
не является однозначной. Преобразовать ее в однозначную грамма-
тику, описывающую язык, в котором ELSE соответствует ближайшему
незакрытому THEN.
5. Какие ограничения следует наложить на грамматику, чтобы при-
менение рекурсивного спуска было возможно?
6. Напишите грамматики для следующих языков:
2
n m n m n
а) 0 б) a b a b в) xx, где x - любая цепочка
из нулей и единиц.
Упражнения по программированию:
1. Переделайте компилятор так, чтобы он не допускал ошибочных
(т.е. не порождаемых грамматикой) цепочек.
2. Добавьте в компилятор операцию возведения в степень (право-
ассоциативная операция "^" с наивысшим приоритетом).
3. Переделайте компилятор формул в интерпретатор.
4. Добавьте в компилятор операцию "унарный минус", чтобы вход-
ные цепочки типа -(-a*b+c) стали бы допустимыми и правильно
компилировались. Цепочки вида --a, a+-b, конечно же, не дол-
жны допускаться!
5. Реализуйте компилятор римские цифры -> арабские цифры
6. Реализуйте компилятор арабские цифры -> римские цифры
В префиксной форме записи формулы знак операции предшествует
операндам, например, 1+2*3 записывается в виде + 1 * 2 3 .
(Именна эта форма записи была предложена Я.Лукасевичем и полу-
чила название "польской").
7. Вычислите значение формулы, записанной в префиксной записи,
просматривая ее один раз слева направо.
8. Реализуйте компилятор формул инфиксная запись -> префиксная.
9. Реализуйте компилятор формул из постфиксной (или префиксной)
записи в инфиксную. В каком направлении удобно просматривать
исходную постфиксную (или префиксную) запись? Из-за наличия
скобок такой перевод не является однозначным, поэтому две
задачи:
- в инфиксной записи допускаются "лишние" скобки;
- "лишние" скобки не допускаются.
Оставить комментарий
Комментарии
2.
+1 / -1
14 декабря 2008, 16:38:17
ты орешь чувак, при чем тут твой реферат на тему компиляция?!
мля, ты еще и из 2005 года Х)
мля, ты еще и из 2005 года Х)
3.
Аноним
17 октября 2005, 19:32:26
Мне нужен реферат на тему:"Компиляция"