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

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’’ >

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

Алгоритм 3.7.2.1. Построение множества укорачивающих нетерминалов.

Вход. КС-грамматика G = (, , P, S).

Выход. Множество укорачивающих нетерминалов: _ = {A | A ⁺ , A  }.

Описание алгоритма.

Построить рекурсивно множества укорачивающих нетерминалов ⁰_, ¹_, … , ⁱ_, … , следующим образом:

1. Положить ⁰_ = {A | A  , A  }, i = 1.

2. Положить ⁱ_ = ^i-1_  {A | A    P и   (^i-1_)⁺}.

3. Если ⁱ_  ^i-1_, положить i = i + 1 и перейти к шагу 2.

4. Положить _ = ⁱ_.

Конец алгоритма

Так как _  , число повторений шага 2 алгоритма не превышает n + 1, где n – число нетерминалов грамматики G.

Замечание

При определении множеств ⁱ_ можно рассматривать только правила вывода, не содержащие в правых частях терминалы.

Алгоритм 3.7.2.2. Преобразование КС-грамматики с -правилами в эквивалентную НКС-грамматику.

Вход. КС-грамматика G = (, , P, S).

Выход. НКС-грамматика G¢ = (¢, , P¢, S¢), порождающая язык L(G¢) = L(G).

Описание алгоритма.

Построить множество _ укорачивающих нетерминалов.

Построить P¢ следующим образом:

1. Положить P¢ = .

2. Если A  ₀B₁₁B₂₂… B_k_k  P, где k  0, B_j  _ (1 j  k) и ни один из символов цепочек _i  (  )^* (0  i  k) не содержит символов из _, то включить в P¢ все правила вывода вида A  ₀X₁₁X₂₂… X_k_k, где X_j  = B_j или X = . Если все цепочки _i = , то правило A   не включать в P¢.

3. Если S  _, то положить ¢ =   {S¢} и добавить в P¢ два правила: S¢  S и S¢  , в противном случае ¢ =  и S¢ = S.

4. Положить G¢ = (¢, , P¢, S¢).

Конец алгоритма

Пример 3.8

Преобразовать КС-грамматику G = (, , P, S). где  = {А, S},  = {b, c}, P = {S  сА, S  , А  сA, А  bA, A  }, в эквивалентную НКС-грамматику.

Используя алгоритм 3.7.2.1, получаем: ⁰_ = {S, A}, ¹_ = {S, A}, значит _ = ¹_ = {S, A}.

Далее, выполняя шаги алгоритма 3.7.2.2, имеем:

Шаг 1. P¢ = .

Шаг 2. Рассмотрим правило S  сА. Для него в новое множество правил грамматики P¢ нужно включить правила S  сA и S  с. Для правила А à сA требуется добавить в множество P¢ правила А à сA и А à с, а для правила А à bA – правила А à bA и А à b. На данном шаге алгоритма получаем P¢ = {S à сА, S à с, А à сA, А à с, А à bA, А à b}

Шаг 3. В рассматриваемой грамматике S  _, поэтому в множество нетерминальных символов добавляем новый нетерминал S¢, а в множество правил P¢ — два правила: S¢  S и S¢ .

Окончательно имеем НКС-грамматику G¢ = ({S¢, S, A}, {b, c}, {S¢  S, S¢ , S à сА, S à с, А à сA, А à с, А à bA, А à b }, S¢), которая эквивалентна исходной грамматике.

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

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

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

Задание.   

2.2.2.3 T = { a, b, c, d }, N = { S, A, B }, R = { S  Aa, S  bB, A cAdA, A  a, A , B ®cBdd, B  ®};

Решение:

1. Построим множество укорачивающих нетерминалов.

2. Преобразуем исходную КС-грамматику с -правилами в эквивалентную НКС-грамматику.

Новая грамматика, эквивалентная исходной имеет следующий вид:

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

;

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

Преобразовать исходную КС-грамматику 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’ >

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

Преобразовать исходную КС-грамматику 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 ® e};

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

N_ε ={B, A, S}

N⁰={B} из правила B ® e

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 ® e

A  ® SA,

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

S ® AB,

S ® A,

S ® B,

S’  ® S, //SÎ N_ε ,добавляем правило S’  ® e

S’  ® e

}

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

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

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

Определение. Правило вывода вида А  В называется цепным правилом.

Алгоритм 3.7.3. Исключение цепных правил.

Вход. НКС-грамматика G = (, , P, S).

Выход. Эквивалентная НКС-грамматика G¢ = (, , P¢, S) без цепных правил.

Описание алгоритма.

1. Для каждого A   построить множество _A = {B | A ^* B}следующим образом:

   1. Положить ⁰_A = {A} и i = 1.

   2. Положить ⁱ_A = ^i-1_A  {C | B  C  P и B  ^i-1_A}.

   3. Если ⁱ_A    ^i-1_A, то положить _A = ⁱ_A.

2. Положить P¢ = .

3. Если B    P и не является цепным правилом, положить P¢ = P¢  {A  } для всех таких A, что B  _A.

4. Положить G¢ = (, , P¢, S).

Конец алгоритма

Пример 3.9

Исключить цепные правила из КС-грамматики G₀ с правилами P:

(1)	E		E + T
(2)	E		T
(3)	T		T*P
(4)	T		P
(5)	P		i
(6)	P		(E)

Шаг 1. После выполнения шага 1 алгоритма получим: _E = {E, T, P}, _T = {T, P}, _P = {P}.

Шаг 2. P¢ = .

