Compilers

Разделяющие пробелы обычно выкидываются.

2. Синтаксический анализ, или разбор. Поток лексем группируется в иерархическую структуру, помогающую компилятору синтезировать выходной код. Как правило, это синтаксическое дерево наподобие следующего:

                       :=
                      /  \
                    /      \
               position      +
                           /   \
                         /       \
                     initial       *
                                 /   \
                              rate    60

Такие структуры отражают логику выражений – например, тот факт, что сначала выполняется умножение rate на 60, а потом сложение.

3. Семантический анализ. На этой стадии программа проверяется на семантическую корректность и собирается информация для следующих этапов. Наиболее важная часть семантического анализа – проверка типов: соответствуют ли типы операндов в каждом операторе спецификации языка. При этом компилятор может модифицировать синтаксические деревья, вставляя преобразования типов. Если в вышеприведённом примере переменная rate имеет тип real, то целое число 60 будет преобразовано к real:

                       :=
                      /  \
                    /      \
               position      +
                           /   \
                         /       \
                     initial       *
                                 /   \
                              rate  inttoreal
                                       |
                                       60

Ряд действий может быть выполнен как на стадии лексического анализа, так и синтаксического. Обычно выбирают вариант, который делает проще анализ в целом. Например, в Паскале или в Си информацию о типе переменной можно выделить уже на стадии лексического анализа, в то время как в PL/1 такое возможно только при синтаксическом анализе (синтаксис переусложнённый).

1.4. Основные стадии компиляции

Обычно выделяют следующие стадии компиляции:

Кроме того, на всех стадиях компилятору приходится работать с таблицами и обрабатывать ошибки компиляции.

На практике некоторые стадии могут объединяться в одну, некоторые – как, например, оптимизация – могут отсутствовать. Не всегда генерируется промежуточный код, в некоторых случаях можно сразу выдавать целевой код.

Первые три стадии уже рассмотрены в предыдущем параграфе; они составляют этап анализа. При этом не только формируется синтаксическое дерево, но и собирается информация, которая заносится в таблицы. В рассматриваемом примере выясняется, что в выражении участвуют переменные position, initial и rate. Во многих языках они к этому моменту должны быть описаны и, соответственно, включены в таблицу переменных. Для генерации кода существенны не имена переменных, а их адреса, поэтому синтаксическое дерево будет выглядеть примерно так:

                       :=
                      /  \
                    /      \
                  id1        +
                           /   \
                         /       \
                       id2         *
                                 /   \
                               id3  inttoreal
                                       |
                                       60

(Здесь id1, id2 и id3 – условные обозначения адресов переменных position, initial и rate соответственно.)

На долю обработчика ошибок выпадает определить местоположение ошибки, установить характер ошибки (а не просто сказать "произошла ошибка"), выдать соответствующее сообщение и попытаться как-то избавиться от ошибочной конструкции, чтобы продолжить анализ дальше.

Промежуточный код можно рассматривать как программу для некоторой абстрактной машины. (В некоторых случаях разработчики компилятора даже моделируют эту машину, чтобы проверять качество промежуточного кода.) Он должен обладать следующими свойствами: его должно быть легко генерировать, и по нему должно быть легко строить целевой код.

Промежуточный код может выглядеть по-разному. Одно из популярных представлений – так называемые "четвёрки": команды, состоящие из кода команды, адресов двух операндов и адреса, куда поместить результат. Например, оператор в нашем примере можно странслировать примерно в следующий код (здесь он изображён в "читабельном" виде):

   temp1 <- INTTOREAL(60)
            temp2 <- ID3 * TEMP1
            temp3 <- ID2 + TEMP2
            id1 <- TEMP3

Цель оптимизации – улучшить промежуточный код по некоторым параметрам (обычно по размеру либо по скорости). Некоторые оптимизации выглядят почти тривиально, но тем не менее способны существенно улучшить код. Например, в предыдущем коде можно выполнить преобразование inttoreal(60) уже во время компиляции и сразу же подставить результат:

        temp1 <- 60.0

        temp2 <- ID3 * TEMP1

        temp3 <- ID2 + TEMP2

        id1 <- TEMP3

Далее, переменная temp1 получает конкретное значение, причём только один раз, а дальше встречается только в правой части. Можно её устранить:

        temp2 <- ID3 * 60.0

        temp3 <- ID2 + TEMP2

        id1 <- TEMP3

Точно так же устраним temp3 и получим более оптимальный код:

     temp2 <- ID3 * 60.0

        id1 <- ID2 + TEMP2

Разные компиляторы оптимизируют по-разному. Те из них, которые уделяют оптимизации значительное время, принято называть оптимизирующими компиляторами. Многие компиляторы позволяют управлять процессом оптимизации.

Генерирование целевого кода – завершающая стадия компиляции. Переменным присваиваются конкретные адреса, при этом выбирается, какие переменные будут размещены в регистрах. Потом промежуточный код транслируется в целевой.

1.5. Группирование стадий

Обычно стадии объединены в две большие части, анализатор и синтезатор. Анализатор выполняет стадии анализа и создаёт промежуточный код; эта часть зависит в основном от исходного языка и мало зависит (или совсем не зависит) от целевого. На этом этапе создаются таблицы символов, диагностируется основная часть ошибок и производится оптимизация кода.

Синтезатор практически не зависит от исходного языка. На этом этапе генерируется и оптимизируется целевой код.

Такое разделение наводит на идею семейств компиляторов. Предположим, у нас есть N языков и M машин. Вместо того, чтобы разрабатывать N*M компиляторов для каждой пары язык-машина, мы можем разработать единый промежуточный язык и потом комбинировать N анализаторов и M синтезаторов. Если появляется новый язык, достаточно написать один анализатор; для новой машины достаточно написать один синтезатор.

Известно несколько примеров реализации такого подхода; наиболее популярно семейство компиляторов GNU, распространяемое свободно. В прошлом был весьма популярен пакет Top Speed. В целом же данный подход имеет довольно ограниченное применение. Дело в том, что во многих случаях специализированные компиляторы, ориентированные на конкретный язык и конкретную платформу, выдают гораздо более эффективный код, чем "составные". Применение "универсального" промежуточного языка не позволяет использовать особенности конкретной машины; кроме того, исходный язык может включать в себя средства, сильно зависящие от машины: управление памятью, обработку прерываний, многопроцессность и т.п.

Идея "составных" компиляторов впервые была выдвинута ещё в 50-х годах. Тогда же образовался комитет по выработке универсального промежуточного языка, UNCOL. Деятельность комитета успеха не имела.

Глава 2. ПРОСТОЙ КОМПИЛЯТОР

В этой главе излагаются основные понятия и методы трансляции. В качестве примера рассматривается построение компилятора, транслирующего арифметические выражения в "польскую обратную запись", которая легко переводится в команды стековой машины.

2.1. Обзор

Язык программирования можно задать, описав, как выглядят его программы (синтаксис языка) и каков их смысл (семантика языка). Для задания синтаксиса будет использоваться нотация, называемая формой Бэкуса-Наура (ФБН) или контекстно-свободной грамматикой (КСГ). Она позволяет описать синтаксис точно и формально. Семантику описывать гораздо сложнее; чаще всего будут использоваться неформальные словесные описания.

Контекстно-свободные грамматики не только описывают синтаксис, но и могут задавать способ трансляции выражений исходного языка в промежуточную форму. Такая техника называется синтаксически управляемым переводом или, кратко, СУ-переводом. Она широко применяется при построении компиляторов и будет постоянно использоваться в этой главе.

2.2. Задание синтаксиса

КСГ описывает иерархическую структуру языковых конструкций. Например, условный оператор if-else в С имеет следующую форму:

        if ( выражение ) оператор else оператор

В формальной нотации этот факт записывается так:

        <ОПЕРАТОР> -> if ( <ВЫРАЖЕНИЕ> ) <ОПЕРАТОР> else <ОПЕРАТОР>

Стрелка -> читается как "может иметь форму": оператор может иметь форму, описанную выше. Такое правило называется правилом вывода, или продукцией. Его можно рассматривать как часть определения понятия "оператор". Если оператор может иметь и другие формы, то мы можем выписать соответствующие правила вывода; совокупность всех правил вывода полностью определяет понятие "оператор".

