Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991 Литература 1. A.Aho, R.Sethi, J.Ullman Compilers: principles, techniques, and tools. Addison-Wesley, Reading, MA, 1986. - современный учебник, в котором подробно изложены все темы кур¦ са; у нас, к сожалению, практически недоступен. 2. A.Aho, J.Ullman Principles of compiler design. Addison-Wesley, Reading, MA, 1977. - более старая версия преды¦ дущей книги. 3. А.Ахо, Д.Ульман Теория синтаксического анализа, перевода и компиляции. т.1,2 - М.:Мир, 1978. - монография освещает те¦ оретические аспекты рассматриваемого предмета и содержит почти все интересное, известное в начале 70-х годов. 4. Д. Грис Конструирование компиляторов для цифровых вычис¦ лительных машин. - М.:Мир, 1975. - в этой замечательной, хотя и несколько устаревшей книге основное внимание уделяется практи¦ ческим вопросам; вместе с предыдущей книгой они удачно дополня¦ ют друг друга. Небесполезные сведения содержатся и во многих других книгах, вышедших на русском языке, в названии которых встречаются слова "компилятор" или "транслятор", например, 5. Р.Хантер. Проектирование и конструирование компиляторов. - М.:Финансы и статистика,1984. Д.В.Варсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991 Материал к лекции 1. Языки и грамматики. Простейший компилятор. Алфавит - это любое множество символов. Понятие символа не определяется. Цепочка символов 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. Реализуйте компилятор формул из постфиксной (или префиксной) записи в инфиксную. В каком направлении удобно просматривать исходную постфиксную (или префиксную) запись? Из-за наличия скобок такой перевод не является однозначным, поэтому две задачи: - в инфиксной записи допускаются "лишние" скобки; - "лишние" скобки не допускаются. - конец материала к лекции 1 -