Шаг 3. Выберем первый нетерминал E из множества N_E. Формируя множество правил, левая часть которых – нетерминальный символ E, а правые части – это правые части нецепных правил исходной грамматики, в левой части которых находятся символы из множества N_E, получаем: {E à E + T, E à T * P, E à (E), E à i}. Включаем эти правила в P¢ и имеем P¢= {E à E + T, E à T * P, E à (E), E à i}. Таким же образом рассматриваем остальные символы из N_E , затем символы множеств N_T и N_P. Окончательно получаем G¢ = (N, S, P¢, S), где P¢ = {E  E + T, E  T * P, E  i, E  (E), T  T * P, T  (E), T  i, P  (E), P  i}.

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

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

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

Задание.   

4. /

/

Решение:

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

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

/

Новая грамматика, эквивалентная исходной имеет следующий вид:

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

/

/

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

Преобразовать НКС-грамматику 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’ >

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

Преобразовать НКС-грамматику 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)};

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

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

Вход. Приведенная КС-грамматика G = (, , P, S).

Выход. Эквивалентная КС-грамматика G¢ = (¢, , P¢, S) без левой рекурсии.

Описание алгоритма.

1. Пусть множество нетерминалов грамматики  = {A₁, A₂, … , A_n}. Преобразуем грамматику таким образом, чтобы в правиле A_i   цепочка  начиналась либо с терминала, либо с такого A_j, что j > i. Установим i = 1.

2. Пусть множество A_i-правил имеет вид A_i  A_i₁, A_i  A_i₂, …, A_i  A_i_m A_i  ₁, A_i  ₂, …, A_i  _m, где ни одна из цепочек _j, не начинается с A_k, если k  i. Заменим A_i-правила правилами A_i  ₁, A_i  ₂, …, A_i  _n, A_i  ₁A¢_i, A_i  ₂A¢_I, …, A_i  _n A¢_i и A_i¢à a₁, A_i¢à a₂, …, A_i¢ à a_m, A_i¢à a₁A¢_i, A_i¢ à a₂A¢_i, …, A_i¢à a_mA¢_i, где A¢_i – новый нетерминальный символ. После выполнения такой замены правые части всех A_i-правил начинаются с терминального символа или с нетерминала A_k, для некоторого k > i.

3. Если i = n, то преобразование завершено, иначе положить i = i + l и j = l.

4. Заменить каждое правило A_i  A_j правилами A_i  ₁, A_i  ₂, …, A_i  _m, где A_j  ₁, A_j   ₂, …, A_j  _m – все A_j-правила грамматики. Правая часть A_j – правила начинается с терминального символа или с нетерминала A_k для k > j, поэтому правая часть каждого построенного A_i – правила обладает этим же свойством.

5. Если j = i – 1, то перейти к шагу 2 алгоритма, иначе положить j = j + 1 и перейти к шагу 4.

Конец алгоритма

Пример 3.11

Исключить левую рекурсию из грамматики G₀ с правилами

(1)	E		E + T
(2)	E		T
(3)	T		T*P
(4)	T		P
(5)	P		i
(6)	P		(E)

Применив к E-правилам E  E+T , E  T описанное преобразование, получим  = +T и  = T. В соответствии с этим преобразованием, новые E-правила будут иметь вид: E  T, E  TE¢ и в грамматику необходимо добавить правило для нового нетерминала E¢: E¢  +T.

После рассмотрения всех правил исходной грамматики G получим правила новой грамматики G¢:

E  T, E  TE¢, E¢  +T, E¢  +TE¢, T  P, T  PT¢, T¢  *P, T¢  *PT¢, P  (E+T), P  (E), P  i.

Пример 3.12

Устраним левую рекурсию в грамматике G, определяемой множеством правил P = {S  AB,  S  a, A  BS, A  Sb, B  SA, B  BB, B  a}.

Положим А₁ = S, А₂ = A и А₃ = B и выполним алгоритм 3.7.5 по шагам.

Шаг 1. i = 1.

Шаг 2. Правила вывода вида A₁  A₁ (в обозначениях исходной грамматики S  S) в грамматике нет. Шаг не выполняется.

Шаг 3. i = 2, j = 1.

Шаг 4. Найдем все правила вида A₂  A₁ (для нашего примера — это A  S). Таких правил в грамматике только одно — это правило A  Sb. Для выполнения замены этого правила нужно найти правила, в правой части которых стоит символ A₁ (т.е. S).

После замены правила A  Sb получим новое множество правил P¢ = {S  AB, S  a, A  BS, A  Abb, A  ab, B  SA, B  BB, B  a}.

Шаг 5. j = i – 1. Переход к шагу 2.

Шаг 2. (i = 2). Правила A  BS, A  Abb, A  ab заменяем правилами: A  BS,   A  ab, A  BSA¢, A  abA¢ и A¢  Bb, A¢  BbA¢. Получаем следующее множество правил: P¢ = { S  AB, S  a, A  BS, A  ab, A  BSA¢, A  abA¢, A¢  Bb, A¢  BbA¢, B  SA, B  BB, B  a}.

Шаг 3. i = 3, j = 1.

Шаг 4. Используя правила S  AB, S  a, заменяем правило B à SA правилами B à ABA, B à aA. Получаем новое множество правил грамматики: P¢ = { S  AB, S  a, A  BS, A  ab, A  BSA¢, A  abA¢, A¢  Bb, A¢  BbA¢, B à ABA, B à aA}.

Шаг 5. j  i – 1, j = 2. Переход к шагу 4.

Шаг 4. (i = 3, j = 2). Используя правила A  BS, A  ab, A  BSA¢, A  abA¢, заменяем правило B à ABA правилом B à aA, B à BSBA, B à abBA, B àBSA¢BA, B à abA¢BA и получаем новое множество правил грамматики P¢ = {S  AB, S  a, A  BS, A  ab, A  BSA¢, A  abA¢, A¢   Bb,  A¢  BbA¢, B à aA,  B à BSBA,  B à abBA,  B à BSA¢BA, B à abA¢BA}.

