Устранение левой (правой) рекурсии

КС-грамматика в нормальной форме Грейбах

Определение: В КС-грамматике символ называется рекурсивным, если для него существует вывод вида

.

Определение: Если в КС-грамматике существует вывод вида

,

где

, ,

то такая рекурсия называется левой, соответственно символ называется леворекурсивным.

Определение: Если в КС-грамматике существует вывод вида

,

где

, ,

то такая рекурсия называется правой, а символ называется праворекурсивным.

Определение: В КС-грамматике существует вывод вида . Если и , то имеет место цикл (цепные правила).

Определение: Грамматика , в которой имеется левая (правая) рекурсия относительно хотя бы одного нетерминала, называется леворекурсивной (праворекурсивной).

Определение: Грамматика , в которой отсутствует левая (правая) рекурсия относительно любого нетерминала, называется нелеворекурсивной (неправорекурсивной).

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