G = {N\{a, b}, Р\ S), где N-{5. А, Б, <Л£>, <ВВ>, а}, а Я состоит из правил

Sa iABy\BA

АВ<ВВу\а

B-AS[b <АВ>АВ КВВуВВ

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

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

Определение. Нетерминал А КС-грамматики G = {N, 2, Р, S)

называется рекурсивным, если АаА для некоторых а и (1 Если а-е, то А называется леворекурсивным. Аналогично, если ре, то А называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный нетерминал, называется леворекурсивной. Аналогично определяется праворекурсивная грамматика. Грамматика, в которой все нетерминалы, кроме, быть мокет, начального символа, рекурсивные, называется рекурсивной.

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

Лемма 2.15. Пусть G = (N, 2, Р, 5) - К.С-грамматика, в которой

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

G = {NU{A\, 2, Р, S)

где А - новый нетерминал, а Р получается из Р заменой А-пра-вил правилами )

Тогда L{G)=L(G).

AS.- Прим. ред.

1) Надо си;е устранить S т правой части правила В-~) Заметим, что правила А- содержатся как в исходном, так и врезультирующем множестве Л-правил.

Доказательство. Цепочки, которые можно получить в грамматике G из нетерминала А при.менением Л-правил лишь к самому левому нетерминалу, образуют регулярное множество (Pi + p2+• • -+Рп) (01 "гг "Ь • • •-г«,г.) *• 0 в точности те цепочки, которые можно получить в G из Л с помощью правых ВЫВОДОВ, применив один раз Л-правило и несколько раз Л-пра-вила. (В результате весь вывод уже не будет левым.) Все шаги вывода в G, на которых не используются Л-правила, можно непосредственно сделать в G, так как ие Л-правила в G и G одни и те же. Отсюда можно заключить, что L {G) L{G).

Обратное включение доказывается по существу так же. В G берется правый вывод и рассматриваются последовательности шагов, состоящие из одного применения Л-правила и нескольких применений Л-правил. Таким образом, L (G) -Z(G). □

На рис. 2.13 показано, как действует преобразование, описанное в лемме 2.15, на деревья выводов.

Л"

Рис. 2.13. Части деревьев: а -часть дерева вС; б -соотиетствующая часть в Q.

Пример 2.27. Пусть С -наша обычная грамматика с правилами

Е-Е-\-Т\Т

T->-T*F\F

F{E)\a

Если применить к ней конструкцию леммы 2.15, то получится эквивалентная ей грамматика С с правилами

Е -Tl+TE T-E\FT

F-.{E)\a □

Теперь мы готовы описать алгоритм, устраняющий левую рекурсию из приведенной КС-грамматики. По идее этот алгоритм подобен алгоритму решения уравнений с регулярными коэффициентами.

Алгоритм 2.13. Устранение левой рекурсии.

Вход. Приведенная КС-грамматика G = {N, 2, Р, S). Выход. Эквивалентная КС-грамматика G без левой рекурсии. Метод.

