Искючим из грамматики правила, содержащие непроизводящие нетерминалы

R’={ S  b, S  C, A  e, A  Ab, C  Ca, C  d }

G1=( T, N_p, S, R’)

3. Множество достижимых символов N_r = {d,a,b,S,C}

   • N⁰={S}

   • N¹={S,b,C}, из правил S  b, S  C

   • N²={S,b,C,a,d} из правил C  Ca, C  d

   • N³={S,C,b,a,d}.

   • N_r = {d,a,b,S,C}

4. Исходная грамматика без бесполезных символов будет выглядеть следующим образом.

N’={S,C}, T’={a, b, d}, R’’={ S  b, S  C, C  Ca, C  d }

G = < T’, N’, S, R’’ >

2.2.2. Исключение -правил

Преобразовать исходную КС-грамматику G = < T, N, S, R > в эквивалентную НКС-грамматику:

2.2.2.1.   T = { a, b }, N = { A, B, S }, R = { S  AB, A   SA, A  BB, A  bB, B  b, B  aA, B  };

Множество укорачивающих нетерминалов:

N_ε ={B, A, S}

• N⁰={B} из правила B  

• N¹={B,A} из правила A  BB

• N²={B,A,S} из правила S  AB

• N_ε ={B, A, S}

Построение R’ = {

B  b,

B  aA,

B  a, //A N_ε, исключаем правило A  BB,

A  bB,

A  b, //B N_ε, исключаем правило B  

A   SA,

A   S, //S N_ε, исключаем правило S  AB

S  AB,

S  A,

S  B,

S’   S, //S N_ε ,добавляем правило S’   

S’   

}

Т.о.преобразованная грамматика -

G’ = < T, N, S’, R’ >

2.2.3. Исключение цепных правил

Преобразовать НКС-грамматику G = < T, N, S, R > в эквивалентную КС-грамматику, не содержащую цепных правил.

2.2.3.1. T = { i, :=, (, ) }, N = { S, A, B, F, L, P, Q }, R = { S   LA, S   LB, L   P:= , L   Q:= , P   i, A   F, Q   i, B   F, F   Q(i) };

1. для каждого D из N построим множество N_D {E | D  * E}

N_S={S} N_A={A,F} N_B{B,F} N_F={F} N_L={L} N_P={P} N_Q={Q}

2. Построим R’ без цепных правил

wR’ = {S LA, S   LB, L   P:= , L   Q:= , P   i, Q   i, AQ(i), BQ(i)}, FQ(i)};

Т.о. преобразованная грамматика –

G = < T, N, S, R’ >

2.2.4. Исключение левой рекурсии

Исключить левую рекурсию из КС-грамматики G = < T, N, S, R >.

2.2.4.1.   T = { a, b, с }, N = { S, A }, R = { S   SaA, S   AA, S   b, A   ASa, A   Ab, A   c };

1. i=1

S   SaA; S   AA, S   b

после замены S   AA, S   b, S   AAS’, S   bS’, S’   aA, S’   aA S’

2. i=2, j=1

правил вида A2A1a нет.

j=i-1

3. j=1, i=2

A   ASa, A   Ab, A   c

После замены A   c, A   cА’, A’   Sa, A’   b,

A’   SaA’, A’   bA’

R’={ S   AA, S   b, S   AAS’, S   bS’, S’   aA, S’   aA S’, A   c, A   cА’, A’   Sa, A’   b,

A’   SaA’, A’   bA },

N’={S,A,S’A’}

Грамматика без левой рекурсии -

G’={T,N’,S,R’}

Раздел 3

КОНЕЧНЫЕ АВТОМАТЫ И ПРЕОБРАЗОВАТЕЛИ

Формулировка задания.

Построить детерминированный конечный автомат (КА) по автоматной грамматике G = < T, N, S, R >. Определить язык, допускаемый конечным автоматом.

3.2.1.4. T = { 0, 1 }, N = { S, A, B }, R = { S  , S   1S, S   0A, A   1S, A   0B, B   , B   0B, B 1B };

Исключим e-правила

S->e

S->1S S->1

S->0A

A->1S A->1

A->0 A->0B

B->0 B->0B, B->1, B->1B

Функции переходов недетерминированного конечного автомата.

(S,1)={S,E}

(S,0)=A

(A,1)={S,E}

(A,0)={B,E}

(B,1)={B,E}

(B,0)={B,E}

Преобразование недетерминированного конечного автомата в детерминированный.

F={P0,P2,P3} q0=p0 {1,0} {P0,P1,P2,P3}

Г раф переходов полученного детерминированного автомата

Функция переходов

(p0,0)=p1

