Порождение

Пример 10

Используя приведенные соглашения, можно записать грамматику из примера 5.2 в следующем виде:

E->E A E | (E) | -E | id

A-> +| - | * | / |

Из соглашений следует, что E и А — нетерминалы, причем E является старто­вым символом. Остальные символы представляют собой терминалы.

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

Рассмотрим, например, следующую грамматику арифметических выражений.

E->E+E | E*E | (E) | -E | id (5.3)

Продукция E-> -E означает, что выражение, которому предшествует знак минуса, также является выражением. Эта продукция может использоваться для порождения бо­лее сложных выражений из простых, позволяя заменять любой экземпляр E на –E. В простейшем случае можно заместить одно E на -E и описать это как Е=> -E. Такая запись читается, как "E порождает -E", или "из E выводится -E". Продукция E—>(E) го­ворит, что можно также заменить один экземпляр E в любой строке грамматики на (E), например E*E=>(E)*E или E*E=>E*(E).

Можно взять нетерминал E и неоднократно применять продукции в произ­вольном порядке для получения последовательности замещений, например, E => -E => -(E) => -(id). Такая последовательность замен представляет порождение (id) из E. (Символ => означает "порождает за один шаг". Символ =*> означает "порождает за нуль или более шагов". Символ =+> используется для обозначения "порождает за один или более шагов".)

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

Например, строка -(id+id) является предложением грамматики (5.3) так как существует следующее порождение

Е => -E=> -(E) => -(Е + Е)=> -(id + Е) => -(id + id) (5.4)

Строки Е, -E, -(E),..., -(id+id), появляющиеся в процессе порождения, представляют собой сентенциальные формы данной грамматики. Для указания того, что -(id+id) мо­жет быть выведено из E, можно записать E=*>-(id + id).

На каждом шаге порождения осуществляется два выбора — во-первых, выбор за­меняемого нетерминала, во-вторых, его альтернативы. Например, порождение (5.4) из приме­ра 11 может продолжиться после -(E+E) следующим образом:

-(E+E) => -(E+id) => -(id+id) (5.5)

Каждый нетерминал в (5.5) замещается той же правой частью, что и в (5.4), но в дру­гом порядке.

Дата добавления: 2014-12-27