Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 22 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

Составители: 

Рубрика: 

22
Пример 4.4. Дана грамматика ),},,,{},1,0({
S
P
B
A
S
G
=
с правилами :
P
ε
ε
|1)3;|0)2;)1
B
B
A
A
A
B
S
→→→ . Преобразуем ее в эквивалентную
грамматику по алгоритму 4.4.
Шаг 1. N
0
= {A, B};
N
1
= {S, A, B};
N
2
= {S, A, B}.
Т.к. N
1
= N
2
, то искомое множество построено и N = {S, A, B}.
Шаг 2, 3. Множество :
′
1)
B
A
A
B
S
||→ ; 2) 0|0
A
A
→ ; 3) .1|1
B
B
→
Шаг 4. Т.к.
N
S
∈
, то введем новый нетерминал С и пополним множество
P
′
правилом вида
ε
|
S
C
→ . Результирующая грамматика будет иметь вид:
),},,,,{},1,0({ CPCBASG =
′
с правилами :
′
;||)2;|)1
B
A
A
B
S
S
C
→→
ε
1|1)4;0|0)3
B
B
A
A
→→ .
Алгоритм 4.5. Устранение цепных правил
Вход: КС-грамматика ),,,( SPVVG
N
T
= .
Выход: Эквивалентная КС-грамматика
),,,( SPVVG
N
T
′′
′
=
′
без цепных
правил, т.е. правил вида
B
A
→ , где
N
VBA
∈
,.
Шаг 1. Для каждого нетерминала
A
вычислить множество выводимых из
него нетерминалов, т.е. множество ,*|{ BABN
A
⇒= где }.
N
VB
∈
1.1
Положить }.{
0
AN
A
=
1.2
Вычислить }.,,)(|{
11
N
A
i
A
i
A
i
VCNBPCBCNN ∈∈∈→∪=
−
−
1.3
Если
A
i
A
i
NN
1−
≠ , то положить i:=i+1 и перейти к пункту 1.2, иначе
считать .
A
i
A
NN =
Шаг 2. Построить множество
P
′
так: если
P
B
∈
→ )(
α
не является цеп-
ным правилом )(
N
V∉
α
, то включить в
P
′
правило
α
→
A
для каждого
A
, та-
кого, что
A
N
B
∈ .
Пример 4.5. Грамматика ),},,,{},,({
L
P
N
M
L
n
G
+
=
с правилами :
P
n
N
N
N
M
M
L
|)3;)2;)1
+
→→→ . Преобразуем ее в эквивалентную
грамматику G
′
по алгоритму 4.5.
Шаг 1. };{
0
LN
L
=
};,{
1
MLN
L
=
};,,{
2
NMLN
L
=
}.,,{
3
NMLN
L
=
Т.к.
LL
NN
32
= , то }.,,{ NMLN
L
=
};{
0
MN
M
= 
       Пример 4.4. Дана грамматика G = ({0, 1}, {S , A, B}, P, S ) с правилами P :
1) S → AB; 2) A → 0 A | ε ; 3) B → 1B | ε . Преобразуем ее в эквивалентную
грамматику по алгоритму 4.4.
       Шаг 1. N0 = {A, B};
                N1 = {S, A, B};
                N2 = {S, A, B}.
       Т.к. N1 = N2, то искомое множество построено и N = {S, A, B}.
       Шаг 2, 3. Множество P′ : 1) S → AB | A | B ; 2) A → 0A | 0 ; 3) B → 1B | 1.
       Шаг 4. Т.к. S ∈ N , то введем новый нетерминал С и пополним множество
P′ правилом вида C → S | ε . Результирующая грамматика будет иметь вид:
G ′ = ({0, 1}, {S , A, B, C}, P, C ) с правилами P′ : 1) C → S | ε ; 2) S → AB | A | B;
3) A → 0 A | 0; 4) B → 1B | 1.

                      Алгоритм 4.5. Устранение цепных правил
     Вход: КС-грамматика G = (VT , V N , P, S ) .
     Выход: Эквивалентная КС-грамматика G ′ = (VT , VN′ , P′, S ′) без цепных
правил, т.е. правил вида A → B , где A, B ∈V N .
      Шаг 1. Для каждого нетерминала A вычислить множество выводимых из
него нетерминалов, т.е. множество N A = {B | A ⇒ *B, где B ∈ VN }.
      1.1 Положить N 0A = { A}.
      1.2 Вычислить N iA = N iA−1 ∪ {C | ( B → C ) ∈ P, B ∈ N iA−1, C ∈ VN }.
     1.3 Если N iA ≠ N iA−1 , то положить i:=i+1 и перейти к пункту 1.2, иначе
считать N A = N iA .
     Шаг 2. Построить множество P ′ так: если ( B → α ) ∈ P не является цеп-
ным правилом (α ∉V N ) , то включить в P ′ правило A → α для каждого A , та-
кого, что B ∈ N A .
      Пример 4.5. Грамматика G = ({+, n}, {L, M , N }, P, L) с правилами P :
1) L → M ; 2) M → N ; 3) N → N + | n . Преобразуем ее в эквивалентную
грамматику G′ по алгоритму 4.5.
      Шаг 1. N 0L = {L};
             N1L = {L, M };
               N 2L = {L, M , N };
               N 3L = {L, M , N }.
      Т.к. N 2L = N 3L , то N L = {L, M , N }.

               N 0M = {M };

22

Страницы