(p0,1)=p2

(p1,0)=p3

(p1,1)=p2

(p2,0)=p1

(p2,1)=p2

(p3,0)=p3

(p3,1)=p3

Описание языка, допускаемого конечным автоматом.

Цепочки, принадлежащие языку – наборы 1 и 0, начало которых – последовательности 1 любой длины, резделяемые 0, конец – произвольная последовательность 1 и 0 любой длины. Начало и конец разделены двумя нулями

начало и/или конец могут отсутствовать

Последовательность конфигураций конечного автомата при разборе цепочки, принадлежащей языку 111101100100101001

(p0, 111101100100101001)

(p2, 11101100100101001)

(p2, 1101100100101001)

(p2, 101100100101001)

(p2, 01100100101001)

(p1,1100100101001)

(p2, 100100101001)

(p1, 00100101001)

(p3, 0100101001)

(p3, 100101001)

(p3, 00101001)

(p3, 0101001)

(p3, 101001)

(p3, 01001)

(p3, 1001)

(p3, 001)

(p3, 01)

(p3, 1)

(p3,ε)

p3 – одно из конечных состояний ДКА

Последовательность конфигураций конечного преобразователя при переводе цепочки, не принадлежащей языку. 11110

(p0, 11110)

(p2, 1110)

(p2, 110)

(p2, 10)

(p2, 0)

(p1, 11110)

3.2  

Формулировка задания

  Определить конечный преобразователь, осуществляющий перевод последовательности составных имен (идентификаторов, разделенных символом ".") в последовательность цепочек 1ⁿ , где n – число простых идентификаторов, входящих в состав составного идентификатора. Элементы последовательности разделяются запятой, признаком конца последовательности является символ "#".

Функции переходов и выходов, таблица переходов и выходов и граф переходов и выходов детерминированного конечного преобразователя.

а – любой символ имени

(q0, a) = {(q1, )}

(q1, a) = {(q1, )}

(q1, .) = {(q2, 1)}

(q1, , ) = {(q3, 1)}

