Тема 3: Эквивалентные преобразования грамматик.

1. Преобразования автоматных грамматик к вполне детерминированной форме.

2. Исключение тупиковых правил.

3. Обобщённые КС-грамматики. Приведение грамматик к удлиняющей форме.

4. Декомпозиция правил КС-грамматик.

5. Устранение левой рекурсии. Левая факторизация.

1. Преобразования автоматных грамматик к вполне детерминированной форме.

Две грамматики называются эквивалентными, если они порождают один и тот же язык. Как факт, примем следующую теорему: не существует алгоритма, определяющего эквивалентность или неэквивалентность двух грамматик. Тем не менее, существуют преобразования, приводящие к эквивалентной грамматике. Критерием преобразования являются:

1. Приведение к детерминированной форме.

2. Устранение правил, не приводящих к терминальным цепочкам.

3. Уменьшение вывода за счёт увеличения количества правил и удаление пустых цепочек.

Теорема: для любой автоматной грамматики существует эквивалентная ей грамматика во вполне детерминированной форме.

Алгоритм приведения к детерминированной форме:

1. A  a,F’: A  aF’

Второй шаг аналогичен алгоритму приведения к детерминированной форме конечных автоматов.

Если в исходной грамматике имеется правило: «SaA₁|…|aA_n», то в результирующей грамматике добавляется правило вида: <S>a<A₁…A_n>,A_iaB_j, <…A_i…>a<…B_j….>.

Процесс построения новых нетерминалов завершается после рассмотрения нетерминалов исходной грамматики и анализа всех вновь появившихся нетерминалов.

Если цепочка принадлежит языку, порождаемому одной грамматикой, она будет принадлежать и языку, порождаемому другой грамматикой:

a € L (G₁); a € L (G₂)

a € L (G₂); a € L (G₁)

a = a₁…a_n.

S_a1A_a2…A_anF.

<S>_a1<A₁>…<A_n>, a € L (G₂).

Пример:

S  aB|aC|bB|bS|c

B  cC|c

CaS|a|c

Грамматика находится не во вполне детерминированной форме, так как имеются разветвления состояний.

Добавляем предконечное состояние:

S aB|aC|bB|bS|cF’

B cC|cF’

C aS|aF’|cF’

F’  ⊥F

Перевод:

<S> a<BC>|b<BS>|c<F’>

<B>  c<CF’>

<C> a<SF’>|c<F’>

<F’> ⊥<F>

<BC>  c<CF’>|a<SF’>

<BS>  c<CF’>|a<BC>|b<BS>

<CF’>  a<SF’>|c<F’>|⊥<F>

<SF’>  a<BC>|b<BS>|c<F’>|⊥<F>

Переименовываем:

<S> - S

<F> - F

<F’> - F’

<BC> - A

<BS> - B

<CF’> - C

<SF’> - D

Решение:

S  aA|bB|cF’

F’  ⊥F

A  cC|aD

B  cC|aA|bB

C  aD|cF’|⊥F

D  aA|bB|cF’|⊥F

2. Исключение тупиковых правил.

Правила, не приводящие к терминальным цепочкам, называются тупиковыми. Различают тупики внешнего типа, внешнего типа и циклические тупики внешнего и внутреннего типа.

Правила вида: «AaBb» называются тупиком внешнего типа, если не существует ни одного правила для нетерминалаB: «Bb₁».

Правила вида: «Aj» называются тупиком внутреннего типа, если не существует ни одного правила для нетерминалаB: «BaAb», по которому можно попасть внутрьA.

B

A

S

C

F

AB– внешний тупик,CA– внутренний.

A₀  a₀A₁b₀

A₁  a₁A₂b₁ – циклический тупик.

Эта же совокупность правил называется циклическим тупиком внутреннего типа, если ни для одного A_iне существует правила, по которому в этот нетерминал можно попасть.

Теорема: для любой КС-грамматики существует эквивалентная ей грамматика беступиковых правил.

Для устранения тупиков циклического типа строится множество нетерминалов, не являющихся тупиками…

1. X₀ = V_T – множество нетерминалов.