Шаг 5. j = i – 1. Переход к шагу 2.

Шаг 2. (i = 3). Правила B à BSBA,  B à BSA¢BA, B à aA, B à abBA,  B à abA¢BA заменяем правилами B à ab, B à abBA, B à abA¢BA, B à abB¢, B à abBAB¢, B à abA¢BAB¢, B¢à SBA, B¢à SA¢BA,  B¢à SBAB¢, B¢à SA¢BAB¢.

Шаг 3. i = n, выход из алгоритма с окончательным множеством правил грамматики P¢ = {S  AB, S  a, A  BS, A  ab, A  BSA¢, A  abA¢, A¢   Bb, A¢  BbA¢, B à ab, B à abBA, B à abA¢BA, B à abB¢, B à abBAB¢,  B à abA¢BAB¢, B¢à SBA, B¢à SA¢BA,  B¢à SBAB¢, B¢à SA¢BAB¢}.

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

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

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

Задание.   

2.2.4.6

Решение:

1. I=1;

Заменим выражения стоящие слева от фигурной скобки на выражения, написанные справа от фигурной скобки

2. i=2

Повторим предыдущий шаг для i=2;

T

T

3. i=3;

Преобразования не требуются.

Новая грамматика, эквивалентная исходной:

,где

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

Исключить левую рекурсию из КС-грамматики 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’}

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

Исключить левую рекурсию из КС-грамматики 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 };

i=1

S  ® SaA; S  ® AA, S  ® b

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

i=2, j=1

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

j=i-1

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’}

Построение детерминированного конечного автомата по автоматной грамматике

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

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

Задание.   

3.2.1.3.   

Решение:

Исключим  - правила из грамматики.

Запишем грамматику недетерминированного конечного автомата:

K = ({S, A, B, C, D, E}, {0, 1}, , S, {E}), где функции переходов:

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

K’ = ({P₀, P₁, P₂, P₃, P₄}, {1,0}, ’, P₀, {P₃, P₄})

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

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

(P₀, 1) = P₁

(P₁, 0) = P₀

(P₁, 1) = P₂

(P₂, 0) = P₃

(P₃, 0) = P₃

(P₃, 1) = P₄

(P₄, 0) = P₄

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

Цепочки, принадлежащие языку – наборы 1 и 0, в начале которых стоит произвольное количество подцепочек “10” (≥0), далее стоит подцепочка “11”, далее стоит произвольное количество 0(>0), после чего цепочка либо заканчивается, либо стоит 1, после чего стоит произвольное количество 0.

(10)ⁿ11(0)^m(1(0)^k)^p, где n≥0, m>0, k≥0, 0≤p≤1

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

(P₀, 101011000100)

(P₁, 01011000100)

(P₀, 1011000100)

(P₁, 011000100)

(P₀, 11000100)

(P₁, 1000100)

(P₂, 000100)

(P₃, 00100)

(P₃, 0100)

(P₃, 100)

(P₄, 00)

(P₄, 0)

(P₄, )

Построение детерминированного конечного автомата по автоматной грамматике

Построить детерминированный конечный автомат (КА) по автоматной грамматике 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)

Построение детерминированного конечного автомата по автоматной грамматике

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