Здесь части "if", "(", ")", "else" являются элементами C; мы будем называть их терминальными символами (терминалами). Конструкции <ОПЕРАТОР>, <ВЫРАЖЕНИЕ> не принадлежат C, они обозначают понятия языка и называются нетерминалами.

{В данном файле – и на доске на занятиях – мы будем брать нетерминалы в угловые скобки. Терминалы – там, где это необходимо – будут заключаться в кавычки. При записи правила будем ставить пробелы там, где это нужно для лучшей читаемости; если пробел является элементом языка, то он будет взят в кавычки.}

Для того, чтобы определить КСГ, нужно задать:

1) множество терминалов;

2) множество нетерминалов;

3) множество продукций, имеющих форму:

        нетерминал -> цепочка из терминалов или нетерминалов   ;

4) один из нетерминалов обозначить как стартовый. Это как раз и будет определяемое грамматикой понятие.

Пример 2.1. Рассмотрим грамматику для очень простых арифметических выражений: числа состоят из одной цифры, используются операции "+" и "-". Продукции таковы:

        1. <ВЫРАЖЕНИЕ> -> <ЦИФРА>
        2. <ВЫРАЖЕНИЕ> -> <ВЫРАЖЕНИЕ> + <ЦИФРА>
        3. <ВЫРАЖЕНИЕ> -> <ВЫРАЖЕНИЕ> – <ЦИФРА>
        4. <ЦИФРА> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

На минуту отвлечёмся от смысла этих правил и рассмотрим соглашения, которыми мы будем пользоваться при задании грамматики:

1) правила группируем по левым частям; для удобства несколько правил с одинаковыми левыми частями могут объединяться в одно, при этом правые части разделяются символом | . Например, первые три правила можно записать в эквивалентной форме:

        <ВЫРАЖЕНИЕ> -> <ЦИФРА>           |
                       <ВЫРАЖЕНИЕ> + <ЦИФРА> |
                       <ВЫРАЖЕНИЕ> – <ЦИФРА>

Иногда мы будем считать это одной продукцией, а иногда – тремя отдельными, как будет удобнее.

2) Нетерминал в левой части самого первого правила считается стартовым символом – здесь это <ВЫРАЖЕНИЕ>.

3) Набор терминалов и нетерминалов для данной грамматики явно не задаётся, а определяется из продукций.

Грамматика определяет некоторое понятие или, что то же самое, задаёт набор строк (конечной длины), которые подходят под это понятие. Мы можем определить, например, понятие "правильная программа на языке С"; тем самым мы опишем язык С. В дальнейшем мы будем называть языком некоторый набор строк конечной длины и будем говорить, что грамматика задаёт язык.

{На самом деле не всё так просто. Язык С невозможно полностью определить КСГ: есть такая теорема, что если в языке требуется описывать переменные до их первого использования, то этот язык нельзя задать КСГ. Но это уже вопрос семантики; мы можем задать грамматикой более широкое множество программ и назвать их программами, правильными с точки зрения синтаксиса, но не обязательно правильными с точки зрения семантики.}

Каким же образом грамматика задаёт набор правильных выражений (язык)? Мы строим вывод выражения – последовательность цепочек из терминалов и нетерминалов – по следующим правилам:

1) Вывод начинается со стартового нетерминала.

2) На каждом шаге применяется правило N -> С: нетерминал N, входящий в цепочку, заменяется на цепочку C.

3) Последняя строка символов – выводимое выражение. Оно состоит из терминалов и, следовательно, дальше вывод продолжить нельзя.

Пример 2.2. Построим вывод выражения 9-5+2:

	<ВЫРАЖЕНИЕ>
        <ВЫРАЖЕНИЕ> + <ЦИФРА>
        <ВЫРАЖЕНИЕ> + 2
        <ВЫРАЖЕНИЕ> – <ЦИФРА> + 2
        <ВЫРАЖЕНИЕ> – 5 + 2
        <ЦИФРА> – 5 + 2
        9 – 5 + 2

Можно обратить эту процедуру и показать, что строка 9-5+2 является выражением.

1) 9 – это выражение (по правилу 1), так как 9 – это цифра.

2) 9-5 – это выражение (по правилу 3), так как 9 – выражение и 5 – цифра.

3) 9-5+2 – это выражение (по правилу 2), так как 9-5 – выражение и 2 – цифра.

Данная процедура называется разбором строки 9-5+2. Процесс разбора можно проиллюстрировать следующей схемой.

		      выражение
		      /    | \
		    /      |   \
		  /        |     \
	   выражение      \    цифра
	    /  |  \        |     |
	  /    |    \      |     |
     выражение|    цифра |     |
	 |     |     |     |     |
       цифра |     |     |     |
	 |     |     |     |     |
	 9     –     5     +     2

Эта схема называется деревом разбора. Каждая вершина дерева помечена символом грамматики. Внутренняя вершина и её потомки соответствуют некоторой продукции: сама вершина – левой части продукции, а потомки, перечисленные слева направо – правой. Корень дерева помечен стартовым нетерминалом; листья дерева помечены терминалами или символом e , внутренние вершины – нетерминалами.

Упражнение 2.1. Рассмотрим грамматику:

	S ->  S S +  |  S S *  |  a

а) Покажите, как из данной грамматики можно вывести строку aa+a* .

б) Постройте дерево разбора для данной строки.

в) Какой язык задаётся этой грамматикой? Обоснуйте ответ.

Упражнение 2.2. Какой язык задают следующие грамматики?

а) S ->  0 S 1  |  0 1

б) 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 (в книге 2.5). Рассмотрим грамматику из примера 2.1. Правило 1 говорит, что цифра является выражением. Можно исключить понятие "цифра" и записать грамматику следующим образом:

        <ВЫРАЖЕНИЕ> -> <ВЫРАЖЕНИЕ> + <ВЫРАЖЕНИЕ> |
                       <ВЫРАЖЕНИЕ> – <ВЫРАЖЕНИЕ> |
                       0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Можно показать, что данная грамматика порождает то же самое множество выражений. В то же время она является неоднозначной. Например, выражение 9-5+2 может быть разобрано двумя способами:

               выражение                   выражение
                /  |  \                     /  |  \
              /    |    \                 /    |    \
       выражение   +   выражение   выражение   –   выражение
        /  |  \            |           |            /  |  \
      /    –    \          2           9          /    +    \
 выражение   выражение                       выражение   выражение
     |           |                               |           |
     9           5                               5           2

Если вычислять значение выражения, руководствуясь деревом, то в первом случае получится 6, во втором 2. Грамматика из примера 2.1 второго варианта не допускает.

Из данного примера видно, что разбор должен быть однозначным, иначе результаты работы программы нельзя предсказать. Поэтому при определении языка мы должны либо строить однозначную грамматику, либо вводить дополнительные правила разрешения неоднозначных ситуаций.

Ассоциативность операций

В арифметике принято, что 9+5+2 эквивалентно (9+5)+2 и 9-5-2 эквивалентно (9-5)-2. Когда у операнда – в данном случае 5 – знак операции стоит и справа и слева, требуются дополнительные соглашения, чтобы определить, к какой из операций относится этот операнд. Мы называем операцию "-" левоассоциативной, потому что операнд с минусом слева и справа принадлежит левой операции. В большинстве языков программирования операции сложения, вычитания, умножения и деления левоассоциативны.

Некоторые распространённые операции, например возведение в степень, правоассоциативны. Ещё один пример – операция присваивания в С: выражение a=b=c трактуется как a=(b=c). Такого рода строки могут быть сгенерированы следующей грамматикой:

        <СТРОКА> -> <БУКВА> | <БУКВА> = <СТРОКА>
        <БУКВА> -> a | b | c ..... | z

Следующие схемы показывают различие между левоассоциативными операциями, как -, и правоассоциативными.

              выражение                      строка
                /  |  \                     /  |  \
              /    |    \                 /    |    \
       выражение   –     цифра        буква    =     строка
        /  |  \            |            |           /  |  \
      /    –    \          2            a         /    =    \
 выражение     цифра                           буква        строка
     |           |                               |            |
   цифра         5                               b          буква
     |                                                        |
     9                                                        c

