14. Нормальная формула Грейбах

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

Определение.

Нетерминал А в КС–грамматике G = (N,  Р S) называется рекурсивным, если А + A для некоторых  и . Если  = е, то А называется леворекурсивным. Аналогично, если  = е, то А называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный терминал, называется леворекурсивной. Аналогично определяется и праворекурсивная грамматика. Грамматика, в которой все не терминалы, кроме может быть начального символа, рекурсивные называется рекурсивной грамматикой.

Практически все языки программирования определяются нелеворекурсивной грамматикой. Поэтому все элементы левой рекурсии должны быть устранены из грамматики.

Пусть G = (N,  Р S) – КС–грамматика, в которой

- все правила из Р и ни одна из цепочек не начинается сА.

Пусть G'=(N