(1) Пусть N = {1, ..AJ. Преобразуем G так, чтобы в правиле А-цепочка а начиналась либо с терминала, либо с такого Лу, что />i. С этой целью положим

(2) Пусть множество Л,-правил - это ЛЛ ,.cti ... .. . Л Ipj.. .р„ где ни одна из цепочек ру не начинается с Ai, если ki. (Это всегда можно сделать.) Заменим Л,-пра-вила правилами

а.

1Р1Р,ЛП--..М

асс,Л-). . .(аЛ-

где Ai - новый нетерминал. Правые части всех Л -правил начинаются теперь с терминала или с Л;. для некоторого к > г.

(3) Если in, полученную грамматику С считать результатом и остановиться. В противном случае положить г - г--1 и / 1.

(4) Заменить каждое правило вида А- Аа правилами Л,--»-ра .. . I рс, где Л-Pi-.-Pm-все Л-правила. Так как правая часть каждого Лу-правила начинается уже с терминала или с Л. для k > /, то и правая часть каждого Л,-правила будет теперь обладать этим свойством.

(5) Если ji-l, перейти к шагу (2). В противном случае положить / = / + 1 и перейти к шагу (4). □

Теорема -2.18. Каждый КС-язык определяется не леворекурсивной грамматикой.

Доказательство. Пусть G - приведенная грамматика, порождающая КС-язык L. При применении к ней алгоритма 2.13

используются только те преобразования, которые упоминаются в леммах 2.14 и 2.15. Поэтому результирующая грамматика G порождает Е.

Сформулируем два утверждения, которые по существу уже встречались в конце описаний ишгов (2) и (4) алгоритма 2.13:

(2.4.4) После выполнения шага (2) для / правая часть каждого Л-правила начинается с терминала или с такого Лд, что k> i.

(2.4.5) После выполнения шага (4) для i и / правая часть каждого Л-правила начинается с терминала или с такого Л., что k > /.

Докажем, что (2.4.4) истинно для всех /г, а (2.4.5) истинно для всех таких пар {i, j), что in и г >/. Рассмотрим значения параметров / н (г, /) утверждений (2.4.4) и (2.4.5) в том порядке, б каком они встречаются в ходе работы алгоритма 2.13 на шаге (2) и шаге (4) соответственно:

1, (2, 1), 2, i-l, (I, 1), .... ( /),

{i, i-l), г, . .., (n, rt-1), n

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

Базис. Так как на шаге (2) цепочки р, р не могут начинаться с Л, то для /1 утверждение (2.4.4) истинно.

Шаг индукции. Предположим, что (2.4.4) и (2.4.5) истинны для значений параметров, предшествующих (г, /). Так как / < i, то по предположению индукции (2.4.4) истинно для /. Поэтому на шаге (4) каждая из цепочек р, р начинается с терминала или с такого Af, что k > /. Но после завершения шага (4) цепочки р,, ..., р становятся префиксами правых частей Л-правил. Следовательно, (2.4.5) истинно для (i, /).

Так же просто доказывается, что если (2.4.4) и (2.4.5) истинны для значений параметров, предшествующих г, то (2.4.4) истинно для i. Оставляем это в качестве упражнения.

Из (2.4.4) заключаем, что нетерминалы Л, ..., Л„ не являются леворекурсивными, так как если Л,=>"Лa для некоторого а, то k > i. Теперь нужно показать, что нетерминалы А(, появляющиеся на шаге (2), не могут быть леворекурсивными. Это непосредственно следует из того, что грамматика G приведенная. На шаге (2) все цепочки а, ..., а„ не пустые, и потому Ai не может быть первым символом правой части правила. □

Пример 2.28. Пусть G определяется правилами А-ВС\а В~СЛ\АЬ С~АВ\СС\а

Положим Ау = А, А = В и АС После каждого применения шага (2) или (4) алгориша 2.13 получаются такие грамматики (мы указываем только новые правила):

Шаг (2) для i = G не меняется

Шаг (4) для 1 = 2, /-1: В--СА\BCblab

Шаг (2) для 1 = 2; В ~СА {аЬ {САВ\аЬВ

ВСЬВ\СЬ Шаг (4) для i-3, /-1: СВСВ\аВ\СС\а Шаг (4) для 1 = 3, 1 = 2:

С~>СЛCSIаЬСВIСАВСВ\аЬВСВ \аВ\CC\a

Шаг (2) для г=3:

С -> аЬСВ I аЬВСВ \аВ\а\ аЬСВС \ аЬВСВС \ аВС \ аС С ~> АСВС I АВСВС 1СС \ АСЕ \ АВСВ \ С □

Интересный частный случай не леворекурсивной грамматики- грамматика в нормальной форме Грейбах.

Определение. КС-грамматика G=(N, 2, Р, S) называется грамматикой в нормальной форме Грейбах, если в ней нет е-правил и каждое правило из Р, отличное от S~e, имеет вид Л -аа, где aS и aN*.

Если грамматика не леворекурсивна, то на множестве ее нетерминалов можно определить естественный частичный порядок. Этот частичный порядок можно вложить в линейный порядок, полезный при преобразовании грамматики к нормальной форме Грейбах.

Лемма 2.16. Пусть G = (N, S, Р, 3)~~не леворекурсивная грамматика. Существует такой линейный порядок < на N, что если АВа принадлежит Р, то Л < В.

Доказательство. Пусть R - такое отношение на N, что ARB тогда и только тогда, когда Л=>+Ва для некоторого а. Так как грамматика G не леворекурсивна, то R - частичный порядок (транзитивность легко доказывается). Отношение R можно расширить до линейного порядка <, обладающего нужным свойством (см. алгоритм 0.1). П

Алгоритм 2.14. преобразование к нормальной форме Грейбах.

Вход. Не леворекурсивная приведенная КС-грамматика G-(N, 2, Р, S).

Выход. Эквивалентная грамматика 6 в нормальной форме Грейбах.

Метод.

(1) Построить с помощью леммы 2Л6 такой линейный порядок < на N, что каждое Л-правило начинается либо с терминала, либо с такого нетерминала В, что Л < В. Упорядочить N-Hi, AJ так, что Л < Л, <... <Л„.

(2) Положить i=n-1.

(3) Если г =0, перейти к шагу (5). В противном случае заменить каждое правило вида ЛЛа, где ; > г, правилами Л-Ра!.. .]р,,а, где Л-,. .р--все Лу-правила. Позже мы убедимся, что каждая из цепочек р, р„ начинается терминалом.

(4) Положить i = t-1 и вернуться к шагу (3).

(5) Сейчас правая часть калдаго правила (кроме, возможно, S->е) начинается терминалом. В каждом правиле Л-аХ.. .Х заменить Ху 2 новым нетерминалом X}.

(6) Для новых нетерминалов XJ, введенных на шаге (5), добавить правила -t-Xy. П

Теорема 2.19. Если L - КС-язык,.то L = L{G) для некоторой грамматики G в нормальной форме Грейбах.

Доказательство. Индукцией по п - i (т. е. по i, но в обратном порядке, начиная с i = n-\ и кончая ( = 1) можно показать, что после выполнения шага (3) алгоритма 2.14 для i правая часть каждого Л,-правила начинается терминалом. Ключевой момент здесь-использование линейного порядка <. После шага (5) грамматика преобразуется к нормальной форме Грейбах и по лемме 2.14 порождаемый ею язык не изменится. □

Пример 2,29. Рассмотрим грамматику G с правилами ЕТ\ТЕ

Т-Р\ГГ

F{E)\a

Упорядочим нетерминалы следующим образо.м: Е < Е <Т < Г <F.