Заметьте, что дерево разбора в левоассоциативном случае вырастает влево, а в правоассоциативном – вправо. Нетрудно представить, как будут выглядеть деревья для случаев 1-2-3-4-5-6-7-8-9 и a=b=c=d=e=f.

Приоритет операций

Рассмотрим выражение 9+5*2. Оно может быть интерпретировано двояко: (9+5)*2 либо 9+(5*2). Ассоциативность операций в данном случае не поможет. Нам нужны правила приоритета операций.

Будем говорить, что у умножения приоритет выше, чем у сложения, если умножение выбирает свои операнды раньше. В арифметике умножение и деление имеют приоритет выше, чем сложение и вычитание. При этом умножение и деление имеют одинаковый приоритет, и порядок выполнения определяется ассоциативностью; то же со сложением и вычитанием.

Покажем, как построить грамматику, если заданы приоритеты и ассоциативность операций. Начнём с четырёх действий арифметики. Их характеристики можно свести в таблицу, расположив операции по возрастанию приоритета:

        + –  (левоассоциативные)
        * /  (левоассоциативные)

У нас будет два нетерминала сумма и произведение для каждого из уровней приоритета, и дополнительный нетерминал множитель для основных единиц в выражении. Сейчас это цифра и выражение в скобках:

        <МНОЖИТЕЛЬ> -> цифра | ( <ВЫРАЖЕНИЕ> )

Рассмотрим операции с наивысшим приоритетом. Поскольку они левоассоциативны, грамматика для произведения устроена аналогично грамматике из примера 2.1:

        <ПРОИЗВЕДЕНИЕ> -> <ПРОИЗВЕДЕНИЕ> * <МНОЖИТЕЛЬ> |
                          <ПРОИЗВЕДЕНИЕ> / <МНОЖИТЕЛЬ> |
                          <МНОЖИТЕЛЬ>

То же со сложением:

        <СУММА> -> <СУММА> + <ПРОИЗВЕДЕНИЕ> |
                   <СУММА> – <ПРОИЗВЕДЕНИЕ> |
                   <ПРОИЗВЕДЕНИЕ>

Выражение – это сумма:

        <ВЫРАЖЕНИЕ> -> <СУММА>

Теперь соберём эти правило воедино, заменяя везде нетерминал <СУММА> на <ВЫРАЖЕНИЕ>:

        <ВЫРАЖЕНИЕ> -> <ВЫРАЖЕНИЕ> + <ПРОИЗВЕДЕНИЕ> |
                       <ВЫРАЖЕНИЕ> – <ПРОИЗВЕДЕНИЕ> |
                       <ПРОИЗВЕДЕНИЕ>

        <ПРОИЗВЕДЕНИЕ> -> <ПРОИЗВЕДЕНИЕ> * <МНОЖИТЕЛЬ> |
                          <ПРОИЗВЕДЕНИЕ> / <МНОЖИТЕЛЬ> |
                          <МНОЖИТЕЛЬ>

        <МНОЖИТЕЛЬ> -> цифра | ( <ВЫРАЖЕНИЕ> )

В данной грамматике выражения трактуются как список произведений, разделённых знаками + и -, а произведение – как список множителей, разделённых знаками * и /.

Упражнение 2.4. Постройте однозначные грамматики для каждого из следующих языков. Покажите корректность.

Упражнение *2.5. Покажите, что все двоичные числа, порождённые следующей грамматикой, делятся на три. (Использовать индукцию по числу вершин дерева разбора.)

        <ЧИСЛО> -> 11 | 1001 | <ЧИСЛО> 0 | <ЧИСЛО> <ЧИСЛО>

Все ли числа, делящиеся на три, порождаются этой грамматикой?

2.3. Синтаксически управляемый перевод

Постфиксная (польская обратная) запись

Постфиксную запись можно наглядно описать следующим образом:

Скобки в постфиксной записи не нужны, порядок выполнения операций определяется однозначно.

Синтаксические определения

Синтаксическое определение – это контекстно-свободная грамматика, дополненная информацией о семантике конструкции. С каждым символом грамматики ассоциируется некоторый набор значений, которые мы будем называть атрибутами. Каждому правилу вывода соответствует набор семантических правил, определяющих, каким образом вычисляются атрибуты выводимой конструкции.

Переводом строки x называется следующая процедура. Сначала строим дерево разбора для x. Потом для каждой вершины Х вычисляем набор атрибутов, связанных с Х, используя семантические правила. Результатом перевода является дерево с набором вычисленных атрибутов для каждой вершины, или помеченное дерево.

Атрибут а вершины Х будет обозначаться X.a – так же, как в С обозначаются поля структуры. Действительно, разработчик компилятора может рассматривать набор атрибутов для вершины как некоторую структуру или класс.

Синтезируемые атрибуты

Атрибут называется синтезируемым, если его значение в вершине дерева может быть определено по значениям атрибутов потомков вершины. Синтезируемые атрибуты обладают хорошим свойством – они могут быть вычислены за один обход дерева снизу вверх. В этой главе будут рассматриваться только такие атрибуты.

Пример 2.4. Построим синтаксическое определение для перевода выражений из примера 2.1 в постфиксную запись. С каждым нетерминалом свяжем атрибут t – строку, представляющую постфиксную запись для выражения, порождаемого этим нетерминалом.

   Правило вывода                  Семантическое правило

  <ВЫР> -> <ЦИФРА>            <ВЫР>.t = <ЦИФРА>.t
  <ВЫР> -> <ВЫР1> + <ЦИФРА>   <ВЫР>.t = <ВЫР1>.t || <ЦИФРА>.t || "+"
  <ВЫР> -> <ВЫР1> – <ЦИФРА>   <ВЫР>.t = <ВЫР1>.t || <ЦИФРА>.t || "-"
  <ЦИФРА> -> 0                <ЦИФРА>.t = "0"
  <ЦИФРА> -> 1                <ЦИФРА>.t = "1"
  .....                       .....
  <ЦИФРА> -> 9                <ЦИФРА>.t = "9"

В записи семантических правил символ || будет обозначать конкатенацию строк.

На следующем рисунке изображено помеченное дерево разбора, соответствующее дереву из примера 2.2.

                      выражение.t = 95-2+
                      /       |       \
                    /         +         \
                  /                       \
           выражение.t = 95-            цифра.t = 2
            /    |    \                     |
          /      –      \                   2
  выражение.t = 9      цифра.t = 5
         |                 |
    цифра.t = 9            5
         |
         9

Пример 2.5. Пусть имеется робот, которому можно отдать команду передвинуться на один шаг на север, юг, запад или восток от текущей позиции. Последовательность шагов может быть описана следующей грамматикой:

        <ПУТЬ> -> старт | <ПУТЬ> <ШАГ>
        <ШАГ> -> север | юг | запад | восток

Если задан путь:

        старт запад юг восток восток восток север север,

то координаты робота будут меняться следующим образом:

                                 * (2,1)
                                 | север
             запад   старт       |
     (-1,0) *------* (0,0)       *
            |                    | север
         юг |                    |
    (-1,-1) *------*------*------* (2, -1)
             восток восток восток

Построим синтаксическое определение для вычисления позиции, в которой окажется робот, пройдя заданный путь. С нетерминалом <ПУТЬ> свяжем атрибуты x и y – координаты робота, а с нетерминалом <ШАГ> – атрибуты dx, dy, изменение координат. Синтаксическое определение выглядит так:

   продукция                   семантическое правило
<ПУТЬ> -> старт             <ПУТЬ>.x = 0, <ПУТЬ>.y = 0
<ПУТЬ> -> <ПУТЬ1> <ШАГ>     <ПУТЬ>.x = <ПУТЬ>.x + <ШАГ>.dx,
                            <ПУТЬ>.y = <ПУТЬ>.y + <ШАГ>.dy

<ШАГ> -> север              <ШАГ>.dx = 0, <ШАГ>.dy = 1
<ШАГ> -> юг                 <ШАГ>.dx = 0, <ШАГ>.dy = -1
<ШАГ> -> запад              <ШАГ>.dx = -1, <ШАГ>.dy = 0
<ШАГ> -> восток             <ШАГ>.dx = -1, <ШАГ>.dy = 0

