Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11639
Последний выпуск: 19.06.2015

Языки и грамматики. Простейший компилятор.

   Алфавит - это любое множество символов. Понятие  символа  не
определяется. Цепочка символов  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. Реализуйте компилятор формул из постфиксной (или префиксной)
   записи в инфиксную. В каком направлении удобно просматривать
   исходную постфиксную (или префиксную) запись? Из-за  наличия
   скобок такой перевод не является  однозначным,  поэтому  две
   задачи:
   - в инфиксной записи допускаются "лишние" скобки;
   - "лишние" скобки не допускаются.
Оглавление | Вперед

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 

Комментарии

1.
53K
03 сентября 2009 года
koster
0 / / 03.09.2009
Мне нравитсяМне не нравится
6 декабря 2009, 19:40:22
спасибо, нашел реферат!
2.
46K
14 декабря 2008 года
Artemd999
0 / / 14.12.2008
+1 / -1
Мне нравитсяМне не нравится
14 декабря 2008, 16:38:17
ты орешь чувак, при чем тут твой реферат на тему компиляция?!
мля, ты еще и из 2005 года Х)
3.
Аноним
Мне нравитсяМне не нравится
17 октября 2005, 19:32:26
Мне нужен реферат на тему:"Компиляция"
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог