Программно методический комплекс для обучения процессу создания компиляторов (стр. 3 из 14)

1) выделение из входной строки очередного слова;

2) поиск в таблицах лексем и определение кода лексемы;

3) формирование и вывод выходной строки.

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

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

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

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

Следующей стадией анализа является синтаксический разбор.

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

1) реализуется на основе прямого лексического анализа. От синтаксического анализатора поступает запрос «дать лексему» и указывается тип лексемы;

2) непрямой лексический анализ. Синтаксический анализатор выдает запрос «дать лексему», тип лексемы не указывается. Нет решающего блока, считаем, что работает группа параллельных автоматов.

1.4 Синтаксический и семантический анализ

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

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

Процесс синтаксического анализа может рассматриваться как построение дерева грамматического разбора для транслируемых предложений. Грамматики могут использоваться как для порождения так и для распознавания предложений языка. Порождение начинается с начального понятия (или аксиомы грамматики). При распознавании с помощью грамматических правил порождается предложение, которое затем сравнивается с входной строкой. При этом применение правил подстановки для порождения очередного символа предложения зависит от результатов сравнения предыдущих символов с соответствующими символами входной строки. Результат анализа исходного предложения в терминах грамматических конструкций удобно представлять в виде дерева. Такие деревья обычно называются деревьями грамматического разбора или синтаксическими деревьями. На рисунке 3 изображено дерево грамматического разбора для предложения READ (VALUE).

Рисунок 3 – Дерево грамматического разбора

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

Достоинством восходящего метода является его несомненная простота, а также высокая скорость выполнения (не тратится время на поиск правила редукции).

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

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

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

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

В дальнейшем мы будем работать с синтаксически-неориентированными алгоритмами, т.к. будем работать лишь с одним языком – учебный язык на основе языка Паскаль.

1.5 Грамматики

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

I:=J+K

I:=X+Y

где Х и Y являются действительными переменными, aI, J, К — целыми переменными. Эти два предложения имеют одинаковый синтаксис. Оба являются операторами присваивания, в которых присваиваемое значение определяется выражением, состоящим из двух имен переменных, разделенных оператором сложения. Однако семантика этих двух предложений совершенно различна. Первое предложение говорит о том, что переменные в выражении должны быть сложены с использованием целых арифметических операций, а результат сложения должен быть присвоен переменной I. Второе предложение задает сложение с плавающей точкой, результат которого должен быть преобразован в целое число перед присваиванием. Очевидно, эти два предложения будут скомпилированы в различные последовательности машинных команд, хотя их грамматическое описание одинаково. Различия между ними проявятся на этапе генерации объектного кода.

На рисунке 4 показаны БНФ грамматики, используемые в дипломном проекте. Подчеркнутые волнистой линией элементы могут опускаться (не использоваться).

1. <prog> ::= PROGRAM <prog-name>VAR <dec-list> BEGIN <stmt-list> END.

2. <prog-name> ::= id ;

3. <dec-list> ::= <dec> { ; <dec> } ;

4. <dec> ::= <id-list> : <type>

5. <type> ::= INTEGER | REAL | STRING

6. <id-list> ::= id { , id }

7. <stmt-list> ::= <stmt> { ; <stmt> } ;

9. <assign> ::= id := <exp>

10. <exp> ::= – <term> { + <term> | – <term> }

11. <term> ::= <factor> { * <factor> | DIV <factor> | / <factor> }

12. <factor> ::= id | int | real | <text-val> | (<exp>)

13. <read> ::= READ ( <id-list> )

14. <write> ::= WRITE ( <value> { , <value>} )

15. <for> ::= FOR <index-exp> DO <body>

16. <index-exp> ::= id := <exp> TO|DOWNTO <exp>

17. <body> ::= <stmt> | BEGIN <stmt-list> END

18. <value> ::= <id-list> | <text-val>

19. <text-val> ::= ′ <text> ′

20. <text> ::= string

21. <if> ::= IF <сравнение> THEN <body> ELSE <body>

22. <сравнение>::= <factor> <условие> <factor>

23. <условие> ::= > | < | = | >= | <= | <>

24. <while> ::= WHILE <сравнение> DO <body>

25. <repeat> ::= REPEAT <body> UNTIL <сравнение>

Рисунок 4 – Упрощенная грамматика языка Паскаль

Существует несколько различных форм записи грамматик, среди которых мы рассмотрим форму Бекуса—Наура (БНФ). БНФ не самое мощное из известных средств описания синтаксиса. Однако эта форма достаточно проста, широко используется и предоставляет достаточные для большинства приложений средства. На рис.4 изображена одна из возможных грамматик БНФ.

Грамматика БНФ состоит из множества правил вывода, каждое из которых определяет синтаксис некоторой конструкции языка программирования. Рассмотрим, например, правило 13 на рис. 4:

<read> ::= READ ( <id-list> )

Это определение синтаксиса предложения READ языка Паскаль, обозначенное в грамматике как <read>. Символ ::= можно читать как «является по определению». С левой стороны от этого символа находится определяемая конструкция языка (в нашем случае— <read>), а с правой—описание синтаксиса этой конструкции. Строки символов, заключенные в угловые скобки < и >, называются нетерминальными символами (т. е. являются именами конструкций, определенными внутри грамматики). То, что не заключено в угловые скобки, называется терминальными символами грамматики (лексемами). В этом правиле вывода нетерминальными символами являются <read> и <id—list>. Терминальными символами являются лексемы READ, (, ). Таким образом, это правило определяет, что конструкция <read> состоит из лексемы READ, за которой следует лексема (, за ней следует конструкция языка, называемая <id—list>, за которой следует лексема ). Пробелы при описании грамматических правил не существенны и вставляются только для наглядности.