Delphi World - Основы компиляции - Лекция 1
Delphi World - это проект, являющийся сборником статей и малодокументированных возможностей  по программированию в среде Delphi. Здесь вы найдёте работы по следующим категориям: delphi, delfi, borland, bds, дельфи, делфи, дэльфи, дэлфи, programming, example, программирование, исходные коды, code, исходники, source, sources, сорцы, сорсы, soft, programs, программы, and, how, delphiworld, базы данных, графика, игры, интернет, сети, компоненты, классы, мультимедиа, ос, железо, программа, интерфейс, рабочий стол, синтаксис, технологии, файловая система...
Основы компиляции - Лекция 1

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

Литература

  • 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 -

Проект Delphi World © Выпуск 2002 - 2017
Автор проекта: Эксклюзивные курсы программирования