Лекция 10 Левокурсивные и правокурсивные грамматики

Определение 10.1 Некоторый нетерминальный символ А контекстно-свободной грамматики G = (N,, P, S) называется рекурсивным, если существует вывод А + А для некоторых и. Если при этом =, то А называется леворекурсивным. Аналогично, если =, то А называется праворекурсивным. Грамматика, имеющая хотя бы один леворекурсивный нетерминальный символ, называется леворекурсивной. Грамматика, в которой все нетерминальные символы, кроме, быть может, начального символа, рекурсивные, называется рекурсивной.

Заметим, что для рекурсивных грамматик в выводе А + А всегда либо, либо. Если = и =, то грамматика G является циклической грамматикой. Пример Примером праворекурсивной грамматики является грамматика со следующей схемой: 1 0 Данная грамматика порождает множество чисел, состоящих из нулей и единиц.

Пример Тот же самый язык, что и в примере порождает леворекурсивная грамматика со следующей схемой: 1 0

Пример Примером леворекурсивной грамматики является грамматика со следующей схемой: А 1 0 Данная грамматика порождает множество идентификаторов, начинающихся с буквы А.

Пример Тот же самый язык, что и в примере порождает праворекурсивная грамматика со следующей схемой: А 1 0

Лемма 10.1 Пусть G = (N,, P, S) – КС-грамматика, в которой для некоторого нетерминального символа А все А- правила имеют вид А A 1 | A 2 | … | A m | 1 | 2 | … | n | причем ни одна из цепочек i не начинается с А. Пусть G'=(N {A'},, P', S), где A' – новый нетерминал, а P' получается из P заменой этих А- правил следующими правилами А 1 | 2 | … | n | 1A' | 2A' | … | nA' | А' 1 | 2 | … | m | 1A' | 2A' | … | mA' Тогда L(G') = L(G). Рассмотрим алгоритм преобразования КС- грамматики, в которой имеется непосредственная левая рекурсия, к КС-грамматике без левой рекурсии.

Доказательство. Цепочки, которые можно получить в грамматике G из нетерминала А применением А- правил лишь к самому левому нетерминалу, образуют регулярное множество ( … + n )( … + m )* Это в точности те цепочки, которые можно получить в грамматике G' из А с помощью правых выводов, применив один раз А-правило и несколько раз А'- правила (в результате вывод уже не будет левым). Все шаги вывода, на которых не используются А- правила, можно непосредственно сделать и в грамматике G', так как не А-правила в обеих грамматиках одни и те же. Отсюда можно заключить, что L(G) L(G').

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

Лемма 10.2 Пусть G = (N,, P, S) – КС-грамматика, в которой для некоторого нетерминального символа А все А- правила имеют вид А A 1 | A 2 | … | A m | 1 | 2 | … | m причем ни одна из цепочек i не начинается с А. Пусть G'=(N,, P', S), где P' получается из P заменой этих А-правил следующими правилами А 1 | 2 | … | m | 1A | 2A | … | mA Тогда L(G') = L(G). Грамматика примера получена из грамматики примера с использованием преобразования леммы 10.2.

На рисунке показано, как действуют преобразования на дерево вывода A A i1... i2 A A ik A ik A ik-1... i1

Пример Пусть G0 – обычная грамматика с правилами E E+T E T T T*F T F F (E) F a Эквивалентная ей грамматика G`

E T E TE' E' +T E' +TE' T F T FT ' T ' *F T ' *FT ' F (E) F a Рассмотрим теперь, как преобразовать приведенную леворекурсивную КС-грамматику к КС-грамматике, не имеющей левой рекурсии.

Алгоритм 10.2 Устранение левой рекурсии. Вход: Приведенная КС-грамматика G=(N,,P,S) Выход: Эквивалентная КС-грамматика G` без левой рекурсии. Метод. Пусть N = {A1,…, An}, т.е. все нетерминальные символы грамматики упорядочены некоторым произвольным образом. Преобразуем G так, чтобы в правиле Ai цепочка начиналась либо с терминала, либо с такого Aj, что j i. 1) Положим i=1.

2) Пусть множество Ai – правил – это Ai Ai | … | Ai m | 1 | … | p, где ни одна из цепочек j не начинается с Ak, если k i (если это не выполнено, можно ввести новый нетерминальный символ, заменить первый символ правила этим символом и добавить дополнительное правило в грамматику). Заменим Ai–правила правилами: Ai 1 | … | p | 1Ai' | … | pAi' Ai' 1 | … | m | 1Ai' | … | mAi' где A'i новый нетерминал. Правые части всех Ai- правил начинаются теперь с терминала или с Ak для некоторого k > i. 3) Если i=n, полученную грамматику G' считать результатом и остановиться. В противном случае положить i=i+1 и j=1.

4) Заменить каждое правило вида Ai Aj правилами Ai 1 |…| m, полученными в результате замены Aj правыми частями всех Aj-правил вида Aj 1|…| m. Так как правая часть каждого Aj-правила начинается уже с терминала или с Ak для k > j, то и правая часть каждого Ai- правила будет теперь обладать этим свойством. 5) Если j=i–1, перейти к шагу (2). В противном случае положить j=j+1 и перейти к шагу (4).

Теорема 10.1 Для каждого КС-языка существует порождающая его не леворекурсивная грамматика. Доказательство есть следствие приведенных в данном разделе преобразований. Пример Пусть G есть КС-грамматика с правилами A BC a B CA Ab C AB CC a

Положим A1=A, A2=B и A3=C После каждого применения шага (2) или (4) алгоритма получаются следующие грамматики (указываем только новые правила). Шаг (2) для i=1: G не меняется Шаг (4) для i=2, j=1: B CA BCb ab Шаг (2) для i=2: B CA ab CAB abB B Cb Шаг (4) для i=3, j=1: C BCB aB CC a Шаг (4) для i=3, j=2: C CACB ab CB CAB CB ab B CB aB CC a Шаг (2) для i=3: C abCB ab B CB aB a abCBC ab B CB C aB C aC C ACB C AB CB C CC ACB AB CB C

Задание 13 Привести пример лево-рекурсивной грамматики (рекурсия не является непосредственной), устранить в грамматике левую рекурсию.