3.2.1.4. T = { 0, 1 }, N = { S, A, B }, R = { S ® e, S  ® 1S, S  ® 0A, A  ® 1S, A  ® 0B, B  ® e, 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

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

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

d(S,0)=A

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

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

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

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

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

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

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

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

d(p0,0)=p1

d(p0,1)=p2

d(p1,0)=p3

d(p1,1)=p2

d(p2,0)=p1

d(p2,1)=p2

d(p3,0)=p3

d(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.2.8.  Определить детерминированный конечный преобразователь, преобразующий множество цепочек, в которых четное количество нулей ограничено произвольным числом единиц, во множество цепочек { 1ⁿ , где n – число групп с четным количеством нулей}. Цепочки разделяются запятой, последовательность цепочек заканчивается символом "#".

Решение:

1. Определим необходимые для заданного по условию преобразователя состояния:

q₀ – начальное состояние;

q₁–четное количество нулей;

q₂–нечетное количество нулей;

q₃–текущий символ 1 или , ;

q₄–конечное состояние;

2. Опишем функции переходов:

 (q₀, #) = {(q₄, #)}

(q₀, ,) = {(q₃, ,)} 0

(q₃, ,) = {(q₃, ,)}

(q₀, 1) = {(q₃, ε)}

(q₃, 1) = {(q₃, ε)} 0 1 #

(q₃, 0) = {(q₂, ε)} ,

(q₂, 0) = {(q₁, ε)}

(q₁, 0) = {(q₂, ε)} 0 1

(q₂, 1) = {(q₃, ε)}

(q₁, 1) = {(q₃, 1)}

(q₃, #) = {(q₄, #)} 1 #

1 ,

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

Входная цепочка: 110011,1101#

(q_0, 110011,1101#, ε), (q₃,10011,1101#,ε), (q₃,0011,1101#,ε), (q₂,011,1101#,ε), (q₁,11,1101#,ε),

(q₂,1,1101#, 1), (q₃,,1101#, 1),(q₃,1101#, 1,), (q₃,101#, 1,),(q₃,01#, 1,),(q₂,1#, 1,),(q₃,#, 1,),(q₄,#, 1,).

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

Входная цепочка: 110011,1101

(q_0, 110011,1101, ε), (q₃,10011,1101,ε), (q₃,0011,1101,ε), (q₂,011,1101,ε), (q₁,11,1101,ε),

(q₂,1,1101, 1), (q₃,,1101, 1), (q₃,1101, 1,), (q₃,101, 1,), (q₃,01, 1,), (q₂,1, 1,), (q₃,ε, 1,).

Построение детерминированного конечного преобразователя

Определить конечный преобразователь, осуществляющий перевод последовательности составных имен (идентификаторов, разделенных символом ".") в последовательность цепочек 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).

Построение детерминированного конечного преобразователя

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

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

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

d(q0, a) = {(q1, e)}

d(q1, a) = {(q1, e)}

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

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

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

d(q2, a) = {(q1, e)}

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

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

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

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

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

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

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

Построение детерминированного автомата (распознаватель) с магазинной памятью

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

Построить детерминированный автомат с магазинной памятью.

Задание

4.2.1.3. Построить детерминированный магазинный автомат, распознающий цепочки в алфавите { 0,1 } с одинаковым количеством нулей и единиц.

Решение

Функции переходов, для этого автомата будут выглядеть следующим образом:

(q₀, 0, Z) = (q₀, 0Z);

(q₀, 1, Z) = (q₀, 1Z);

(q₀, 0, 0) = (q₀, 00);

(q₀, 1, 1) = (q₀, 11);

(q₀, 1, 0) = (q₀, ε);

(q₀, 0, 1) = (q₀, ε);

(q₀, ε, Z) = (q₁, ε).

q₁ – конечное состояние.

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

(q₀, 110010, Z), (q₀, 10010, 1Z), (q₀, 0010, 11Z), (q₀, 010, 1Z), (q₀, 10, Z), (q₀, 0, 1Z), (q₀, ε, Z),(q₁, ε, Z).

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

(q₀, 1110, Z), (q₀, 110, 1Z), (q₀, 10, 11Z), (q₀, 0, 111Z), (q₀, ε, 11Z). Из текущего состояния не возможно совершить переход.

Построение детерминированного автомата (распознаватель) с магазинной памятью Формулировка задания

Построить детерминированный магазинный автомат, распознающий цепочки из множества { 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)

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

Построение детерминированного автомата (распознаватель) с магазинной памятью

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

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

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

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

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

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

d(q1,1,1)=(q1,11)

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

d(q2,0,0)=(q2,00)

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

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

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

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

d(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.4   Построить детерминированный преобразователь с магазинной памятью, осуществляющий перевод произвольной цепочки из множества { 0ⁿ1ⁿ 0^m1^m..., где n, m,...> 0 } в цепочку вида 1^n+m+ .

Решение

Определим детерминированный преобразователь с магазинной памятью следующим образом:

P= <{q0,q1 },{1,0},{0, Z}, ,Z, q0, q1>

Функции переходов, для этого автомата будут выглядеть следующим образом:

(q₀, 0 , Z) = (q₀, 0Z, ε);

(q₀, 0, 0) = (q₀, 00, ε);

(q₀, 1, 0) = (q₀, ε, 1);

(q₀, ε, Z) = (q₁, ε, ε)

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

(q₀, 0001110011010011, Z), (q₀, 001110011010011, 0Z), (q₀, 01110011010011, 0Z),

(q₀, 1110011010011, 000Z), (q₀, 110011010011, 00Z), (q₀, 10011010011, 0Z), (q₀, 0011010011, Z),

(q₀, 011010011, 0Z), (q₀, 11010011, 00Z), (q₀, 1010011, 0Z), (q₀, 010011, Z), (q₀, 10011, 0Z),

(q₀, 0011, Z), (q₀, 011, 0Z), (q₀, 11, 00Z), (q₀, 1, 0Z), (q₁, ε, Z).

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

(q₀, 01001, Z), (q₀, 1001, 0Z), (q₀, 001, Z), (q₀, 01, 0Z), (q₀, 1, 00Z), (q₀, ε, 0Z). Из текущей конфигурации невозможно совершить переход.

Построение детерминированного преобразователя с магазинной памятью.

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

Построить детерминированный преобразователь с магазинной памятью, осуществляющий перевод произвольной цепочки из множества {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, ε). Из текущей конфигурации невозможно совершить переход

Построение детерминированного преобразователя с магазинной памятью.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

d(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.11. T = { +, *, /, . }, N = { S, T, P, C }, R = { S  S + T, S   T, T  T*P, T P, P   .C., C   /C, C   / };

Решение

Определим функции перехода для МП-автомата:

(q, , S) = {(q, S+T), (q, T)}

(q, , T) = {(q, T*P), (q, P)}

(q, , P) = {(q, .C.)}

(q, , C) = {(q, /C), (q, /)}

(q, +, +) ={( q, )}

(q, *, *) ={( q, )}

(q, /, /) = {( q, )}

(q, ., .) = {( q, )}

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

   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, с }

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

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

d(q,e,S)={(q,SaA),(q,AA),(q,b)}

d(q,e,A)={(q,Asa),(q, Ab),(q, c)}

d(q,α, α)={(q, e)} для α € { a, b, с }

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

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

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

Задание

4.2.4.3. T = { a, b }, N = { S, A, B }, R = { S   AB, S   a, A   BS, A  Sb, B   SA, B   BB, B   a };

Решение

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

Определим функции перехода для расширенного МП-автомата:

(q, , AB) = {(q,S)}

(q, , a) = {(q, S), (q, B)}

(q, , BS) = {(q, A)}

(q, ,Sb) = {(q, A)}

(q, , SA) = {(q, B)}

(q, , BB) = {(q, B)}

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

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

(q, b,) = {(q, b)}

Пример 5.6

Определим расширенный МП-автомат с магазинной памятью, распознающий арифметические выражения из примера 5.3, следующим образом:

P = ({q, r}, {i, +, *, (, )}, {i, +, *, (, ), E, T, M}, , q, , {r}), в котором функция переходов  определяется следующим образом:

 (q, a, ) = {(q, a)} для всех a  ,

 (q, , E + T) = {(q, E)},

 (q, , T) = {(q, E)},

 (q, , T * M) = {(q, T)},

 (q, , M) = {(q, T)},

 (q, , i) = {(q, M)},

 (q, , (E)) = {(q, M)},

 (q, , E) = {(r, )}.

При анализе входной цепочки i + i * i МП-автомат P может выполнить следующую последовательность тактов:

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

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

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, )

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

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

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}, d, q, Z, {r})

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

d(q, e, аA)= (q, S)

d(q, e, Ab)= (q, S)

d(q, e, Sc)= (q, A)

d(q, e, d)= (q, A)

d(q, e, ZS)= (r, e)

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

Определение. Множество ПЕРВЫЙ (FIRST) — множество терминальных символов, которыми начинаются цепочки, выводимые из нетерминала A:

FIRST(A) = {a    A _l⁺ a, где   (  )^*}.

Определение. Множество СЛЕДУЮЩИЙ (FOLLOW) — множество терминальных символов, которые могут встретиться непосредственно справа от нетерминала A в некоторой сентенциальной форме:

FOLLOW(А) = {a    S _l^* A и a  FIRST ()}.

Пример 7.1

Для рассмотренной выше грамматики с правилами

(1)	S		aAS		(3)	A		cAS
(2)	S		b		(4)	A		

множество FIRST(A) = {c}, а множество FOLLOW(A) = {a, b}, так как непосредственно справа от нетерминала A в сентенциальных формах может находиться символ S и FIRST(S) = {a, b}.

Определение. КС-грамматика G = (N, S, P, S) является LL(1)-грамматикой тогда и только тогда, когда для каждого A-правила грамматики

A  ₁  ₂  …  _n, n  1

выполняются следующие условия:

1. Множества FIRST(₁), FIRST (₂), …, FIRST (_n) попарно не пересекаются.

2. Если _i ^* , то FIRST (_j) ∩ FOLLOW(A) =  для 1  j  n, i  j.

Важным следствием этого определения является то, что леворекурсивная грамматика не может быть LL(1)-грамматикой.

Другое важное свойство LL(1)-грамматики – ее однозначност.

Алгоритм 7.1. Алгоритм построения управляющей таблицы М для LL(1)-грамматики.

Вход. LL(1)-грамматики G = (N, S, Р, S).

Выход. Корректная управляющая таблица M для грамматики G.

Описание алгоритма.

Таблица M определяется на множестве (N  S  {^})  (  {}) по следующим правилам:

3. Если A   – правило вывода грамматики с номером i, то М(А, а) = (, i) для всех a   , принадлежащих множеству FIRST().

Если   FIRST(), то М(А, b) = (, i) для всех b  FOLLOW(A).

1. М(a, a) = ВЫБРОС для всех a.

2. М(, ) = ДОПУСК.

3. В остальных случаях M(X, a) = ОШИБКА для X  (    {}) и a    {}.

Конец алгоритма

Рассмотрим, как строится управляющая таблица М для грамматики G₁ с правилами:

Управляющая таблица должна содержать 11 строк, помеченных символами из множества (N È S È {^}), и 6 столбцов, помеченных символами из множества (S È {e}).

Заполнение таблицы начнем с выполнения шага 1 алгоритма.

Шаг 1. Будем строить таблицу построчно, для чего последовательно рассматриваем все нетерминальные символы.

4. Нетерминал E.

Этому символу соответствует правило вывода грамматики

1. E  TE. Так как FIRST(TE) = { (, i}, то следовательно,

M(E, ( ) = M(E, i) = ( TE, 1).

4. Для нетерминала E в грамматике имеется два правила вывода: (2) и (3).

• Для правила (2) E  + TE множество FIRST(+TE) = {+} и, следовательно, M(E, +) = (+TE, 2).

• Правило (3) имеет пустую правую часть, поэтому необходимо вычислить множество символов, следующих за нетерминалом E¢ в сетенциальных формах. Построив левый вывод E  TE¢  PT¢E¢  (E)T¢E¢  (TE¢)TE¢…, получим FOLLOW(E) = { ), e).

Таким образом, M(E¢, ) ) = M(E¢, ) = (, 3).

• Выполняя шаг 1 алгоритма для нетерминалов Т, T¢’ и Р, получим:

Правило грамматики				Множество				Значение M
(4)	T		PT¢	FIRST(PT¢)	=	{ (, i)}	M(T¢, ( ) = M(T¢, i) = (PT¢, 4)
(5)	T		*PT¢	FIRST(*PT¢)	=	{*}	M(T¢, *) = (*PT¢, 5)
(6)	T		e	FOLLOW(T¢)	=	{+, ), e}	M(T¢,+) = M(T¢, )) = M(T¢,e) = (e,6)
(7)	P		i	FIRST(i)	=	{i}	M(P, i ) = (i, 7)
(8)	P		(E)	FIRST((E))	=	{(}	M(P, ( ) = ((E), 8)

Шаг 2. Далее всем элементам таблицы, находящимся на пересечении строки и столбца, отмеченным одним и тем же терминальным символом, присвоим значение ВЫБРОС.

Шаг 3. Элементу таблицы М(, ) припишем значение ДОПУСК.

Шаг 4. Остальным элементам таблицы присвоим значение ОШИБКА.

В заключение, можно сравнить таблицу, построенную при помощи алгоритма 7.1, с управляющей таблицей, приведенной на рис. 7.5 и убедиться, что они совпадают. В [3] доказано, что алгоритм 7.1 строит корректную управляющую таблицу.

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

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

Задание

5.2.3. ^ ^

Решение

1. ,

2. ,

3. ,

4. .

Определим множества FIRST и FOLLOW для всех нетерминальных символов

Построим управляющую таблицу для грамматики G.

Контрольный пример – разбор цепочки “(a^a)^a”, порождаемой этим алгоритмом.

((a^a)^a, S┴ , ) -> M((S)R,2)

((a^a)^a,(S)R┴ ,2) ->ВЫБРОС

(а^а)^а, S)R┴ ,2) -> M(aR,1)

(a^a)^a, aR)R┴ , 21) ->ВЫБРОС