Обход в глубину

Синтаксическое определение не задаёт какой-то определённый порядок вычисления атрибутов; подойдёт любой порядок, при котором каждый атрибут вычисляется после тех атрибутов, от которых он зависит. На практике используются различные стратегии, но пока что будем использовать только одну – обход в глубину.

Обход дерева начинается с корня дерева. Если мы находимся в некоторой вершине и у неё нет потомков, то вычисляем атрибуты этой вершины. Если потомки есть, то рекурсивно обходим их всех и вычисляем их атрибуты, потом вычисляем атрибуты вершины.

Схемы перевода

Схемы перевода – ещё один часто используемый приём определения перевода. Схема перевода представляет собой грамматику, в продукции которой включены фрагменты, описывающие некоторые действия.

Вернёмся к примеру 2.4. Переводя выражение в постфиксную запись по частям, для каждого из подвыражений мы формируем строку <ВЫР>.t. Когда обход дерева окончен, в атрибуте корневой вершины содержится постфиксная запись разбираемого выражения; эту строку, например, можно вывести на печать.

Вместо этого мы могли бы выводить перевод на печать по мере обхода дерева. Пусть, например, мы обошли следующее поддерево:

           цифра
             |
             9

Перевод данного подвыражения (постфиксная запись) – строка "9". Её можно вывести на печать. Обозначим это действие следующим образом:

            цифра
             |  .
             |    .
             9   вывод("9")

