Достоинством восходящего метода является его несомненная простота, а также высокая скорость выполнения (не тратится время на поиск правила редукции).
Однако все эти достоинства напрочь меркнут перед главным недостатком данного метода. Дело в том, что здесь практически отсутствует какая бы то ни была диагностика (и тем более - локализация) ошибок. Во вторых, некоторые ошибки в исходном выражении не диагностируются вовсе. Например, выражения, в которых встречаются идущие подряд скобки “(” и “)”.
Поэтому при дальнейшем рассмотрении будет рассматриваться нисходящий разбор, как наиболее пригодный метод при ручном написании компилятора [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>
11. <term> ::= <factor> DIV <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. Такая запись устраняет проблему левой рекурсии.
Возможны различные формы внутреннего представления синтаксических конструкций исходной программы в компиляторе. Дерево грамматического разбора оказывается неудобным в работе при работе при генерации и оптимизации объектного кода. Поэтому перед оптимизацией и непосредственно генерацией объектного кода внутреннее представление программы преобразуется в одну из соответствующих форм записи.
Примерами таких форм записи являются:
- обратная польская запись операций;
- тетрады операций;
- триады операций;
- собственно команды ассемблера.
Обратная польская запись - это постфиксная запись операций. Преимуществом ее является то, что все операции записываются непосредственно в порядке их выполнения. Она чрезвычайно эффективна в тех случаях, когда для вычислений используется стек.
Тетрады представляют собой запись операций в форме из четырех составляющих:
<операция>(<операнд1>,<операнд2>,<результат>).
Тетрады используются редко, так как требуют больше памяти для своего представления, чем триады, не отражают взаимосвязи операций и, кроме того, плохо отображаются в команды ассемблера и машинные коды, так как в наборах команд большинства современных машин не встречаются операции с тремя операндами.
Триады представляют собой запись операций в форме из трех составляющих: <операция>(<операнд1>,<операнд2>), при этом один или оба операнда могут быть ссылками на другую триаду в том случае, если в качестве операнда данной триады выступает результат выполнения другой триады. Поэтому триады при записи последовательно номеруют для удобства указания ссылок одних триад на другие. Например, выражение A := B*C + D - B*10, записанное в виде триад будет иметь вид:
1) * ( B, C )
2) + ( ^1, D )
3) * ( B, 10 )
4) - ( ^2, ^3 )
5) := ( A, ^4 )
Здесь операции обозначены соответствующим знаком (при этом присвоение также является операцией), а знак ^ означает ссылку операнда одной триады на результат другой.
Команды ассемблера удобны тем, что при их использовании внутреннее представление программы полностью соответствует объектному коду и сложные преобразования не требуются. Однако использование команд ассемблера требует дополнительных структур для отображения их взаимосвязи. Кроме того, внутреннее представление программы получается зависимым от результирующего кода, а это значит, что при ориентации компилятора на другой результирующий код потребуется перестраивать как само внутреннее представление программы, так и методы его обработки в алгоритмах оптимизации (при использовании триад или тетрад этого не требуется).
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26