(^a)^a, R)R┴ , 21) -> M(^aR, 3)

(^a)^a, ^aR)R┴ , 213) ->ВЫБРОС

(a)^a, aR)R┴ , 213) ->ВЫБРОС

()^a, R)R┴ , 213) -> M( ,4)

()^a, )R┴ , 2134) ->ВЫБРОС

(^a, R┴ , 2134) -> M(^aR, 3)

(^a, ^aR┴ , 21343) ->ВЫБРОС

(a, aR┴ , 21343) ->ВЫБРОС

( , R┴, 21343) ->M( ,4)

( ,┴ , 213434) ->ДОПУСК

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

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

1. S  ® aAB,

2. S  ® bBS,

3. S  ® e,

4.A  ® cBS,

5.A ® e,

6.B  ® dB,

7.B  ® e

S® β

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

A® β

FIRST(β)={c, e}

B® β

FIRST(β) = {d, e}

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

acdbd

(acdbd,S┴, e)->

(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)->

(e,BSB┴,146726)->

(e,SB┴,1467267)->

(e,B┴,14672673)->

(e,┴,146726737)

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

ВЫБРОС

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

ВЫБРОС

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

ВЫБРОС

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

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

ВЫБРОС

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

ВЫБРОС

M(B, e)=(e,7)