Мы как бы добавили новое ребро к дереву. Если обходить дерево в глубину, то мы сначала доберёмся до 9, а потом до действия. Как только мы добрались до действия – выполняем его. (Такие добавочные рёбра будем изображать точечной линией (на доске и в книге – штриховой).

Идём дальше.

          выражение
              |
            цифра
              |  .
              |    .
              9   вывод("9")

Перевод выражения – "9", но эта строка уже напечатана. Поэтому в данной вершине никаких действий не производится.

Идём дальше.

                  выражение
                   /  |  \
                 /    |    \
               /      –      \
          выражение         цифра
              |               |
            цифра             |
              |  .            5
              |    .
              9   вывод("9")

По аналогии включим действие для цифры 5:

                  выражение
                   /  |  \
                 /    |    \
               /      –      \
          выражение         цифра
              |               |  .
            цифра             |    .
              |  .            5   вывод("5")
              |    .
              9   вывод("9")

Когда мы обойдём всех потомков и вернёмся к корневой вершине, будет выведено "95". Теперь нужно напечатать минус:

                    выражение
                   /  |  \    .
                 /    |    \     .
               /      –      \     вывод("-")
          выражение         цифра
              |               |  .
            цифра             |    .
              |  .            5   вывод("5")
              |    .
              9   вывод("9")

Окончательно дерево будет выглядеть так:

                                  выражение .
                                 /  |  \       .
                               /    +    \        .
                             /           цифра     вывод("+")
                           /               |  .
                         /                 |    .
                    выражение              2   вывод("2")
                   /  |  \    .
                 /    |    \     .
               /      –      \     вывод("-")
          выражение         цифра
              |               |  .
            цифра             |    .
              |  .            5   вывод("5")
              |    .
              9   вывод("9")

Рис. 2.14.

По форме такое дерево похоже на обычное дерево разбора. Выпишем правила вывода, которые дают такое дерево:

        <ВЫРАЖЕНИЕ> -> <ЦИФРА>
        <ВЫРАЖЕНИЕ> -> <ВЫРАЖЕНИЕ> + <ЦИФРА> { вывод("+") }
        <ВЫРАЖЕНИЕ> -> <ВЫРАЖЕНИЕ> – <ЦИФРА> { вывод("-") }
        <ЦИФРА> -> 0 { вывод("0") }
        <ЦИФРА> -> 1 { вывод("1") }
        ....
        <ЦИФРА> -> 0 { вывод("9") }

Действия заключаются в фигурные скобки.

По счастливому стечению обстоятельств цифра в постфиксной записи появляются в том же порядке, что и в инфиксной; при переводе нам не требуется менять местами подвыражения. Такая схема перевода называется простой.

В простой схеме перевода действия выполняются слева направо. При этом мы можем выполнять действия по ходу разбора и, следовательно, нет необходимости строить дерево разбора.

2.4. Синтаксический анализ

Синтаксическим анализом (разбором) называется процесс, определяющий порождается ли данная строка лексем данной грамматикой. При решении этой задачи полезно конструировать дерево разбора, даже если компилятор на самом деле такое дерево не строит.

Синтаксический анализатор (англ. – parser, далее просто – анализатор) может быть построен для любой грамматики. Для любой КС-грамматики существует анализатор, требующий самое большее O(n³) времени для разбора строки из n лексем. Но для языков, которые встречаются на практике, хватает линейных алгоритмов. Анализаторы языков программирования почти всегда проходят один раз слева на право входной текст, считывая зараз одну лексему.

Большинство методов синтаксического разбора попадают в один из двух классов, так называемых метода "сверху-вниз" и метода "снизу-вверх". В первом методе построение дерева начинается с корня и продолжается в направлении листьев, в то время как во втором методе построение начинается с листьев и развивается по направлению к корню. Популярность анализаторов "сверху-вниз" объясняется тем, что эффективный анализатор можно легко построить "вручную". Анализаторы "снизу-вверх" могут работать с бОльшим классом грамматик и схем перевода, поэтому в программах-генераторах анализаторов все больше используются алгоритмы разбора "сверху-вниз".

Разбор сверху-вниз

Мы начнем знакомство с разбором "сверху-вниз" на примере грамматики, которая хорошо подходит для этого класса методов. Следующая грамматика описывает некоторое подмножество типов Паскаля:

<ТИП>		->	<ПРОСТОЙ>				|
			^ id					|
			array [ <ПРОСТОЙ> ] of <ТИП>
                                                                  (2.8)
<ПРОСТОЙ>	->	integer				|
			char					|
			num dotdot num

(Мы пользуемся лексемой dotdot вместо "..", чтобы подчеркнуть, что эта цепочка символов обрабатывается как одно целое) Построение дерева разбора сверху-вниз начинается с корня, помеченного стартовым нетерминалом и продолжается последовательным выполнением следующих двух шагов:

Рис. 2.15.

(a)                         <ТИП>

(b)                         <ТИП>
                  /    /      |    \      \     \
              array   [  <ПРОСТОЙ>  ]     of    <ТИП>

(c)                         <ТИП>
                  /    /      |    \      \     \
              array   [  <ПРОСТОЙ>  ]     of    <ТИП>
                         /    |   \
                       num  dotdot num

(d)                         <ТИП>
                  /    /      |    \      \     \
              array   [  <ПРОСТОЙ>  ]     of    <ТИП>
                         /    |   \               |
                       num  dotdot num          <ПРОСТОЙ>

(e)                         <ТИП>
                  /    /      |    \      \     \
              array   [  <ПРОСТОЙ>  ]     of    <ТИП>
                         /    |   \               |
                       num  dotdot num        <ПРОСТОЙ>
                                                  |
                                                целый

Для некоторых грамматик вышеуказанные шаги выполняются за одно сканирование входной строки. Текущую сканируемую лексему часто называют текущим символом (lookahead symbol). В начале текущий символ – это первая (самая левая) лексема входной строки. Проведем разбор строки array [ num dotdot num ] of integer:

======================================================================
     Дерево
     разбора                        <ТИП>
                                      ^
(а) -------------------------------------------------------------

     Вход           array [ num dotdot num ] of integer:
                      ^ 
======================================================================
                            <ТИП>
                  /    /      |    \      \     \
              array   [  <ПРОСТОЙ>  ]     of    <ТИП>
                ^
 (b) -------------------------------------------------------------

              array [ num dotdot num ] of integer:
                ^ 
======================================================================
                            <ТИП>
                  /    /      |    \      \     \
              array   [  <ПРОСТОЙ>  ]     of    <ТИП>
                      ^                
 (с) -------------------------------------------------------------

              array [ num dotdot num ] of integer:
                    ^ 
======================================================================
и т.п.

Рис. 2.16.

В начале разбора лексема array является текущим символом, а дерево состоит из корня, помеченного стартовым нетерминалом <ТИП> (Рис. 2.16.а) Наша цель – построить остаток дерева так, чтобы строка, порождаемая этим деревом, совпадала бы с входной строкой. Для этого нетерминал <ТИП> должен породить строку, начинающуюся с символа array. В нашей граматике имеется единственная продукция, которая порождает такую строку, поэтому мы выбираем ее, конструируя потомки корня в соответствии с правой частью продукции. Когда потомки узла построены, рассматриваем самого левого потомка. На рис. 2.16.b только что построены потомки корня и рассматривается самый левый потомок, помеченный array.

Если текущий узел дерева разбора помечен терминалом и этот терминал совпадает с текущим символом, мы должны продвинуться как в дереве разбора, так и во входной строке (рис. 2.16.c) Как только в дереве рассматривается узел с нетерминалом, мы повторяем процедуру выбора продукции для этого нетерминала.

Выбор продукции для нетерминала в общем случае может проходить по "методу проб и ошибок", т.е. мы можем взять какую-то продукцию и, если она окажется неподходящей, вернуться назад и попробовать взять следующую. Назовем продукцию неподходящей, если используя ее, мы не можем достроить дерево до получения соответствия с входной строкой. Однако существует особый случай разбора, в котором не случается возврата назад, это предсказывающий разбор.

Предсказывающий разбор

procedure сравнить(t: лексема);

begin
    if текущая_лексема = t then
        текущая_лексема:= следующая_лексема
    else ошибка
end;

procedure тип;
begin
    if текущая_лексема is in {integer, char, num} then
        простой
    else if текущая_лексема = '^' then begin
        сравнить('^'); сравнить(id)
    end
    else if текущая_лексема = array then begin
        сравнить(array); сравнить('['); простой; сравнить('[');
        сравнить(of); тип;
    end
    else ошибка
end;

procedure простой;
begin
    if текущая_лексема = integer then
        сравнить(integer)
    else if текущая_лексема = char then
        сравнить(char)
    else if текущая_лексема = num then
        сравнить(num); сравнить(dotdot); сравнить(num); 
    end
    else ошибка
end;

Рис. 2.17. Псевдокод для предсказывающего анализатора.

В нашей грамматике разбор начинается с вызова процедуры для стартового нетерминала <ТИП>. Пусть вход тот же самый, что и на рис. 2.16., тогда начальное значение текущей лексемы – array. Процедура тип выполняет код

	сравнить(array); сравнить('['); простой; сравнить('[');     	
        сравнить(of); тип;

что соответствует правой части продукции

	<ТИП>	-> array [ <ПРОСТОЙ> ] of <ТИП>

Заметим, что каждый терминал в правой части сравнивается с текущим символом, а для каждого нетерминала правой части вызывается соответствующая процедура.

После того как проведено сравнение лексем "array" и "[", текущим символом является "num". В этот момент вызывается процедура простой и в ее теле выполняется код

	сравнить(num); сравнить(dotdot); сравнить(num); 

Выбором продукции управляет текущий символ. Если правая часть продукции начинается с лексемы, то данная продукция выбирается при условии если текущий символ совпадает с этой лексемой. Рассмотрим случай, когда правая часть начинается с нетерминала:

	<ТИП> -> <ПРОСТОЙ>

Эта продукция используется, если текущий символ может быть выведен из нетерминала <ПРОСТОЙ>. Для нетерминала <ТИП> нет продукции, начинающейся с лексемы "integer", но зато с этой лексемы начинается одна из продукций для нетерминала <ПРОСТОЙ>.

Мы видим, что предсказывающий разбор опирается на информацию о том, какие первые символы могут порождены правыми частями продукций. Пусть у нас есть продукция A -> a, тогда
FIRST(a) = { x О T | $y: a =>* xy}
(множество лексем, встречающихся в качестве первого символа во всех строках, которые можно вывести из a; если a = e или a =>* e , то e in FIRST(a)).

Пример.  FIRST(<ПРОСТОЙ>)                    = {integer, char, num}
         FIRST(^ id)                         = {^}
         FIRST(array [ <ПРОСТОЙ> ] of <ТИП>) = {array}

Алгоритм вычисления множества FIRST будет рассмотрен позднее.

Отметим, что разбор рекурсивным спуском без возврата назад требует, чтобы в случае продукций A -> a и A -> b множества FIRST(a) и FIRST(b) не пересекались. Если это так, то для выбора продукции мы проверяем, принадлежит ли текущий символ соответствующему множеству FIRST.

Использование e -продукций

e -продукция – это продукция вида A -> e . Анализатор рекурсивного спуска выбирает e-продукцию, если не подходит ни одна другая. Пример:

	<ОПЕРАТОР> -> begin <НЕОБЯЗАТЕЛЬНЫЕ_ОПЕРАТОРЫ> end
	<НЕОБЯЗАТЕЛЬНЫЕ_ОПЕРАТОРЫ> -> <СПИСОК_ОПЕРАТОРОВ> | e

Если при разборе нетерминала <НЕОБЯЗАТЕЛЬНЫЕ_ОПЕРАТОРЫ> текущий символ не принадлежит FIRST(<СПИСОК_ОПЕРАТОРОВ>), то выбирается e-продукция. Этот выбор будет верен, если текущий символ – end, в противном случае анализатор выдаст сообщение об ошибке.

Построение предсказывающего анализатора

Предсказывающий анализатор – это программа, в которой каждому нетерминалу соответствует своя процедура. Каждая процедура выполняет две вещи:

Левая рекурсия

Разбор рекурсивным спуском таит опасность зацикливания. Это возможно если продукция имеет вид

	<ВЫР> -> <ВЫР> + <ТЕРМ>

из-за того, что нетерминал <ВЫР> леворекурсивен. Леворекурсивным назовем нетерминал A, если в грамматике есть продукция вида A -> Aa. Если приведенный выше алгоритм выберет эту продукцию, то, поскольку правая часть начинается с <ВЫР>, будет снова вызвана процедура для нетерминала <ВЫР>. Текущий символ, управляющий процессом разбора, может измениться только если будет обнаружено его совпадение с начальным терминалом в правой части продукции. В нашем случае продукция начинается с нетерминала и текущий символ остается неизменным, что вызывает зацикливание.

Левую рекурсию можно устранить переписыванием опасной продукции. Рассмотрим две продукции

	A -> A a | b

где a и b – цепочки терминалов и нетерминалов не начинающиеся с A. (Пример: <ВЫР> -> <ВЫР> + <ТЕРМ> | <ТЕРМ>). Заменим такую продукцию на следующие:

	A -> b R
	R -> a R | e

Здесь R – новый нетерминал. Продукция вида R -> a R называется праворекурсивной. Праворекурсивные продукции приводят к тому, что деревья разбора растут вправо (см. Рис 2.18.б)

                     A
                     | \
                     |  R
                     |  | \
            A        |  |  R         
                     |  |  |\        
      A     |        |  |  | ...     
    / |     |        |  |  |    \    
   A  |     |        |  |  |     R   
 / |  |     |        |  |  |     | \ 
A  |  |     |        |  |  |     |  R
|  |  |     |        |  |  |     |  |
b  a  a ... a        b  a  a ... a  e

Рис. 2.18. Лево- и праворекурсивные способы порождения строки.  

Перевод выражений содержащих левоассоциативные операции, такие как минус, становится сложнее, если используются деревья растущие вправо.

В последствии мы рассмотрим более общий вид левой рекурсии и покажем, как все левые рекурсии могут быть устранены из грамматики.

2.5. Транслятор простых выражений

Используя технику последних трех разделов, мы напишем СУ-транслятор, переводящий арифметические выражения в постфиксную форму. Для начала рассмотрим лишь выражения, состящие из цифр, разделенных знаками плюса и минуса.

	<expr> -> <expr> + <term>	{ print('+') }
	<expr> -> <expr> – <term>	{ print('-') }
	<expr> -> <term>
	<term> -> 0				{ print('0') }
	<term> -> 1				{ print('1') }
	...
	<term> -> 9				{ print('9') }

Рис. 2.19. Описание транслятора инфиксных выражений в постфиксные

Схема перевода может зачастую служить описанием (спецификацией) транслятора. Часто бывает необходимо видоизменить грамматику схемы перевода перед тем как ее можно будет использовать в предсказывающем анализаторе. В частности, грамматика, лежащая в основе схемы на рис. 2.19. леворекурсивна.

Абстрактный и конкретный синтаксис

Дерево разбора – это конкретное синтаксическое дерево. Лежащая в его основании грамматика называется конкретным синтаксисом языка.

Дерево, в котором каждый узел представляет оператор, а потомки этого узла представляют операнды называется (абстрактным) синтаксическим деревом.

       + 
      / \
     –   2
    / \
   9   5

Рис. 2.20. Синтаксическое дерево для выражения 9-5+2

Желательно, чтобы схемы перевода были основаны на грамматике, чьи деревья разбора были бы как можно ближе к синтаксическим деревьям. Сочетания подвыражений в грамматике на рис. 2.19 похожи на их сочетания в синтаксических деревьях. К сожалению, эта грамматика леворекурсивна и не подходит для предсказывающего разбора. Нужно избавлятся от левой рекурсии и, как показывает следующий пример, делать это нужно аккуратно.

Пример 2.9.

	<expr> -> <term>	<rest>
	<rest> -> + <expr> | – <expr> | e
	<term> -> 0	| 1 | ... | 9

Эта грамматика порождает тот же самый язык, что грамматика 2.19 (??? доказать) и может использоваться для рекурсивно-предсказывающего разбора. Однако она не подходит для перевода выражений в постфиксную форму. Дело в том, что продукции <rest> -> – <expr> и <rest> -> + <expr> порождают операции с неизвестными операндами. Рассмотрим первую продукцию. Семантическое правило для нее может быть выписано двумя способами:

	{ rest.t := '-' || expr.t }
	{ rest.t := expr.t || '-' }

(??? Выписать правила для остальных продукций) Однако ни первое, ни второе правило не дает желаемого результата. Правильный перевод выражения 9-5+2 есть 95-2+. Если мы воспользуемся первым правилом, то это даст неверный перевод 9-52+ или 9-5+2 (в зависимости от того, какое правило работает для операции плюс). Если мы воспользуемся вторым правилом, то это даст 952+- или 95+2-, что опять-таки неверно.

То же самое обнаруживается, если мы попытаемся получить из этой грамматики схему перевода. Рассмотрим правило

	<rest> -> – <expr>

Оно должно быть дополнено семантическим действием – печатью знака минус. Это можно сделать тремя способами:

	<rest> -> {print ('-')} – <expr>
	<rest> -> – {print ('-')} <expr>
	<rest> -> – <expr> {print ('-')}

Если строить деревья разбора, как на рис. 2.14, то можно увидеть, что при обходе дерева в глубину будут печататься ...

Приспособление схемы перевода

Техника удаления левой рекурсии, о которой говорилось в предыдущем разделе, может также применяться для продукций с семантическими действиями. Так, продукция
<A> -> <A> a | <A> b | g
превращается в
<A> -> g <R>
<R> -> a <R> | b <R> | e


В нашем случае <A> = <expr>, a = + <term> { print('+')}, b = – <term> { print('-')}, g = <term>. Новый нетерминал обозначим как <rest>. Если в продукцию входит семантическое действие, то мы сохраняем его при преобразованиях.

	<expr> -> <term>	<rest>
	<rest> -> + <expr> | – <expr> | e
	<term> -> 0	| 1 | ... | 9

	<expr> -> <term> <rest>
	<rest> -> + <term> { print('+') } <rest>
	<rest> -> – <term> { print('-') } <rest>
	<rest> -> e
	<term> -> 0              { print('0') }
	<term> -> 1              { print('1') }
	...
	<term> -> 9              { print('9') }

(??? Показать, как транслируется выражение 9-5+2 в новой грамматике)

Процедуры для нетерминалов <expr>, <term> и <rest>

Функции, соответствующие нетерминалам имитируют правые части продукций:

-----------------------------------------------------------------------
expr()
{
   term(); rest();
}

rest()
{
   if (lookahead == '+')
   {
      match('+'); term(); putchar('+'); rest();
   }
   else if (lookahead == '-')
   {
      match('-'); term(); putchar('-'); rest();
   }
   else;
}

term()
{
   if (isdigit(lookahead))
   {
      putchar(lookahead); match(lookahead);
   }
   else error();
}

match(int t)
{
   if (lookahead == t)
       lookahead = getchar();
   else error();
}

error()
{ printf("syntax error\n"); exit(1);
}
-----------------------------------------------------------------------

2.6. Лексический анализ

Сейчас мы добавим к транслятору из предыдущего раздела синтаксический анализатор, прочитывающий и преобразующий вход в поток лексем для лексического анализатора. Выражения языка состоят из цепочек символов алфавита. Последовательность входных символов составляющих один символ языка называется лексемой. Лексический анализатор может выдавать синтаксическому анализатору лексемное представление символа. Мы начнем с перечисления некоторых функций, выполнения которые мы могли бы ожидать от лексического анализатора.

Удаление пробелов и комментариев

Транслятор выражений из предыдущей секции прочитывает каждый символ входа, таким образом лишние символы, такие как пробелы, приведут к ошибке. Если пробелы удаляютс лексическим анализатором, синтаксическому анализатору не придется их рассматривать. Не так легок другой способ, состоящий в изменении грамматики, так чтобы она включала символы пробела (табуляции, переводы строки и т.п.)

Константы

Мы хотим использовть произвольные целочисленные константы в наших выражениях. Из-за того, что целочисленная константа – это цепочка цифр, мы можем добавить в грамматику соответствующие продукции, либо создать соответствующий символ для таких констант. Однако задача сбора цепочки цифр в целые числа обычно дается лексическому анализатору, так как числа можно трактовать при переводе как одно целое.

Пусть num – символ, представляющий число. Когда во входном потоке появляется последовательность цифр, лексический анализатор передаст синтаксическому анализатору символ num. Само значение целого числа будет передано как атрибут символа num. Если мы запишем символ и его атрибуты как пару в угловых скобках, то вход

	31 + 28 + 59

преобразуется в последовательность пар

	 <+, >  <+, > 

Символ "+" не имеет атрибутов. Второй компонент пары, атрибут, не играет роли при разборе, но необходим при переводе.

Распознавание идентификаторов и ключевых слов.

Языки програмирования используют идентификаторы как имена переменных, массивов, функций и т.п. Грамматика для языка зачастую трактует идентификатор как символ. СА, основанный на такой грамматике желает видеть один и тот же символ, скажем "id", каждый раз, когда на входе появляется идентификатор. К примеру, вход

	count = count + increment;                                     (2.15)

должен быть преобразован лексическим анализатором в используемый для разбора поток символов

	id = id + id;

Говоря о лексическом анализе входной строки (2.15), полезно различать символ id и лексемы count и increment. Транслятору нужно знать, что лексема count образует первые два вхождения симовла id в (2.16), а лексема increment – его третье вхождение.

Когда на входе появляется лексема-идентификатор, необходим механизм распознавания того, встречалась ли эта лексема раньше. Лексема сохраняется в таблице символов, а указатель на позицию в таблице символов становится атрибутом символа id.

Многие языки программирования используют слова такие, как begin, end, if, в качестве знаков препинания или для того чтобы выделить определенные конструкции. Эти слова называются ключевыми словами в общем случае удовлетворяют правилам построения идентификатора. Таким образом, необходим механизм распознавания, в каком случае лексема является ключевым словом, а в каком – идентификатором. Эта проблему легче решить, если ключевые слова заререзервированы, т.е. не могут быть использованы в качестве идентификаторов. В таком случае слово образует идженификатор, если оно не является ключевым словом.

Проблема выявления символов языка встает также в том случае, если одни и те же входные символы встречаются в лексемах нескольких символов языка, как в <>, <, <= В ПАСКАЛЕ. ТЕХНИКА ЭФФЕКТИВНОГО РАСПОЗНАВАНИЯ ТАКИХ СИМВОЛОВ ОБСУЖДАЕТСЯ В ГЛАВЕ 3.

Взаимодействие с лексическим анализатором

Лексический анализатор, будучи вставлен между синтаксическим анализатором и входным потоком, взаимодействет с ними следующим образом:

          прочесть символ   +-------------+  передать лексему   +-----------+
+------+  --------------->  | лексический |  и ее  атрибуты     | синтаксич.|
| Вход |                    |  анализатор |  -----------------> | анализатор|
+------+  <--------------   +-------------+                     +-----------+
           ВЕРНУТЬ СИМВОЛ


РИС. 2.25.

В некоторых ситуациях лексический анализатор должен прочесть несколько символов сразу, чтобы выяснить, какую лексему нужно передать синтаксическому анализатору. Пример: лексический анализатор языка Паскаль встречает входной символ '>'. Ему нужно прочесть еще один символ, чтобы выяснить, какая лексема встретилась: '>' или '>='. При необходимости лишний прочитанный символ возвращается во входной поток, так как он может быть началом следующей лексемы.

Лексемы, выдаваемые лексическим анализатором могут храниться в буфере лексем и потребляться синтаксическим анализатором по мере необходимости. Обычно буфер хранит лишь одну лексему. В этом случае лексический анализатор может быть процедурой, вызываемой синтаксич. анализатором, которая возвращает лексему.

Прочитывание и возврат символов со входа производится обычно с помощью входного буфера.

Лексический анализатор

Мы построим элементарный лексический анализатор на языке С для перевода выражений из предыдущего раздела. Цель: разрешить, чтобы в выражениях могли встречаться пробелы и числа. Функция lexan() возвращает целое число, кодирующее лексему. В глобальной переменной tokenval хранится значение последовательности цифр.

Использование чисел в выражениях требует изменения грамматики на рис. 2.19. Правила для конкретных цифр заменяются следующей продукцией и семантическим действием:

	 -> ( <expr> ) | 
                  num { print(num.value} }

На С эта продукция записывается так:

factor()
{
    if (lookahead == '(') 
    {  match('('); expr(); match(')');
    }
    else if (lookahead == NUM)
    {  printf(" %d ", tokenval); match(NUM);
    }
    else error();
}

#include 
#include 

#define NUM 256

int lineno = 1;
int tokenval = NONE;

int lexan()
{
	int t;
	while(1) 
	{	t = getchar();
		if (t == ' ' || t = '\t')
		;
		else if (t == '\n')
			lineno++;
		else if (isdigit(t))
		{	tokenval = t – '0';
			t = getchar();
			while (isdigit(t))
			{	tokenval = tokenval*10 + t – '0';
				t = getchar();
			}
			ungetc(t,stdin);
			return NUM;
		}
		else
		{	tokenval = NONE;
			return t;
		}
	}
}

2.7. Подключение таблицы символов

Структура данных, называемая таблицей символов обычно используется для хранения информации о разного рода конструкциях языка. Эта информация собирается на этапе анализа и используется на этапе синтеза при генерации целевого кода. Например, во время лексического анализа как элемент символьной таблицы хранится цепочка знаков, или лексема, образующая идентификатор. На более поздних этапах компилятор может добавлять к этому элементу информацию о типе идентификатора, его использовании (процедура, переменная или метка) и его место в памяти. В разделе 7.6 мы обсудим детально исполнение и использование таблицы символов. В этом разделе мы покажем, как лексический анализатор из предыдущего раздела мог бы взаимодействовать с таблицей символов.

Интерфейс с таблицей символов

Табличносимвольные процедуры в первую очередь касаются сохранения и затребования лексем. При сохранении лексемы сохраняется также и символ, связанный с лексемой:

Наш лексический анализатор использует процедуру поиска (lookup) для выяснения того, есть ли для лексемы элемент в таблице символов. Если нет, то анализатор использует процедуру вставки (insert) для создания такого элемента. Мы обсудим реализацию, в которой и лексический, и синтаксический анализаторы знают формат элементов таблицы символов.

Зарезервированные ключевые слова

Вышеуказанные процедуры могут обрабатывать любой наборых зарезервированных ключевых слов. Рассмотрим, к примеру символы "div" и "mod" с лексемами div и mod соответственно. Мы можем инициализировать таблицу символов с помощью вызовов

	insert("div", div);
	insert("mod", mod);

Впоследствии любой вызов lookup("div") возвращает символ div, поэтому div не может быть использован как идентификатор.

Реализация таблицы символов

Таблицу символов можно реализовать, как (динамический) массив элементов типа SymtableRecord:

struct SymtableRecord
{      char *lexeme;
	 enum {NUM, DIV, MOD, ID} token;
       int attribute;
};

2.8. Абстрактная стековая машина

Стековая машина – популярная форма промежуточного представления кода. Команды и данные у этой машины хранятся отдельно. Все арифметические операции выполняются над величинами в стеке. Команд очень немного и они разбиваются на три класса: целочисленной арифметики, манипуляций со стеком и потока управления.

Арифметические команды

Абстрактная стековая машина должна выполнять каждый оператор промежуточного языка. Базовые операции, такие как сложение и вычитание поддерживаются абстрактной машиной напрямую. Более сложные операции, возможно, должны выполняться как последовательность команд абстрактной машины. Мы упрощаем описание машины, допуская, для каждой арифметической операции есть своя команда.

Программа абстрактной машины для арифметического выражения имитирует вычисления постфиксного представления этого выражения с использованием стека. Вычисление осуществляется путем обработки постфиксного представления слева направо, причем каждый операнд помещается в стек в том порядке, в каком он встречается. Если встречается k-арная операция, то ее самый левый аргумент – это (k-1)-я позиция ниже вершины в стеке, а самый правый находится в вершине стека. Операция применяется к верхним k величинам стека, операнды выталкиваются, результат кладется в стек.

L-values и R-values

Имеются отличия в значении идентификаторов слева и справа от знка присваивания. Величины, стоящие справа (r-values) – это, действительно, величины, в то время как величины стоящие слева (l-values) – это адреса, в которых должны быть сохранены r-values.

Манипуляции со стеком

Кроме очевидных команд помещения в стек целочисленных констант и извлечения величины из стека, имеются команды доступа к данным в памяти:

      push v          поместить v в стек
      rvalue l        поместить в стек значение l
      lvalue l        поместить в стек адрес l
      pop             извлечь величину в вершине стека
      :=              величина в вершине помещается по адресу,
                      расположенному под вершиной, оба выталкиваются
      copy            положить в стек копию величины из его вершины

3. ЛЕКСИЧЕСКИЙ АНАЛИЗ

3.1. Роль лексического анализатора

Лексический анализ – первая фаза компиляции. Его основная задача – прочитывать входные символы и выдавать последовательность терминальных символов языка для синтаксический анализатора. Иногда лексический анализатор разделяют на две фазы: сканирование и собственно лексический анализ.

Имеется несколько причин для разделения стадии анализа компиляции на лексический анализ и синтаксический анализ:

1. Такое разделение часто позволяет нам упростить одну из этих стадий. Если мы разрабатываем новый яхык, разделение лексических (языковых) и синтаксических (правил правописания) приводи к более ясному структуре языка в целом.

2. Улучшается эффективность компилятора. Отдельный лексический анализатор позволяет нам строить специализированный и более эффективный обработчик для задачи. Много времени тратится при чтении исходной программы и разбиения ее на лексемы. Особая техника буферизации для чтения входных символов и обработки лексем может значительно ускорить быстродействие компилятора.

3. Расширяется переносимость компилятора. Особенности входного алфавита и другие, зависящие от устройства ввода аномалии затрагивают только лексический анализатор.

Разработаны специализированные средства облегчающие автоматизацию разработки лексических и синтаксических анализаторов, когда они отделены друг от друга.

Символы, шаблоны, лексемы

В общем случае есть множество входных строк, для которых лексический анализатор выдает один и тот же соответствующий им терминальный символ языка (понятие, token). Это множество строк задается шаблоном, связанным с данным символом языка. Говорится, что шаблон соответствует (match) каждой строке множества. Лексема – это цепочка символов входной программы, соответствующая шаблону для символа.

Символы       Примеры лексем      Неформальное описание шаблона
(tokens)

const         const               const
if            if                  if
relation      <, <=, =            < ИЛИ <= ИЛИ = ИЛИ <> или >= или >
id            pi, count, D2       буква со следующими за ней буквами и цифрами
num           3.1416, 6.02E23     любая целочисленная константа

Шаблон – это правило, описывающее множество лексем. Шаблон для символа const – это единственная строка const, повторяющая ключевое слово. Шаблон для символа relation есть множество всех шести отношений Паскаля. Для точного описания шаблонов более сложных символов, таких как id или num используется нотация регулярных выражений.

3.2 Буферизация ввода

[пропущено]

3.3 Описание терминальных символов

Операции над языками

Пусть L и M – языки. Определим следующие операции над этими языками:

Объединение             L И M = {s | (s О L) Ъ (s О M)}
Конкатенация            LM = {st | (s О  L) & (t О  M)}
                        L0 = {e}
                        Li = Li-1 L
Замыкание               L* = И Li, i=0.. Ґ 
Позитивное замыкание    L+ = И Li, i=1.. Ґ 

Пример 3.2

Пусть L = {A, B, ..., Z, a, b, ..., z}, D = {0, 1, ..., 9}

Каковы множества L U D, LD, L^4, L*, L(L U D), D+ ?

Регулярные выражения

Идентификаторы Паскаля – это

      буква  (буква | цифра)*

Вертикальная черта обозначает здесь "или", скобки используются для группирования подвыражений, звездочка означает "ноль или более появлений" выражения в скобках, а расположение символа буква и остатка выражения означает конкатенацию.

Регулярное выражение (РВ) строится из более более простых по правилам определения. РВ r обозначает некоторый язык L(r).

Определение регулярных выражений над алфавитом S:

   РВ                                Обозначаемый язык
------------------------------------------------------------------------
1. e                                 {e}
2. a О S                      {a} 
3. (r и s – некоторые РВ)
   (r) | (s)                         L(r) U L(s)
   (r)(s)                            L(r) L(s)
   (r)*                              (L(r))*
   (r)                               L(r)
------------------------------------------------------------------------

Регулярное множество (РМ) – это язык, обозначаемый регулярным выражением. При записи РВ мы принимаем следующие соглашения об операциях:

1. * – наивысший приоритет, левоассоциативная

2. конкатенация левоассоциативна

3. | – низший приоритет, левоассоциативная

При таких соглашениях (a)|((b)*(c)) эквивалентно a|b*c (что означает?) Если РВ r и s обозначают один и тот же язык, то мы говорим, что они эквивалентны и записываем это как r = s.

Пример 3.3. Пусть \Sigma = {a, b}.

1. РВ a|b обозначает РМ {a, b}

2. (a|b)(a|b) = aa | bb | ab | ba = {aa, ab, ba, bb} 

3. aa*bb* --> a..ab..b

4. (a|b)* = (a*b*)* --> все строки из a и b

5. a | a*b

Некоторые алгебраические свойства РВ:

	      r | s = s | r
	r | (s | t) = (r | s) | t
            (rs)t = r(st) 
         r(s | t) = rs | rt
         (s | t)r = sr | st
               er = r       
               re = r       
               r* = (r | e)*
              r** = r*

Регулярные определения

Для удобства обозначений мы могли бы давать имена для РВ и определять РВ с использованием этих имен как если бы они были символами. Если S – алфавит основных символов, то регулярное определение (РО) есть последовательность определений вида

	d1 -> r1
	d2 -> r2
	...
	dn -> rn

где каждое d_i – различное имя, r_i есть РВ над алфавитом S И {d₁, d₂, ..., d _i-1}}

	  цифра -> 0 | 1 | ... | 9
	  цифры -> цифра цифра*
	  дробь -> . цифры | e
	степень -> ( E (+ | – | e) цифры ) | e
	  число -> цифры дробь степень

