Автор: А.Г.Дымченко

Литература

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