Формальные грамматики

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

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

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

Формальная грамматика G есть четверка G=(N,T,E,P), где N – множество нетерминальных символов, T – множество терминальных символов, E – начальный символ, P – множество продукций, и

Каждая новая строка в процессе вывода должна получаться из уже выведенной строки применением продукции.

Предложение – это строка, состоящая только из терминальных символов, выводимая из начального символа.

Язык L, определяемый грамматикой G, есть множество предложений, выводимых в G из L: .

Дата добавления: 2014-01-06