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

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

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

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

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

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

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

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

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

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

Грамматики

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

I:=J+K

и

I:=X+Y

где Х и Y являются действительными переменными, a I, 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> }  ;

8. <stmt>   ::= <assign> | <for> | <read> | <write> | <while> | <repeat> | <if>

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>, за ко­торой следует лексема ). Пробелы при описании грамматических правил не существенны и вставляются только для наглядности.

Для распознавания нетерминального символа <read> необ­ходимо чтобы было определение для нетерминального символа <id-list>. Это определение дается правилом 6 на рис. 4:

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

Эта нотация, означает, что конструкция, заключенная в фигурные скобки, может быть либо опущена, либо повторяться один или более число раз. Таким образом, правило 6 определяет нетерминаль­ный символ <id-list> как состоящий из единственной лексемы id или же из произвольного числа следующих друг за другом лексем id, разделенных запятой. В соответствии с этим новым определением процедура, соответствующая нетерминальному символу <id-list>, сначала ищет лексему id, а затем продолжает сканировать входной текст до тех пор, пока следующая пара лексем не совпадет с запятой и id. Такая запись устраняет проблему левой рекурсии.