Языки и трансляции. Мартыненко Б.К. - 186 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

184
поскольку правый контекст для S есть ε. Другого правила для S, в котором
справа встречается нетерминал S, не существует. Поэтому σ
0
’
(S, S)={{ε}}.
Построение σ
0
’(S, A): существует только одно правило с нетерминалом S в
левой части и нетерминалом A — в правой. Это правило S → AS. Вычисляется
1
FIRST
G
от правого контекста A, т.е.
1
FIRST
G
(S)={ε, a, b}. Соответственно
σ
0
’(S, A)={{ε, a, b}}.
Построение σ
0
’(A, S): не существует ни одного правила с нетерминалом A
в левой части и нетерминалом S — в правой. Поэтому σ
0
’(A, S)=∅.
Построение
σ
0
’(A, A): имеется только одно продуктивное правило A → aA,
дающее по пустому правому контексту A значение σ
0
’(A, A)={{ε}}.
Шаг 2. Построение σ
1
’(S, S): имеем правило для S → AS, в котором справа
два нетерминала — два источника для пополнения множества σ
0
’(S, S) новыми
членами. Именно, можно вычислить новый член по первому вхождению
нетерминала A в правую часть этого правила и по второму вхождению
нетерминала S:
1
1
FIRST ( ),
G
LL S
′
=⊕
где
,LAS
0
′
′
∈
σ( )=∅.
Ясно, что из этого источника никакого пополнения не получится.
Попробуем воспользоваться другим источником для получения нового члена:
1
1
FIRST ( ),
G
LL
′
=⊕ ε
где
,LSS
0
′
′
∈
σ ( ) ={{ε}}.
Существует единственное множество с помощью которого вычис-
ляется новый член но такое множество уже
есть в
На рис. 2.2 представлена схема соответствия параметров, используемых
при вычислении множества σ
1
’(S, S).
Аналогичным образом пополняются множества σ
0
’(S, A), σ
0
’(A, S) и σ
0
’(A, A).
Однако добавить к этим множествам новые члены, как нетрудно проверить, не
удаётся. Теперь всё готово для тестирования данной
cfg G на предмет её
принадлежности к классу
LL(1)-грамматик. Имеем два альтернативных правила:
S → AS, S → ε для нетерминала S. Требуется вычислить
1
11
(FIRST ( ) ) (FIRST ( ) ),
k
GG
AS L L⊕∩ ε⊕ где L∈σ(S)={{ε}}.
Получаем
{},L
′
=
ε
S → AS
L
’
∈σ
0
’
(A, S )
σ
1
’
(S, S):
L
’
∈σ
0
’
(S, S )
L
’
⊕
1
1
FIRST
G
(S )
L
’
⊕
1
1
FIRST
G
(ε)
11
1
FIRST ( ) { } { } { },
G
LL
′
=⊕ ε=ε⊕ε=ε
,SS
0
′
σ( ).
Рис. 2.2.

Страницы