2. X₁= {A|Aa,a€X₀} – терминалы, из которых можно получить нетерминальную цепочку не более чем за один шаг.

3. X_i= {A|Aa,a€X₀vX_k},k= 0…i,k€v- терминалы, из которых можно получить нетерминальную цепочку не более чем заi-шагов.

Так как множество нетерминалов любой грамматики конечное, то существует такой номер I, что на некотором шагеX_I=X_I+1;

Все нетерминалы, вошедшие в X_I– «хорошие». Не вошедшие исключаются вместе с правилами, в которые они входят.

Для полученной грамматики выполняется второй шаг алгоритма, исключающий тупики внутреннего типа и циклические тупики внутреннего типа.

2. Y₀= {S} – нетерминалS, «хороший».

Y₁ = {A|S  a, a € Y₀}

… … … … …

Y_i = {A|B  aAф, B € v Y_k}, k = 0…i-1, k € v

Y_i– множество нетерминалов, в которые можно попасть не более чем заiшагов.

Все нетерминалы, не попавшие в Y_Iявляются тупиками внутреннего типа или циклическими тупиками внутреннего типа, и из грамматики исключаются.

Пример:

SaA|cC|bD|qP|kT

A  cC

C  k

T  m

D  bT|fK

P  cR

R  dK

B  dQ|m

Q  pB|rB

Решение:

1. X₀ = V_T

2. X₁ = {C,T,B}

3. X₂= {C,T,B,S,A,D,Q} // входят только множества, в которых есть один или два нетерминала из предыдущих множеств (выше).

4. X₃ = {C,T,B,S,A,D,Q}

Таким образом, вычёркиваем «qP» из 1 строчки, а также множестваP,RиK.

1. Y₀ = {S}

2. Y₁ = {S,A,C,D,T}

3. Y₂ = {S,A,C,D,T}

B,Q– совокупность правил, составляющих циклический тупик внутреннего типа. Их из грамматики исключаем.

Получаем беступиковую грамматику.

3. Обобщённые КС-грамматики. Приведение грамматик к удлиняющей форме.

Правило вида Aε называются аннулирующими.

Грамматика с аннулирующими правилами является обобщённой.

Теорема: для любой обобщённой грамматики существует эквивалентная ей грамматика с не более чем одним обобщённым правилом.

Шаг 1: определение принадлежности пустой цепочки языку и построение множества нетерминалов, из которых за некоторое количество шагов можно получить пустую цепочку.

X₀ = {ε}

X₁ = {A|A  ε}

X_i = {A|A  a, a € v X_k}, k = 0…i-1, k € v

Если S€X_I, то пустая цепочка принадлежит языку.

В таком случае Sзаменяется наS₁и добавляется правило:SS₁|ε.

Если в грамматике имеются правила вида: A₀a₀A₁a₁A₂…A_na_n, то в грамматику добавляются следующие правила:

A₀  a₀a₁A₂…A_na_n,

A₀  a₀A₁a₁a₂…A_na_n,

A₀a₀a₁a₂a_n, то есть рассматриваются все случаи исчезновения.

A­_iε.

Пример: <число> <знак><целая часть>.<дробная часть>

<знак> +|-| ε

<целая часть> <целая часть><цифра>| ε

<дробная часть> <целая часть>

<цифра> 0|…|9

Решение:

X₀= { ε }

X₁= {<знак>,<целая часть>}

X₂= {<знак>,<целая часть>,<дробная часть>}

X₃= {<знак>,<целая часть>,<дробная часть>}

X₂=X₃.

Правило 1: перебор всех вариантов исчезновения.

<число> <знак><целая часть>.<дробная часть>|<целая часть>.<дробная часть>|<знак><дробная часть>|<знак><целая часть>|.<дробная часть>|<целая часть>.|<знак>.|.

Правило 2:

<знак> +|-

<целая часть> <целая часть><цифра>|<цифра>

<дробная часть> <целая часть>

<цифра> 0|…|9

Рассмотренный алгоритм является алгоритмом о приведении фрагмента грамматики к неукорачивающей форме.

