Джек Креншоу - Давайте создадим компилятор!

• Название: Давайте создадим компилятор!
• Автор: Джек Креншоу
• Жанр: Программирование

Эта серия, написанная в период с 1988 по 1995 года и состоящая из шестнадцати частей, является нетехническим введением в конструирование компиляторов. Серия является руководством по теории и практике разработки синтаксических анализаторов и компиляторов языков программирования. До того как вы закончите чтение этой книги, вы раскроете каждый аспект конструирования компиляторов, разработаете новый язык программирования и создадите работающий компилятор.

---

IF a AND NOT b THEN ....

Но более часто мы видим, что булева алгебра появляется в таком виде:

IF (x >= 0) and (x <= 100) THEN...

Здесь два условия в скобках являются булевыми выражениями, но индивидуальные сравниваемые термы: x, 0 и 100 являются числовыми по своей природе. Операторы отношений >= и <= являются катализаторами, с помощью которых булевские и арифметические компоненты объединяются вместе.

Теперь, в примере выше сравниваемые термы являются просто термами. Однако, в общем случае, каждая сторона может быть математическим выражением. Поэтому мы можем определить отношение как:

<relation> ::= <expression> <relop> <expression>,

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

=, <> (или !=), <, >, <= и >=

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

<b-factor> ::= <b-literal>

| <b-variable>

| (<b-expression>)

| <relation>

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

Уровень Синтаксический элемент Оператор

0 factor literal, variable

1 signed factor unary minus

2 term *, /

3 expression +, -

4 b-factor literal, variable, relop

5 not-factor NOT

6 b-term AND

7 b-expression OR, XOR

Если мы захотим принять столько уровней приоритета, эта грамматика кажется приемлемой. К несчастью, она не будет работать! Грамматика может быть великолепной в теории, но она может совсем не иметь смысла в практике нисходящего синтаксического анализатора. Чтобы увидеть проблему рассмотрите следующий фрагмент кода:

IF ((((((A + B + C) < 0 ) AND....

Когда синтаксический анализатор анализирует этот код он знает, что после того, как он рассмотрит токен IF следующим должно быть булево выражение. Поэтому он может приступить к началу вычисления такого выражения. Но первое выражение в примере является арифметическим выражением A + B + C. Хуже того, в точке, в которой анализатор прочитал значительную часть входной строки:

IF ((((((A ,

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

Происходит то, что красота и элегантность грамматики БНФ столкнулась лицом к лицу с реальностью технологии компиляции.

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

Исправление грамматики

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

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

Когда Никлаус Вирт разработал Паскаль, его желанием было ограничить количество уровней приоритета (меньше подпрограмм синтаксического анализа, в конце концов). Так операторы OR и исключающее OR рассматриваются просто как Addop и обрабатываются на уровне математического выражения. Аналогично AND рассматривается подобно Mulop и обрабатывается с Term. Уровни приоритета:

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

x + (y AND NOT z) DIV 3

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

Авторы C взяли диаметрально противоположный метод: они обрабатывают операторы как разные и C имеет что-то гораздо более похожее на наши семь уровней приоритета. Фактически, в C имеется не менее 17 уровней! Дело в том, что C имеет также операторы '=', '+=' и их родственников '<<', '>>', '++', '–' и т.д. Как ни странно, хотя в C арифметические и булевые операторы обрабатываются раздельно, то переменные нет... в C нет никаких булевых или логических переменных, так что логическая проверка может быть сделана на любом целочисленном значении.

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

IF (c >= 'A') and (c <= 'Z') then ...

скобки обязательны. Я никогда не мог понять раньше почему, и ни мой компилятор, ни любой человек также не объясняли этого достаточно хорошо. Но сейчас мы все можем видеть, что оператор «and», имеющий приоритет как у оператора умножения, имеет более высокий приоритет, чем у операторов отношения, поэтому без скобок выражение эквивалентно:

IF c >= ('A' and c) <= 'Z' then

что не имеет смысла.

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

<b-expression> ::= <b-term> [<orop> <b-term>]*

<b-term> ::= <not-factor> [AND <not-factor>]*

<not-factor> ::= [NOT] <b-factor>

<b-factor> ::= <b-literal> | <b-variable> | <relation>

<relation> ::= | <expression> [<relop> <expression]

<expression> ::= <term> [<addop> <term>]*

<term> ::= <signed factor> [<mulop> factor]*

<signed factor>::= [<addop>] <factor>

<factor> ::= <integer> | <variable> | (<b-expression>)

Эта грамматика приводит к тому же самому набору семи уровней, которые я показал ранее. Действительно, это почти таже самая грамматика... я просто исключил заключенное в скобки b-выражение как возможный b-показатель и добавил отношение как допустимую форму b-показателя.

Есть одно тонкое, но определяющее различие, которое заставляет все это работать. Обратите внимание на квадратные скобки в определении отношения. Это означает, что relop и второе выражение являются необязательными.

Странным последствием этой грамматики (которое присутствует и в C) является то, что каждое выражения потенциально является булевым выражение. Синтаксический анализатор всегда будет искать булевское выражение, но «уладит» все до арифметического. Честно говоря, это будет замедлять синтаксический анализатор потому что он должен пройти через большее количество вызовов процедур. Это одна из причин, почему компиляторы Паскаля обычно быстрее выполяют компиляцию, чем компиляторы C. Если скорость для вас – больное место, придерживайтесь синтаксиса Паскаля.

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

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

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

{–}

{ Recognize a Boolean Literal }

function IsBoolean(c: char): Boolean;

begin

IsBoolean := UpCase(c) in ['T', 'F'];

end;

{–}

{ Get a Boolean Literal }

function GetBoolean: Boolean;

var c: char;

begin

if not IsBoolean(Look) then Expected('Boolean Literal');

GetBoolean := UpCase(Look) = 'T';

GetChar;

end;

{–}

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

WriteLn(GetBoolean);

Откомпилируйте программу и протестируйте ее. Как обычно пока не очень впечатляет но скоро будет.

Теперь, когда мы работали с числовыми данными, мы должны были организовать генерацию кода для загрузки значений в D0. Нам необходимо сделать то же самое и для булевых данных. Обычным способом кодирования булевых переменных является использование 0 для представления FALSE и какого-либо другого значения для TRUE. Многие языки, как например C, используют для его представления целое число 1. Но я предпочитаю FFFF (или -1) потому что побитовое NOT также возвратит логическое NOT. Итак, нам теперь нужно выдать правильный ассемблерный код для загрузки этих значений. Первая засечка на синтаксическом анализаторе булевых выражений (BoolExpression, конечно):