M(S, e)=(e,3)

M(B, e)=(e,7)

ДОПУСК

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

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

Построить управляющую таблицу и промоделировать работу 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)

ДОПУСК

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

Пусть Х_i и Z_i – грамматические вхождения символов Х и Z в правую часть i-го правила, a Y_j – грамматическое вхождение символа Y в правую часть j-го правила. Определим множество OFIRST (Y_i) (входит первым), в которое включим Y_j и все грамматические вхождения, которыми могут начинаться цепочки, выводимые из Y.

OFIRST(Y_i) = {Y_j }  {X_i  Y ^ A  X и Xi – самое левое грамматическое вхождение в правую часть правила A  X}.

Замечание

Если в грамматике есть правила с пустой правой частью, то на последнем шаге вывода они не применяются.

Используя множества OFIRST, определим отношение OBLOW (входит под) следующим образом:

5. X_i OBLOW Y_j – это множество {(X_i, Y_j)  A X_iZ_i  P и Y_j OFIRST (Z_i) }.

 OBLOW Y_j – это множество {(,Y_j)  Y_j OFIRST (S₀) }, где S₀ – начальное вхождение.

Отношение X_i OBLOW Y_j определяет множество Q грамматических вхождений X_i, для которых представляющие их магазинные символы могут встретиться в магазине непосредственно под символом, представляющим Y_j.

Отношение OBLOW будем задавать с помощью матрицы, содержащей n столбцов и n+1 строк, где n – число грамматических вхождений пополненной грамматики G. Первые n строк и столбцы матрицы отмечены грамматическими вхождениями, а последняя строка – маркером дна магазина. Если X_i OBLOW Y_j, то элемент матрицы, расположенный в строке X_i и столбце Y_j, равен 1.

Построим матрицу отношения OBLOW для грамматики с правилами:

Непосредственно из правил вывода грамматики (1) и (4) получим:

A₁ OBLOW b₁ и B₄ OBLOW b₄.

Из определения отношения OBLOW следует, что  OBLOW Yj тогда и только тогда, когда Yj  OFIRST(S₀). Из S можно вывести цепочки S  a₁A₁b₁ и S  c₂. Следовательно, OFIRST(S₀) = {a₁, c₂, S₀} и  OBLOW а₁,  OBLOW c₂ и  OBLOW S₀.

Рассмотрим правило грамматики с номером (1). Из определения отношения OBLOW следует, что

a₁ OBLOW Y_j для всех Y_j  OFIRST(A₁).

Из А можно вывести цепочки:

A  b₃S₃, A  B₄b₄  c₆b₄, A  B₄b₄  a₅A₅b₄.

Следовательно, OFIRST(А₁) = {a₅, b₃, c₆, A₁, B₄} и a₁ OBLOW a₅, a₁ OBLOW b₃, a₁ OBLOW c₆, a₁ OBLOW A₁, a₁ OBLOW B₄.

Поступая подобным образом для правил (3) и (6), получим матрицу отношения OBLOW:

Опишем алгоритм построения управляющей таблицы T LR(0)-анализатора (множества LR(0)-таблиц) для LR(0)-грамматики, не содержащей правил с пустой правой частью. Этот алгоритм можно также использовать для проверки принадлежности КС-грамматики классу LR(0).

Алгоритм 8.2. Построение множества LR(0)-таблиц.

Вход. LR(0)-грамматика G = (N, S, Р, S), не содержащая -правил.

Выход. Множество T LR(0)-таблиц для грамматики G или сообщение о том, что грамматика G не является LR(0)-грамматикой.

Описание алгоритма.

6. Построить пополненную грамматику G для исходной грамматики G.

