Левые и правые порождения

Язык, определяемый грамматикой

Если - КС-грамматика, то язык, определяемый грамматикой , обозначается и представляет собой множество терминальных строк, порождаемых из начального символа грамматики. Таким образом,

.

Если язык определяется некоторой КС-грамматикой, то он называется контекстно-свободным, или КС- языком.

На каждом шаге порождения осуществляются два выбора:

Выбирается переменная, которая будет заменена телом одного из своих правил;

Для выбранной переменной выбирается правило, правая часть которого подставляется вместо переменной.

Для уменьшения числа выборов потребуем, чтобы на каждом шаге порождения заменяли крайнюю слева переменную одним из тел ее правил. Такие порождения называются левыми (leftmost, lm) и для его указания используются обозначения .

Аналогично можно потребовать, чтобы на каждом шаге заменялась крайняя справа переменная. Такие порождения называются правыми (rightmost, rm) и для его указания используются обозначения .

Любое порождение имеет эквивалентные левое и правое порождение. Это означает, если терминальная строка, переменная, то , а так же.

Дата добавления: 2013-12-14