Пример 29

Пример 28

Любая SLR(l)-грамматика однозначна, но имеется множество однозначных гpaмматик, не являющихся SLR(l). Рассмотрим грамматику с продукциями

S → L = R

S → R

L → * R (7.3)

L → id

R → L

Каноническая система множеств LR(1) пунктов для этой грамматики показана на рис. 41.

I ₀: S’ → •S

S → •L=R

S → •R

L → •*R

L → • id

R → •L

I ₁: S’ → •S

I ₂: S → L•=R

R → L•

I ₃: S → R•

I ₄: L → * •R

R → •L

L → •*R

L → • id

I ₅: L → id •

I ₆: S → L=•R

R → •L

L → •*R

L → • id

I ₇: L → *R •

I ₈: R → L •

I ₉: S → L=R•

Рис. 41. Каноническая LR(0)-систeмa грамматики (7.3)

Рассмотрим множество пунктов I ₂. Первый пункт в этом множестве устанавливает action[2, =] как "перенос 6". Поскольку FOLLOW(R) содержит "=" (чтобы увидеть это, рассмотрите S=>L = R => *R = R), второй пункт определяет action[2, =] как "свертка R → L". Следовательно, запись action[2, =] определена дважды, а поскольку для нее име­ется и запись переноса, и запись свертки, состояние 2 приводит к конфликту пере­нос/свертка при входном символе =.

Грамматика (7.3) не является неоднозначной. Обнаруженный конфликт порождается тем, что метод SLR недостаточно мощный, чтобы запомнить левый контекст, необходи­мый для принятия решения о действиях синтаксического анализатора при входном сим­воле = и просмотренной строке, выводимой из L.

В примере 28 в состоянии 2 был пункт R → L•, который мог соответствовать приведенной выше продукции А → α, и а мог быть знаком =, принадле­жащим FOLLOW(R). Таким образом, SLR-анализатор в состоянии 2 с очередным вход­ным символом = вызывает свертку по продукции R→L (вызывается также и перенос — в соответствии с пунктом S → L • =R в состоянии 2). Однако в грамматике из примера 28 правосентенциальная форма, начинающаяся с R=..., отсутствует. Следовательно, со­стояние 2, соответствующее только активному префиксу L, не должно вызывать свертку этого L в R.

В состоянии можно содержать дополнительную информацию, которая позволит ис­ключить некоторые из таких некорректных сверток по продукции А → α. Разделяя при необходимости состояния, можно заставить каждое состояние LR-анализатора точно указывать, какой входной символ может следовать за основой α (для которой существует возможная свертка в А).

Дополнительная информация внедряется в состояние путем переопределения пунктов для включения терминального символа в качестве второго компонента. Общий вид пункта становится [А → α•β, а], где А → αβ представляет собой продукцию, а — терми­нал или маркер конца строки $. Такой объект назовем LR(1)-пунктом. Здесь 1 означает длину второго компонента, называемого предпросмотром пункта. Предпросмотр не играет роль в пункте вида [А → α•β, а], где β≠λ, однако пункт [А → α•, а] вызывает свертку по продукции А → α только тогда, когда очередной входной ной символ — а. Следовательно, свертка по продукции А → α выполняется только при тех входных символов а, для которых [А → α•, а] является LR(1)-пунктом в состоянии на вершине стека. Множество таких а всегда будет подмножеством FOLLOW(A), но может быть и собственным подмножеством.

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