Сокращения в обозначениях

Некоторые элементы встречаются так часто в РВ, что удобно ввести для них сокращения в обозначениях. Пусть r – РВ.

1. Один или более.
(r)+ = (L(r))+
Это унарный постфиксный оператор того же приоритета и ассоциативности, что и оператор *. Связь с последним: r+ = rr*, r* = r+ | e.

2. Один или ни одного.
r? = r | e, (r)? = L(r) U {e}.

Перепишем определение примера 3.5 с помощью операторов + и ?:

	  цифра -> 0 | 1 | ... | 9
	  цифры -> цифра+ 
	  дробь -> (. цифры)?
	степень -> ( E (+ | -)? цифры )?
	  число -> цифры дробь степень
 

3. Классы символов.

[abc] = a | b | c
[a-z] = a | b | ... | z

С помощью классов символов идентификаторы описываются как [A-Za-z][A-Za-z0-9]*

Нерегулярные множества

Некоторые языки не могут быть описаны РВ. РВ используются только для обозначения фиксированного или произвольного числа повторений заданного выражения. С помощью РВ нельзя описать сбалансированные выражения. Это, однако можно сделать при помощи КСГ. Повторяющиеся строки, например, множество

	{wcw | w = (a | b)*}

нельзя описaть ни РВ, ни КСГ.

