Пример 26

Построение множеств пунктов

Пример 25

Операция goto

Пример 24

Рассмотрим расширенную грамматику арифметических выражений:

Е' → Е

Е → Е+Т | Т (7.2)

Т → T*F | F

F → (E) | id

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

(1) E→E+T

(2) E→Т

(3) T→ T*F

(4) T→F

(5) T→ (E)

(6) T→ id

Если I представляет собой множество из одного пункта {[E' → •E]}, то closure(I) со­держит пункты

E'→	E
Е →	•E+T
Е →	•T
Т →	•T*F
Т →	•F
F →	• (E)
F →	•id

Здесь E' → •E помещается в closure(I) в соответствии с правилом (1). Поскольку Е расположено непосредственно за точкой, согласно правилу (2) добавляются также E-продукции с точкой слева, т.е. E → • Е+Т и Е→ •Т. Теперь, поскольку среди пунктов имеется Т, следующее за точкой, мы добавляем Т→ • T*F и Т→ •F и, аналогично, F → •(E) и F → • id. Больше добавлять в closure(I) нечего.

Второй функцией является goto(I, X), где I является множеством пунктов, а X — символом грамматики, gotо(I, X) определяется как замыкание множества всех пунк­тов [А → αX • β], таких, что [А → α • Xβ] принадлежит множеству I.

Если I представляет собой множество из двух пунктов {[E ' →Е • ],[Е → E•+T]}, то goto(I, +) состоит из

Е→Е+ • Т

E→ • T*F

E→ • F

E → •(E)

E → • id

Вычислили goto(I, +), рассмотрев пункты из I, у которых сразу за точкой идет +. Таким пунктом является Е → Е • +Т, в отличие от пункта Е' → Е •. Мы перемещаем точку за символ +, получая {E → Е+ • Т}, и рассматриваем замыкание этого множества.

Строим С— каноническую систему множества LR(0)-пунктов для расширенной грамматики G'.

Каноническая система множеств LR(0)-пунктов для грамматики (7.2) из примеpa на рис. 37, а функция goto в виде диаграммы переходов детерминированного конечного автомата — на рис. 38.

I ₀: E’ → •E

E → •E+T

E → •T

T → •T*F

T → •F

F → •(E)

F → • id

I ₁: E’ → E•

E → E•+T

I ₂: E → T•

T → T•*F

I ₃: T → F•

I ₄: F → (•E)

E → •E+T

E → •T

T → •T*F

T → •F

F → •(E)

F → • id

I ₅: F → id •

I ₆: E → E+•T

T → •T*F

T → •F

F → •(E)

F → • id

I ₇: T → •T*F

F → •(E)

F → • id

I ₈: F → •(E)

E → •E+T

I ₉: E → E+T•

T → T•*F

I ₁₀: T → T*F•

I ₁₁: F → (E) •

Рис. 37. Каноническая LR(0)-система для грамматики (7.2)

Рис. 38. Диаграмма переходов детерминированного конечного автомата для активных префиксов

Дата добавления: 2014-12-27