Определение синтаксиса

В этом разделе для определения синтаксиса языка будет рассмотрен способ записи, называемый контекстно-свободной грамматикой (или, для краткости, просто граммати­кой). Данный способ будет использоваться как часть спецификации предварительной стадии компилятора на протяжении всей книги.

Грамматика естественным образом описывает иерархическую структуру множества конструкций языка программирования. Например, инструкция if-else в С имеет вид

if (выражение) инструкция else инструкция

Таким образом, инструкция if-else представляет собой ключевое слово if, за которым следует открывающая круглая скобка, выражение, закрывающая скобка, инструкция, ключевое слово else и еще одна инструкция (в С нет ключевого слова then). Используя переменную ехрг для обозначения выражения и переменную stmt для обозначения инст­рукции, можно записать это структурное правило так:

stmt → if (ехрг) stmt else stmt (2.1)

Здесь символ (→) можно прочесть как "может иметь вид". Такое правило называется продукцией (production). В продукции лексические элементы вроде ключевого слова if и скобок называются токенами. Переменные типа ехрг и stmt представляют последова­тельности токенов[6] и называются нетерминальными символами, или просто нетермина­лами (nonterminals).

Контекстно-свободная грамматика имеет четыре компонента.

1. Множество токенов, представляющих собой терминальные символы (или просто терминалы).

2. Множество нетерминальных символов.

3. Множество продукций, каждая из которых состоит из нетерминала, называемого ле­вой частью продукции, стрелки и последовательности токенов и/или нетерминалов, называемых правой частью продукции.

4. Указание одного из нетерминальных символов как стартового, или начального.

Следует придерживаться правила, согласно которому грамматика определяется пере­числением ее продукций, причем первая продукция указывает стартовый символ. Цифры, знаки вроде <= и выделенные полужирным шрифтом слова типа while являются тер­минальными символами. Выделенные курсивом слова являются нетерминалами, а все слова или символы, поданные без выделения, могут рассматриваться как токены[7]. Для удобства записи правые части продукций с одними и теми же нетерминалами слева мо­гут быть сгруппированы с помощью символа "|" ("или").

Пример 2.1

В примерах этой главы используются выражения, состоящие из цифр и знаков "плюс" и "минус", например 9-5+2, 3-1 или 7. Поскольку знаки "плюс" и "минус" должны располагаться между двумя цифрами, такие выражения можно рассматривать как списки цифр, разделенных знаками "плюс" и "минус". Синтаксис используемых вы­ражений описывает грамматика из следующих продукций:

list → list + digit (2.2)

list → list - digit (2.3)

list → digit (2.4)

digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (2.5)

Правые части трех продукций с нетерминалом list в левой части могут быть объединены:

list —> list + digit | list - digit | digit

Здесь, в соответствии с нашими соглашениями, токенами грамматики являются символы

+ - 0123456789

Нетерминальными символами являются выделенные курсивом имена list и digit, при этом нетерминал list — стартовый; именно его продукция дана первой. □

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

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

Пример 2.2

Язык, определяемый грамматикой из примера 2.1, состоит из списков цифр, разде­ленных знаками "плюс" и "минус".

Десять продукций для нетерминала digit позволяют ему быть любым из токенов О, 1, 9. Из продукции (2.4) следует, что список может состоять и из одной цифры, т.е. цифра сама по себе является списком. Продукции (2.2) и (2.3) выражают тот факт, что если мы возьмем любой список и добавим к нему знак "плюс" или "минус" с после­дующей цифрой, то получим новый список.

Оказывается, что продукции (2.2) - (2.5) — все, что надо для определения языка. На­пример, можно сделать вывод, что 9-5+2 является списком, следующим образом.

1. 9 — список в соответствии с продукцией (2.4), поскольку 9 — цифра.

2. 9-5 — список в соответствии с продукцией (2.3), так как 9 — список, а 5 — цифра.

3. 9-5+2— список в соответствии с продукцией (2.2), поскольку 9-5— список, а 2 — цифра.

Данное утверждение продемонстрируем деревом, представленным на рис. 2.2. Каж­дый узел дерева помечен символом грамматики. Внутренний узел и его дочерние узлы соответствуют продукции, причем узел соответствует левой части продукции, а потом­ки — правой. Такие деревья называются деревьями разбора (parse trees); они будут рас­смотрены ниже. □

list

digit

digit

-

+

list

list

digit

Рис. 2.2. Дерево разбора выражения 9-5+2 в соответствии с грамматикой из примера 2.1

Пример 2.3

Еще один пример списков — последовательность инструкций, разделенных точками с запятыми; такую последовательность можно найти в Pascal, в блоке begin-end. Однако между токенами begin и end может и не быть инструкций. Разработку грамматики для блока begin-end можно начать со следующих продукций:

block → begin opt stmts end

opt_stmts → stmt_list | ε

stmt_list → stmt_list; stmt | stmt

Заметьте, что правой частью для opt_stmts может являться е, т.е. пустая строка сим­волов. Таким образом, opt_stmts может быть заменено пустой строкой, и блок может ока­заться строкой из двух токенов begin end. Обратите также внимание, что продукции для stm_list аналогичны продукциям для list в примере 2.1 (точка с запятой вместо арифме­тической операции и с stmt вместо digit). В данном примере не представлены продукции для stmt, но далее вкратце будут рассмотрены продукции для различных инструкций, та­ких как инструкции присвоения, инструкции if и др. □

Дата добавления: 2015-11-30