Другой пример нерегулярного множества – строка Холлерита вида

	nHa1 ... an

Построение минимального ДКА

В начале разбиение состоит из двух классов эквивалентности: завершающие состояния и все остальные. Основной шаг заключается в том, что некоторого класса A = {s1, s2, ... , sk} и некоторого входного символа мы определяем, к каким состояниям есть переходы у состояний s1, s2, ... , sk. Если новые состояния из разных классов эквивалентности, то мы должны разбить A таким образом, чтобы переходы из двух подмножеств А были к состояниям из одного класса в текущем разбиении. Пусть, к примеру, (s1, aw) |- (t1, w) и (s2, aw) |- (t2, w), причем t₁ и t₂ – из двух разных классов нашего разбиения. Тогда мы должны разбить А на как минимум два подмножества, одно из которых содержит s₁, другое s₂. Обратите внимание, что если t₁ и t₂ различаются некоторой строкой w, то s₁ и s₂ различаются строкой aw.

Мы повторяем этот процесс до тех пор пока в текущем разбиении не будет классов, которые понадобилось бы разбивать еще.

Факт: если после окончания данного процесса два состояния окажутся эквивалентными, то они не различаются никакой входной строкой.

Факт: Если по окончании разбиения построить ДКА, взяв в качестве его состояний получившиеся классы эквивалентности и исключив зацикливающие состояния и состояния, недостижимые из стартового, то полученный автомат будет иметь не больше состояний, чем любой автомат, допускающий тот же самый язык.