(q1, #) = {(qe, 1)}

(q2, a) = {(q1, )}

(q3, a) = {(q1, ,)}

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

AB.D,C,A# результат преобразования должен быть 11,1,1

(q0, AB.D,C,A#,) ->(q1, B.D,C,A#, )->(q1, .D,C,A#, )->(q2, D,C,A#,1)->(q1, ,C,A#, 1)->(q3, C,A#, 11)->(q1, ,A#, 11,)->(q3, A#, 11,1)->(q1, #, 11,1,)->(qe, , 11,1,1)

Последовательность конфигураций конечного преобразователя при переводе цепочки, не принадлежащей языку.

C.D,A.# данная цепочка не принадлежит языку.

(q0, C.D,A.#,) -> (q1, .D,A.#,) ->(q2, D,A.#, 1)-> (q1, ,A.#,1)-> (q3, A.#,11)-> (q1, .# ,11,)-> (q2, #, 11,1).

Раздел 4.

АВТОМАТЫ И ПРЕОБРАЗОВАТЕЛИ С МАГАЗИННОЙ ПАМЯТЬЮ

4.2.1.6

Формулировка задания

Построить детерминированный магазинный автомат, распознающий цепочки из множества { 0n1n , n > 0 }  { 1n0n , n > 0 }.

P= <{q0,q1,q2,q3,q4,q5,qe},{1,0},{1,0,Z}, ,Z, q0, qe>

Функции переходов:

(q0,1,Z)=(q1,1Z)

(q0,0,Z)=(q2,0Z)

(q1,1,1)=(q1,11)

(q1,0,1)=(q3,ε)

(q2,0,0)=(q2,00)

(q2,1,0)=(q4, ε)

(q3,0,1)=(q3,ε)

(q4,1,0)=(q4,ε)

(q3, ε ,Z)=(qe,ε)

(q4, ε,Z)=(qe,ε)

Последовательность конфигураций при разборе цепочки 111000, принадлежащей языку .

(q0, 111000, Z)├ (q1, 11000, 1Z) ├ (q1, 1000, 11Z) ├ (q1, 000, 111Z) ├ (q3, 00, 11Z) ├ (q3, 0, 1Z) ├ (q3, ε, Z) ├ (qe, ε, ε).

Последовательность конфигураций при разборе цепочки 00111, не принадлежащей языку .

(q0,00111,Z) ├ (q2,0111,0Z) ├ (q2,111,00Z) ├ (q4,11,0Z )├ (q4,1,Z)

Из данного состояния невозможно совершить переход.

4.2.2.8.  

 Формулировка задания

Построить детерминированный преобразователь с магазинной памятью, осуществляющий перевод произвольной цепочки из множества {13n+20n , n ≥ 0} в цепочку вида 1n0n.

P= <{q0,q1,q2,q4,q5, q6,q7 },{1,0},{1,0}{1,0,Z}, ,Z, q0, q7>

(q0,1,Z)=(q1,Z, ε)

(q1,1,Z)=(q2,Z, ε)

(q2,ε,Z)=(q7, ε, ε)

(q2,1,Z)=(q4,1Z, ε)

(q2,1,1)=(q4,11, ε)

(q2,0,1)=(q6, ε, 0)

(q4,1,Z)=(q5,Z, ε)

(q4,1,1)=(q5,1, ε)

(q5,1,Z)=(q2,1Z, 1)

(q5,1,1)=(q2,11, 1)

(q6, 0, 1)=(q6, ε, 0)

(q6, ε, Z)=(q7, ε, ε)

Преобразование цепочки 1111111100, принадлежащей языку.

(q0, 1111111100,Z, ε) ├ (q1, 111111100, Z, ε) ├ (q2, 11111100, Z, ε) ├ (q4, 1111100, Z, ε) ├ (q5, 111100, Z, ε) ├ (q2, 11100,1Z, 1) ├ (q4, 1100,1Z,1) ├ (q5, 100,1Z,1) ├ (q2, 00, 11Z, 11) ├ (q6, 0 ,1Z, 110) ├ (q6, ε, Z, 1100) ├ (q7, ε, ε, 1100)

Преобразование цепочки 1100, не принадлежащей языку.

(q0, 1100, Z, ε) ├ (q1, 100, Z, ε) ├ (q2, 00, Z, ε). Из текущей конфигурации невозможно совершить переход.

4.2.3.1.

Формулировка задания

Построение недетерминированного МП-автомата по КС-грамматике

   T = { a, b, с }, N = { S, A }, R = { S   SaA, S   AA, S   b, A   ASa, A   Ab, A   c };

(q,,S)={(q,SaA),(q,AA),(q,b)}

(q,,A)={(q,Asa),(q, Ab),(q, c)}

(q,α, α)={(q, )} для α € { a, b, с }

4.2.3.4.

Формулировка задания

Построить недетерминированный расширенный МП-автомат по КС- грамматике

T = { a, b, с, d }, N = { S, A }, R = { S   aA, S   Ab, A   Sc, A   d };

P=({q, r}, {a, b, c, d}, {a, b, c, d, S, A,Z}, , q, Z, {r})

(q, t, )=(q, t), t €{ a, b, с, d }

(q, , аA)= (q, S)

(q, , Ab)= (q, S)

(q, , Sc)= (q, A)

(q, , d)= (q, A)

(q, , ZS)= (r, )

Раздел 5

АЛГОРИТМ РАЗБОРА ДЛЯ LL(1)-ГРАММАТИК

Формулировка задания:

Построить управляющую таблицу и промоделировать работу LL(1)-анализатора для КС-грамматики G = < T, N, S, R >.

    T = { a, b, c, d, e }, N = { S, A, B }, R = { S   aAB, S   bBS, S   , A   cBS, A   , B   dB, B    };

1. S   aAB,

2. S   bBS,

3. S   ,

4.A   cBS,

5.A  ,

6.B   dB,

7.B   

S β

FIRST(β)={a,b,}

A β

FIRST(β)={c, }

B β

FIRST(β) = {d, }

Контрольный пример – разбор цепочки, порождаемой этим алгоритмом

acdbd

(acdbd,S┴, )->

(acdbd,aAB┴,1)->

(cdbd,AB┴,1)->

(cdbd,cBSB┴,14)->

(dbd,BSB┴,14)->

(dbd,dBSB┴,146)->

(bd,BSB┴,146)->

(bd,SB┴,1467)->

(bd,bBSB┴,14672)->

(d,BSB┴,14672)->

(d,dBSB┴,146726)->

(,BSB┴,146726)->

(,SB┴,1467267)->

(,B┴,14672673)->

(,┴,146726737)

M(S,a)=(aAB,1)

ВЫБРОС

M(A,c)=(cBS,4)

ВЫБРОС

M(B,d)=(dB,6)

ВЫБРОС

M(B,b)=(,7)

M(S,b)=(bBS,2)

ВЫБРОС

M(B,d)=(dB,6)

ВЫБРОС

M(B, )=(,7)

M(S, )=(,3)

M(B, )=(,7)

ДОПУСК

Раздел 6

АЛГОРИТМ РАЗБОРА ДЛЯ LR(0)-ГРАММАТИК И SLR(1)-ГРАММАТИК

Формулировка задания:

6.2. Построить управляющую таблицу и промоделировать работу SLR(1)-анализатора для КС-грамматики G = < T, N, S, R >.

6.2.2.   T = { v, u, w, y }, N = { S, A, B, C }, R = { S   Bv, S   vC, A  u, A   vBS, B   u, B   yw, C   Bv, C   yAw };

Построение управляющей таблицы:

1. Построение дополненной грамматики

Дополнительное правило S’S

0 S’S

1 S   Bv

2 S   vC

3 A  u

4 A   vBS

5 B   u

6 B   yw

7 C   Bv

8 C   yAw

┴OBLOW {S0,B1,v2,u5,y6}

B1 OBLOW {v1}

V2 OBLOW{c2,B7,u5,y6,y8}

V4 OBLOW {B4,u5,y6}

B4 OBLOW {S4,B1,u5,y6,v2}

Y6 OBLOW {w6}

B7 OBLOW {v7}

Y8 OBLOW {A8,u3,v4}

A8 OBLOW {w8}

Таблица отношения OBLOW

На основании таблицы OBLOW построим таблицу переходов конечного автомата

Преобразуем полученный автомат в детерминированный

Определим множество магазинных символов

Тогда функции переходов имеют вид:

Контрольный пример – разбор цепочки vyvuywvw, принадлежащей языку.

(┴, vyvuywvw ,ε)

(┴v2 , yvuywvw, ε)

(┴v2Yx, vuywvw, ε)

(┴v2Yxv4, uywvw , ε)

(┴v2Yxv4u5, ywvw , 5)

(┴v2Yxv4B4, ywvw , 5)

(┴v2Yxv4B4yx, wvw , 5)

(┴v2Yxv4B4yxw, vw , 5)

(┴v2Yxv4B4B1, vw , 56)

(┴v2Yxv4B4B1v1, w ,5 6)

(┴v2Yxv4B4S4, w , 561)

(┴v2YxA8 , w , 5614)

(┴v2YxA8w8, ε, 5614)

(┴v2C2, ε, 56148)

(┴S0, ε, 561482)

ДОПУСК

т.о. правый разбор цепочки vyvuywvw - 561482

Раздел 7

АЛГОРИТМ РАЗБОРА ТИПА "ПЕРЕНОС-СВЕРТКА"

Формулировка задания:

7.2. Построить анализатор типа "перенос-свертка" и промоделировать его работу для следующих грамматик слабого предшествования G = < T, N, S, R >:

7.2.4. T = { i, or, and, not, (, ) }, N = { S, T, P ), R = { S  S or T, S  T, T  T and P, T  P, P  i, P   ( S ), P   not P };

1. Отношение (=) определяется непосредственно из правил грамматики

2. Определим отношения FIRSTN и LASTN

Построим транзитивные замыкания данных отношений

3. Представим отношения в виде булевых матриц, строки и столбцы которых обозначены символами грамматики в порядке S T P i or and not ( )

Тогда матрицу отношения (<•) получим из соотношения (<•) = (=)(FIRSTN+)

=

Т.е. отношение (<•) определяется следующим образом

матрицу отношения (•>) получим из соотношения (•>) =((LASTN⁺)T) (=)(E+FIRSTN⁺)

(LASTN⁺)=

(LASTN⁺)T=

((LASTN⁺)^-1)(=) =

(E+FIRTSN⁺) =

Значит матрица отношений предшествования для данной грамматики выглядит следующим образом

Используя таблицу отношений предшествования построим функцию переноса

И функцию свертки

Контрольный пример - разбор цепочки (not i ) and i or not i, принадлежащей языку

(┴, (not i ) and i or not I,ε)

(┴ ( , not i ) and i or not I, ε)

(┴ (not, i ) and i or not I, ε)

(┴ (not i,) and i or not I, ε)

(┴ (not P , ) and i or not I,5)

(┴ (P , ) and i or not I,57)

(┴ (T ,) and i or not I,574)

(┴ (S ,) and i or not I,5742)

(┴ (S) , and i or not I,5742)

(┴P, and i or not I,57426)

(┴T , and i or not I,574264)

(┴Tand, i or not I,574264)

(┴Tand I, or not I,574264)

(┴Tand P , or not I,5742645)

(┴T , or not I,57426453)

(┴S , or not i,574264532)

(┴Sor , not I,574264532)

(┴Sor not , I,574264532)

(┴Sor not I , ε,574264532)

(┴Sor not P , ε,5742645325)

(┴Sor P, ε,57426453257)

(┴Sor T , ε,574264532574)

(┴S, ε, 5742645325741)

ДОПУСК

56