Правило вида: «Из нетерминала выводится терминал» называется цепным.

Теорема о приведении грамматик к неудлиняющей форме: для любой контекстно-свободной грамматики существует эквивалентная ей грамматика без цепных правил.

Доказательство: если из грамматики выводится правило: «AB(A/=S)», тогда во всех правилах, гдеAприсутствует в правых частях, делают заменуAнаB: «CaAb–CaBb».

Если из грамматики выводится правило: «AB(A=S)», и имеется группа правил:Ba₁|…|a_n, замена правила наSa₁|…|a_n, и удаление правила «AB» является эквивалентным преобразованием.

Грамматика называется приведённой, если в ней отсутствуют тупики, аннулирующие и обобщённые правила.

4. Декомпозиция правил КС-грамматик.

Лемма: если в КС-грамматике существует правило вида: «YaXb» и «Xj», то грамматика, в которую добавляется правило: «G₂= (V_N,V_T,S,R,U(Yajb))» эквивалентна исходной.

Доказательство: если a€L(G₁), тоa€L(G₂). С другой стороны, еслиa€L(G₂) и при её выводе не участвуют правила: «Yajb», тоa€L(G₁). Если правила «Yajb» и «Xj» используются при выводе цепочки правил, то их замена позволит вывести цепочку в грамматикеG_1­. Значитa€L(G₁), иa€L(G₂), аG₁ = G_2.

Теорема.

Если в грамматике имеется группа правил:

G₁: {YαXβ,Xy₁…Xy_n}

То замена их на правила такого вида:

{Yαy₁β,Yαy_nβ;Xy₁…Xy_n}

Является ээквивалентным преобразованием.

X/=S,Xy₁…Xy_n

Доказательство производится многократным применением леммы.

Теорема об исключении внешнего правила:

Если в грамматике имеется группа правил:

{Yα₁Xβ₁, … ,Yα_nXβ_n,Xy}

То замена их на правила такого вида:

{Yαy₁β₁,Yαy_nβ_n;Xy}

Является ээквивалентным преобразованием.

При этом если X/=S, и других правилXв правых частях нет, правилоXyиз грамматики можно удалить.

Доказательство производится многократным применением леммы.

Теорема о декомпозиции правил грамматики:

Замена группы правил вида:

{Yα₁Xβ₁;Xy₁}

…

{Yα_nXβ_n;Xy_n}

На группу правил:

{Yα₁y₁β₁;Yα₁y_mβ₁}

…

{ Yα_ny₁β_n;Yα_ny_mβ_n}

Является эквивалентным преобразованием, если X/=Sи других правил сXв левых и правых частях правил вывода нет.

Доказательство производится многократным применением леммы.

<Идентификатор> <Буква> | <Буква> <Идентификатор 1>

<Идентификатор 1> <Буква> <Идентификатор 1>| <Цифра> <Идентификатор 1> | <Буква>| <Идентификатор 1>

<Буква> a|…|z

<Цифра> 0|…|9

Грамматика включает 42 правила. Выполним декомпозицию относительно нетерминала «Буква» и «Цифра».

<Идентификатор> a|…|z|a<Идентификатор 1> |…|z<Идентификатор 1>

<Идентификатор 1> a|…|z|0|…|9

3.5. Устранение левой рекурсии и левая факторизация.

Для любой КС-грамматики существует эквивалентная ей грамматика без левой рекурсии.

A  Aα_i, i=(1,n)

A  β_j, j=(1,m)

Левую рекурсию на правую:

Aβ_j<списокA>

<список A>α_i<списокA> | ε

Пример:

<Идентификатор> <Буква> | <Идентификатор><Буква> | <Идентификатор><Цифра>

<Идентификатор> <Буква><Идентификатор 1>

<Идентификатор 1> <Буква><Идентификатор 1> | <Цифра><Идентификатор 1> | ε

Если в грамматике имеется группа правил:

Aαβ₁|…|αβ_n, то их преобразование на правила вида:

AαB

Dβ₁|…|β_nявляется левой факторизацией.