Алгоритм 3.6. Минимизация числа состояний ДКА

Вход: ДКА М = {S, S, d, s₀, F} Выход: ДКА М' = {S', S, d, s₀', F'},
имеющий минимальное число состояний, такой, что L(M) = L(M').

Метод.

1. Начальное разбиение П = F, S\F.

2. Для получения нового разбиения П' применить следующий алгоритм:

Для каждого класса G из П выполнять
    разбить G на подклассы Gi такие,
       что любые s, t ОG попадают в
       один класс Gi тогда и только тогда, когда для каждого входного символа a 
       d(s, a) = s', 
       d(t, a) = t' и 
       s', t' ОG' О П
    заменить G в П' множеством полученных подклассов Gi
конец

3. Если П' = П, то П_f = П и дальше выполняется шаг 4. В противном случае П := П' и повторить шаг 2.

4. Выбрать по одному состоянию s в каждом классе из П_f как представителя этого класса. Класс, будем записывать через его представителя как [s]. Множество состояний S' есть классы из П_f. Пусть [s] ОП_f и d(s, a) = t, причем t О[r]. Тогда положим d([s], a) = [r]. Пусть s₀ О [s], тогда s₀' = [s]. Классы П_f суть состояния приведенного ДКА М'. Если [f] ОП_f такой, что f ОF, то [f] – конечное состояние автомата M'.

5. Последний шаг – удаление зацикливающих состояний и состояний, недостижимых из стартового.

Дата последней модификации: 15 октября 2000 г.