7. Вычислить отношения OBLOW для грамматических вхождений грамматики G.

8. Определить функции переходов g(Х) следующим образом:

• Построить таблицу, содержащую по одному столбцу для каждого символа из     {} и одной отроке для каждого грамматического вхождения грамматики G¢ и маркера дна. Элемент в строке, помеченной грамматическим вхождением Х_i или маркером дна , и столбце, отмеченном символом грамматики Y, должен содержать все грамматические вхождения, для которых справедливо отношение Х_i OBLOW Y_j. Заметам, что некоторые элементы построенной таким образом таблицы могут содержать более одного грамматического вхождения, т.е. таблица может быть недетерминированной.

• Интерпретируя построенную таблицу как таблицу конечного автомата (состояния - грамматические вхождения и маркер дна (начальное состояние), а входные символы - символы из     {}), определить тип автомата: детерминированный или недетерминированный. Недетерминированный автомат преобразовать в эквивалентный ему детерминированный автомат.

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

В качестве символов алфавита V_p можно использовать любые символы, не являющиеся символами грамматики G¢ Для сохранения наглядности цепочек, представимых магазином, будем считать, что символы из V_p совпадают по написанию с соответствующими грамматическими вхождениями. Если магазинный символ представляет множество грамматических вхождений, то индексы магазинных символов будем обозначать строчными латинскими буквами.

• Заменить совокупности грамматических вхождений, отмечающих состояния автомата, соответствующими символами из V_p.

Полученная таблица представляет собой таблицу функций переходов g(X) LR(0)-анализатора, причем элементы таблицы, соответствующие переходу в пустое множество состояний, имеют значение ОШИБКА.

4. Определить функции действия f(a) для всех магазинных символов, каждому из которых соответствует одна строка таблицы. Количество столбцов таблицы f(a) определяется количеством символов множества S È{e}. Элементы таблицы f(a) определяются следующим образом.

• Если магазинному символу Т соответствует единственное вхождение S₀, то в строке, отмеченной символом Т, f() = ДОПУСК, а все остальные элементы – ОШИБКА.

• Если магазинному символу Т соответствует только одно грамматическое вхождение Xi, являющееся самым правым вхождением в i-е правило вывода грамматики G, то все элемента строки, помеченной Т, имеют значение (СВЕРТКА, i).

• Если магазинному символу Т соответствует маркер дна магазина  или все грамматические вхождения, представляемые символом Т, не являются самыми правыми в своих правилах, то в строке, отмеченной Т, f() = ошибка, а значения остальных элементов – ПЕРЕНОС.

• Если множество вхождений, соответствующее магазинному символу Т, содержит начальное вхождение S₀ и хотя бы еще одно вхождение, отличное от S₀, которое не является самым правым в своем правиле, то в строке, отмеченной Т, f() = ДОПУСК, а значение всех остальных элементов – ПЕРЕНОС.

Если имеется множество грамматических вхождений, не удовлетворяющих перечисленным выше условиям, то G не является LR(0)-грамматикой.

Если построение f(a) закончено успешно, то грамматика является LR(0)-грамматикой, а таблица, полученная объединением таблиц, задающих функции f(a) и g(X) – управляющей таблицей T LR(0)-анализатора.

Конец алгоритма

Построим управляющую таблицу LR(0)-анализатора для грамматики, имеющей следующие правила:

Шаг 1. Определим пополненную грамматику для грамматики G:

G= (N  {S}, S, Р  {S  E}, S).

Шаг 2. Вычислим отношение OBLOW для грамматических вхождений грамматики G¢. Матрица отношения OBLOW имеет вид:

	E0	E1	+1	T1	T2	(3	E3	)3	i4
E0
E1			1
+1				1		1			1
T1
T2
(3		1			1	1	1		1
E3								1
)3
i4
	1	1			1	1			1

Шаг 3. Определим функции переходов g(X).

