Грамматика языка программирования является формальным описанием его синтаксиса или формы, в которой записаны отдельные предложения программы или вся программа. Грамматика не описывает семантику или значения различных предложений. Информация о семантике содержится в программах генерации объектного кода. В качестве иллюстрации различия между синтаксисом и семантикой рассмотрим два предложения
I:=J+K
и
I:=X+Y
где Х и Y являются действительными переменными, а I, J и K —целыми переменными. Эти два предложения имеют одинаковый синтаксис. Оба являются операторами присваивания в которых присваиваемое значение определяется выражением состоящим из двух имен переменных, разделенных оператором сложения. Однако семантика этих двух предложений совершенно различна. Первое предложение говорит о том, что переменные в выражении должны быть сложены с использованием целых арифметических операций, а результат сложения должен быть присвоен переменной I. Второе предложение задает сложение с плавающей точкой, результат которого должен быть преобразован в целое число перед присваиванием. Очевидно, эти два предложения будут скомпилированы в совершенно различные последовательности машинных команд, хотя их грамматическое описание одинаково. Различия между ними проявятся на этапе генерации объектного кода.
Существует несколько различных форм записи грамматик, среди которых мы рассмотрим форму Бекуса—Наура (БНФ). БНФ не самое мощное из известных средств описания синтаксиса. Фактически она даже не является вполне адекватной для описания некоторых реально существующих языков программирования. Однако эта скорма достаточно проста, широко используется и предоставляет достаточные для большинства приложений средства. На рис. 2 изображена одна из возможных грамматик БНФ для очень узкого подмножества языка Паскаль. Полное описание грамматики БНФ для Паскаля содержится в книге Йенсен [1974]. В этом разделе нам осталось обсудить эту грамматику и показать, как она связана с примером программы, изображенным на рис. 1.
Грамматика БНФ состоит из множества правил вывода, каждое из которых определяет синтаксис некоторой конструкции языка программирования. Рассмотрим, например, правило 13 на рис. 2:
<read> ::= READ ( <id-list> )
Это определение синтаксиса предложения READ языка Паскаль, обозначенное в грамматике как <read>. Символ ::= можно читать как «является по определению». С левой стороны от этого символа находится определяемая конструкция языка (в нашем случае— <read>), а с правой—описание синтаксиса этой конструкции. Строки символов, заключенные в угловые скобки < и >, называются нетерминальными символами (т. е. являются именами конструкций, определенными внутри грамматики). То что не заключено в угловые скобки, называется терминальным символами грамматики (лексемами). В этом правиле вывод нетерминальными символами являются <read> и <id—list>. Терминальными символами являются лексемы READ, (, ). Таки образом, это правило определяет, что конструкция <read> состоит из лексемы READ, за которой следует лексема (, за ней следует конструкция языка, называемая (id—list), за которой следует лексема ). Пробелы при описании грамматически правил не существенны и вставляются только для наглядности
Для распознавания нетерминального символа <read> необходимо чтобы было определение для нетерминального символ <id—list>. Это определение дается правилом 6 на рис. 2:
<id-list> ::= id | <id-list> , id
Это правило предлагает две возможности, разделенные символом |, для синтаксиса нетерминального символа <id—list>. Первая возможность состоит в том, что <id—list> состоит просто из лексемы id (запись id означает идентификатор, распознаваемый сканером). Другой вариант состоит в том, что <id—list> состоит из <id—list>, за которым следует лексема «,», за которой следует лексема id. Обратите внимание, что это правило является рекурсивным. Это означает, что конструкция <id—list> определяется фактически в терминах себя самой. Рассмотрев несколько примеров, вы убедитесь, что в соответствии с этим правилом, нетерминальным символом <id—list> является любая последовательность из одной или более лексем id, разделенных запятыми. Таким образом,
ALPHA
является нетерминальным символом <id—list>, состоящим из единственного идентификатора ALPHA;
ALPHA, BETA
также являются конструкцией <id—list>, состоящей из конструкции <id—list> ALPHA, за которой следует «,», за которой идет идентификатор BETA и т. д.
Результат анализа исходного предложения в терминах грамматических конструкций удобно представлять в виде дерева. Такие деревья обычно называют деревьями грамматического разбора или синтаксическими деревьями. На рис. За изображено дерево грамматического разбора для предложения
READ (VALUE)
с использованием только что обсужденных двух правил вывода.
Правило вывода 9 на рис. 2 дает определение синтаксиса предложения присваивания:
<assign> ::= id :== <exp>
Это означает, что конструкция (assign) состоит из лексемы id, за которой следует лексема :=, за которой идет конструкция <eхр>. Правило 10 дает определение конструкции <eхр>:
<ехр> ::= <term> | <exp>+<term> | <exp>—<term>
Используя те же соображения, что и при анализе конструкции <id—list>, мы видим, что это правило определяет конструкцию <ехр> как состоящую из любой последовательности конструкций <term>, соединенных операторами плюс или минус. Аналогично правило 11 определяет конструкцию <term> как последовательность конструкций <factor>, разделенных, знаками * или DIV. В соответствии с правилом 12 конструкция <factor> может состоять из идентификатора id или целого int, которое также распознается сканером, или из конструкции <ехр>, заключенной в круглые скобки.
На рис. 3б изображено дерево грамматического разбора для предложения 14 на рис. 1, основанное на только что рассмотренных правилах вывода. Вы должны внимательно изучить этот рисунок, чтобы убедиться в правильном понимании того, как выполняется грамматический анализ исходного предложения на основании введенных грамматических правил.
Обратите внимание, что в соответствии с деревом грамматического разбора на рис. 3б умножение и деление производятся перед сложением или вычитанием. Прежде всего должны вычисляться термы SUMSQ DIV 100 и MEAN*MEAN, поскольку эти промежуточные результаты являются операндами (левым и правым поддеревом) операции вычитания. Иначе то же самое можно выразить, сказав, что операции умножения и деления имеют более высокий ранг (precedence), чем операции сложения и вычитания. Такое ранжирование операций является следствием того, как записаны правила 10—12. В разд. 3 мы увидим, как подобное ранжирование может быть использовано при осуществлении процесса грамматического разбора.
Дерево грамматического разбора на рис. 3 представляет собой единственно возможный результат анализа этих двух предложений в терминах грамматики, изображенной на рис. 2. Для некоторых грамматик подобной единственности может не существовать. Если для одного и того же предложения можно построить несколько различных деревьев грамматического разбора, то соответствующая грамматика называется неоднозначной (ambiguous). При разработке компиляторов обычно предпочитают пользоваться однозначными грамматиками, поскольку в некоторых случаях неоднозначная грамматика оставляет сомнения относительно того, какой объектный код должен быть сгенерирован для анализируемого предложения.
0 коммент.:
Отправить комментарий