Представление синтаксиса в формальных грамматиках

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

Нетерминальный символ – обозначение элемента синтаксиса и места его вхождения (подстановки) в другие элементы синтаксиса.

Кроме нетерминалов, явно обозначающих синтаксические единицы, для многих элементов синтаксиса используются вспомогательные нетерминалы. Иногда они вводятся, исходя из «технологических=> соображений для придания грамматикам необходимых свойств (см. конфликты «свертка-перенос=>)

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

Повторение. Построение повторяющихся цепочек базируется на известном свойстве: линейная (не ветвящаяся) рекурсия эквивалента циклу. В отношении ФГ это означает, что нетерминал, “отвечающий за повторение”, непосредственно или косвенно рекурсивен. Остальные символы правил являются элементами повторения. Завершение процесса повторения должно сопровождаться применением правила, не содержащего такой рекурсии. В качестве примера рассмотрим определение идентификатора:

I:: LX

X:: e завершение повторения

X:: LX | DX повторение – прямая рекурсия

L:: a |…| z

D:: 0 |…| 9

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

E:: T{ +T | -T } цепочка сложений/вычитаний

C:: (D) десятичная константа

I:: L{ L | D } идентификатор

Вложенность. Принцип вложенности одних синтаксических конструкций в другие естественным образом реализуется в ФГ: нетерминал в левой части правила обозначает синтаксическую единицу, которая “расшифровывается” правой частью, нетерминалы в правой части обозначают “вложенные” элементы синтаксиса. Вложенность может быть и рекурсивной, когда в определении синтаксической единицы используются (прямо или косвенно) синтаксические единицы такого же типа. Пример: синтаксис определения вложенных операторов:

O:: for(E; E; E)O | if (E)O else O | E; | {S}

S:: O | OS

Приоритеты. Наличие приоритетов в цепочке символов (операций) представляет собой не что иное, как неявную вложенность: любая цепочка операций более высокого приоритета образует синтаксическую единицу, которая входит в описание цепочки операций текущего приоритета. Поэтому для каждого уровня приоритета необходима своя группа правил, генерирующая цепочку (последовательность) таких операций. Так, например, синтаксический элемент – арифметическое выражение (нетерминал E) представляет собой группу правил для генерации последовательности операций сложения вычитания, «операндами=> в которой выступает нетерминалы следующего уровня – T. Они, в свою очередь, являются левой частью для группы правил, генерирующих последовательность операций умножения и деления для «операндов=> следующего уровня – термов (F). То есть каждый элемент суммы может (потенциально) быть произведением и т.д. Естественно, что должно быть предусмотрено прямое приведение нетерминала одного уровня к нетерминалу другого при отсутствии соответствующих операций. «Приоритетные=> скобки реализуются в виде правила, в котором нетерминал последовательности операций низшего приоритета, заключенный в скобки, сводится к нетерминалу высшего приоритета:

E:: E + T | E - T | T

T:: T * F | T / F | F

F:: a | (E)

Аналогично для грамматики, использующей аннулирующие правила:

E:: TM

M:: e | +TM | -TM

T:: FG

G:: e | *FG | /FG

F:: a | (E)

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

O:: if (E)OX

X:: else O | e оператор if с else и без него

Возможно также явное перечисление вариантов синтаксиса в правых частях правил (например, вызов функции с пустым списком параметров, единственными параметром и их последовательностью):

F:: a | a()| a(E) | a(SE)

S:: E, | SE,

Разделители. Терминальный символ-разделитель используется для “подсказки”, что вслед за ним следует еще один повторяющийся элемент синтаксиса. Таким образом, он обозначает повторение рекурсии, поэтому в грамматике, ориентированной на нисходящий разбор, за ним обычно следует рекурсивный нетерминал. Типичный пример, список, разделенный запятыми (с использованием аннулирующего правила – правила с пустой правой частью):

L:: aX

X:: e завершение списка

X::, aX продолжение списка

L => aX => a, aX => a, a, aX => a, a, a

В грамматиках, ориентированных на восходящий разбор, разделитель совместно с первым элементом перечисления (списка) используется для введения нетерминала, обозначающего незавершенный список:

L:: a | Sa S – обозначение незавершенного списка

S:: a, | Sa,

a, a, a => Sa, a => Sa => L

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

O:: {S}

S:: e завершение списка

S:: OS повторение

O => {S} => {OS} => {OOS} => {OOOS} => {OOO}