• Используя отношение OBLOW, построим таблицу переходов конечного (в данном случае недетерминированного) автомата:

  	E	T	(	)	i	+
  E0
  E1						+1
  +1		T1	(3		i4
  T1
  T2
  (3	E1, E3	T2	(3		i4
  E3				)3
  )3
  i4
  	E0, E1	T2	(3		i4

• Преобразуем недетерминированный автомат в эквивалентный ему детерминированный автомат, таблица переходов которого будет иметь вид:

  	E	T	(	)	i	+
  {}	(E0, E1}	{T2}	{(3}		{i4}
  {E0, E1}						{+1}
  {T2}
  {(3}	{ E1, E3}	{T2}	{(3}		{i4}
  {i4}
  {+1}		{T1}	{(3}		{i4}
  {E1, E3}				{)3}		{+1}
  {T1}
  {)3}

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

  	{E0, E1 }	{E1, E3 }	{}	{T2}	{(3}	{i4}	{+1}	{T1}	{)3}
  Vp	Ex	Ey		T2	(3	i4	+1	T1	)3

• Тогда функции переходов g(Х) LR(0)-анализатора для грамматики G имеет вид:

g(X)	E	T	(	)	i	+
	Ex	T2	(3		i4
Ex						+1
T2
(3	Ey	T2	(3		i4
i4
+1		T1	(3		i4
Ey				)3		+1
T1
)3

Шаг 4. Определим функции действия f(a). Построим таблицу, содержащую по одной строке для каждого магазинного символа и одному столбцу для каждого символа a  (  {}).

Для строки таблицы, отмеченной символом , соответствующее множество грамматических вхождений состоит из единственного символа , поэтому в этой отроке f() = ОШИБКА, а значения остальных элементов – ПЕРЕНОС.

Множество грамматических вхождений, соответствующих магазинному символу Е_x, содержит два элемента: Е₀ и Е₁. Так как в это множество входит начальное вхождение E₀, а вхождение Е₁ не является самым правым в правиле грамматики (1), то f() = ДОПУСК, а остальные элементы строки, отмеченные символом Е_x, имеют значение ПЕРЕНОС.

Магазинному символу Т₂ соответствует единственное грамматическое вхождение Т₂, которое является самым правым в правиле вывода (2) грамматики. Следовательно, значение всех элементов строки, помеченной Т₂, – (СВЕРТКА, 2).

Поступая подобным образом для остальных строк, получим таблицу функций переходов f(a):

f(a)	(	)	i	+	
	П	П	П	П
Ex	П	П	П	П	Д
T2	С,2	С,2	С,2	С,2	С,2
(3	П	П	П	П
i4	С,4	С,4	С,4	С,4	С,4
+1	П	П	П	П
Ey	П	П	П	П
T1	С,1	С,1	С,1	С,1	С,1
)3	С,3	С,3	С,3	С,3	С,3

Поскольку при построении функции переходов f(a) не возникло конфликтных ситуаций, рассмотренная грамматика является LR(0)-грамматикой. Объединив функции g(X) и f(a) в одну таблицу, получим для управляющую таблицу T LR(0)-анализатора.

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

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

Задание

6.1.3.   T { a, (, ), , }, N = { S, R}, R = { S   a, S   (SR, R   ,SR, R   )};

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

Дополним исходную грамматику правилом S’ S, тем самым получим пополненную грамматику G’ = <T, N’, S’, R’ >:

T { a, (, ), , }, N’ = { S’, S, R}, R = { S’S, S   a, S   (SR, R   ,SR, R   )};

Пронумеруем правила:

0. S’S

1. S   a

2. S   (SR

3. R   ,SR

4. R   )

Рассмотрим правило с №2: (₂OBLOWY_jдля всех Y_jϵ OFIRST(S₂).

Из Sможно вывести цепочки Sa; S (SR.

Следовательно, OFIRST(S₂) = { a₁, (₂, S₂} и(₂OBLOW a₁, (₂OBLOW (₂, (₂OBLOW S₂.

Поступая подобным образом для правила 3, получим матрицу отношения OBLOW.

Определим функцию переходов g(X): используя отношение OBLOW, построим таблицу переходов конечного автомата.

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

Определим функции действия f(a). Построим таблицу, содержащую по одной строке для каждого магазинного символа и по одному столбцу для каждого символа aϵ (T˅ {ε})

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

(┴, (a,a,a) ,ε)

(┴(₂ , a,a,a),ε)

(┴(₂a₁, ,a,a), ε)

(┴(₂S₂, ,a,a), 1)

(┴(₂S₂,₃ , a,a), 1)

(┴(₂S₂,₃a₁, , a), 1)

(┴(₂S₂,₃S₃, ,a), 11)

(┴(₂S₂,₃S₃,₃ ,a), 11)

(┴(₂S₂,₃S₃,₃a₁, ), 11)

(┴(₂S₂,₃S₃,₃S₃, ), 111)

(┴(₂S₂,₃S₃,₃S₃), ε, 111)

(┴(₂S₂,₃S₃,₃S₃R₃, ε, 1114)

(┴(₂S₂,₃S₃R₃, ε, 11143)

(┴(₂S₂R₂, ε, 111433)

(┴S₀, ε, 1114332)

ДОПУСК.

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

Усовершенствуем алгоритм 8.2 построения управляющей таблицы так, чтобы получить анализатор для некоторого класса грамматик, не принадлежащих классу LR(0)-грамматик. Этот класс грамматик является подклассом LR(1)-грамматик и получил название SLR(1)-грамматик без -правил. Буква S в названии грамматики является сокращением английского слова Simple (простой).

Начнем с рассмотрения примера.

Построим управляющую таблицу LR(0)-анализатора для грамматики G₀, правила вывода которой после пополнения имеют вид:

В процессе построения анализатора получаем:

• матрицу отношения OBLOW, определенную на множестве грамматических вхождений пополненной грамматики:

	E0	E1	+1	T1	T2	T3	3	P3	P4	(5	E5	)5	i6
E0
E1			1
+1				1		1			1	1			1
T1
T2
T3							1
3								1		1			1
P3
P4
(5
E5		1			1	1			1	1	1		1
)5												1
i6
	1	1			1	1			1	1			1

таблицу переходов недетерминированного конечного автомата:

	+		(	)	i	E	T	P
			(5		i6	E0, E1	T2, T3	P4
E0
E1	+1
+1			(5		i6		T1, T3	P4
T1
T2
T3		3
3			(5		i6			P3
P3
P4
(5			(5		i6	E1, E5	T2, T3	P4
E5
)5				)5
i6

• таблицу переходов детерминированного конечного автомата:

  	+		(	)	i	E	T	P
  {}			{(5}		{i6}	{E0, E1}	{T2, T3}	{P4}
  {(5}			{(5}		{i6}	{E1, E5}	{T2, T3}	{P4}
  {i6}
  {E0, E1}	{+1}
  {T2, T3}		{*3}
  {P4}
  {E1, E5}	{+1}			{)5}
  {+1}			{(5}		{i6}		{T1, T3}	{P4}
  {3}			{(5}		{i6}			{P3}
  {)5}
  {T1, T3}		{3}
  {P3}

• таблицу кодирования магазинных символов:

{Eo,E1}

{E1,E5}

{T2,T3}

{T1,T3}

{P3}

{P4}

{+1}

{3}

{(5}

{)5}

{i6}

{}

Vp

Ex

Ey

Tx

Ty

P3

P4

+1

3

(5

)5

i6

