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

UptoLike

ВУЗ: 

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

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

Рубрика: 

35
Этап 1. Преобразуем грамматику G в грамматику G′, не содержащую
ε
-
правил:
N
0
= {R};
N
1
= {R}, т.к. N
0
= N
1
, то во множество P
′
войдут правила:
1) S→ TR | T; 2) R
→
+TR | +T | -TR | -T; 3) T→(S) | a | b.
Этап 2. Построение множеств FIRST(1, A) для каждого нетерминала А
представлено в таблице 6.1.
Таблица 6.1 – Построение множеств FIRST(1, A)
FIRST
i
(1, A) 0 1 2 FIRST(1, A)
S T
T, (, a, b T, (, a, b (, a, b
R
+, - +, - +, - +, -
T
(, a, b (, a, b (, a, b (, a, b
Этап 3. Построение множеств FOLLOW(1, A) для каждого нетерминала А
представлено в таблице 6.2.
Таблица 6.2 – Построение множеств FOLLOW(1, A)
Шаг Нетерминалы FOLLOW
i
(1, A) FOLLOW
i
’
(1, A) FOLLOW
i
’’
(1, A)
S
)
), ε ), ε
R
∅ ∅ ∅
0
T R
R, +, - R, +, -
S
), ε ), ε ), ε
R
), ε ), ε ), ε
1
T
R, +, - R, +, -
R, +, -, ), ε
S
), ε ), ε ), ε
R
), ε ), ε ), ε
2
T
R, +, -, ), ε R, +, -, ), ε R, +, -, ), ε
FOLLOW(1, S)
), ε
FOLLOW(1, R)
), ε
FOLLOW(1, T)
+, -, ), ε
Этап 4. Множества FIRST(1, A) и FOLLOW(1, A) для каждого нетерминала
А сведены в таблицу 6.3.
Таблица 6.3 – Множества FIRST(1, A) и FOLLOW(1, A)
A
FIRST(1, A) FOLLOW(1, A)
S
(, a, b
), ε
R
+, -
), ε
T
(, a, b
+, -, ), ε 
     Этап 1. Преобразуем грамматику G в грамматику G′, не содержащую ε-
правил:
     N0 = {R};
     N1 = {R}, т.к. N0 = N1, то во множество P′ войдут правила:
     1) S→ TR | T; 2) R→ +TR | +T | -TR | -T; 3) T→(S) | a | b.
     Этап 2. Построение множеств FIRST(1, A) для каждого нетерминала А
представлено в таблице 6.1.
     Таблица 6.1 – Построение множеств FIRST(1, A)
 FIRSTi(1, A)         0                     1                     2           FIRST(1, A)
     S                T                 T, (, a, b            T, (, a, b         (, a, b
     R               +, -                  +, -                  +, -              +, -
     T             (, a, b               (, a, b               (, a, b           (, a, b
     Этап 3. Построение множеств FOLLOW(1, A) для каждого нетерминала А
представлено в таблице 6.2.
     Таблица 6.2 – Построение множеств FOLLOW(1, A)

Шаг Нетерминалы      FOLLOWi(1, A)             FOLLOWi’(1, A)              FOLLOWi’’(1, A)
         S                    )                          ), ε                    ), ε
 0       R                   ∅                            ∅                       ∅
         T                   R                         R, +, -                 R, +, -
         S                  ), ε                         ), ε                    ), ε
 1       R                  ), ε                         ), ε                    ), ε
         T                R, +, -                      R, +, -               R, +, -, ), ε
         S                  ), ε                         ), ε                    ), ε
 2       R                  ), ε                         ), ε                    ), ε
         T              R, +, -, ), ε                R, +, -, ), ε           R, +, -, ), ε
  FOLLOW(1, S)      ), ε
  FOLLOW(1, R)      ), ε
  FOLLOW(1, T)      +, -, ), ε
      Этап 4. Множества FIRST(1, A) и FOLLOW(1, A) для каждого нетерминала
А сведены в таблицу 6.3.
     Таблица 6.3 – Множества FIRST(1, A) и FOLLOW(1, A)
      A             FIRST(1, A)                  FOLLOW(1, A)
      S                (, a, b                        ), ε
      R                  +, -                         ), ε
      T                (, a, b                     +, -, ), ε

                                                                                             35

Страницы