Программно-методический комплекс для обучения процессу создания компиляторов
Рефераты >> Программирование и компьютеры >> Программно-методический комплекс для обучения процессу создания компиляторов

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

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

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

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

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

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

1.5 Грамматики

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

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. Такая запись устраняет проблему левой рекурсии.


Страница: