SLR(1)-грамматики

Напомним, что для любого нетерминала K мы определяли (с. [*]) множество ${\hbox{\rm Послед}}({\hbox{\tt K}})$ тех терминалов, которые могут стоять непосредственно за ${\hbox{\tt K}}$ в выводимом (из начального нетерминала) слове; в это множество добавляют также символ EOI, если нетерминал K может стоять в конце выводимого слова.


$\scriptstyle{\blacktriangleright}$ 14.3.1. Доказать, что если в данный момент LR-процесса последний символ стека S равен K, причем процесс этот может в дальнейшем успешно завершиться, то Next принадлежит ${\hbox{\rm Послед}}({\hbox{\tt K}})$.

Решение. Этот факт является непосредственным следствием определения (вспомним соответствие между правыми выводами и LR-процессами).$\scriptstyle\blacktriangleleft$


Рассмотрим некоторую грамматику, произвольное слово S из терминалов и нетерминалов и терминал x. Если множество ${\hbox{\rm Сост}}({\hbox{\tt S}})$ содержит ситуацию, в которой справа от подчеркивания стоит терминал x, то говорят, что для пары $\langle{\hbox{\tt S}},{\hbox{\tt x}}\rangle$ возможен сдвиг. Если в ${\hbox{\rm Сост}}({\hbox{\tt S}})$ есть ситуация ${\hbox{\tt K}}\to{\hbox{\tt U}}\_\,$, причем x принадлежит ${\hbox{\rm Послед}}({\hbox{\tt K}})$, то говорят, что для пары $\langle{\hbox{\tt S}},{\hbox{\tt x}}\rangle$ SLR(1)-возможна свертка (по правилу ${\hbox{\tt K}}\to{\hbox{\tt U}}$). Говорят, что для пары $\langle{\hbox{\tt S}},{\hbox{\tt x}}\rangle$ возникает SLR(1)-конфликт типа     сдвиг/свертка, если возможны и сдвиг, и свертка. Говорят, что для пары $\langle{\hbox{\tt S}},{\hbox{\tt x}}\rangle$ возникает SLR(1)-конфликт типа свертка/свертка, если есть несколько правил, по которым возможна свертка.

Грамматика называется SLR(1)-грамматикой, если в ней нет     SLR(1)-конфликтов типа сдвиг/свертка и свертка/свертка ни для одной пары $\langle{\hbox{\tt S}},{\hbox{\tt x}}\rangle$.


$\scriptstyle{\blacktriangleright}$ 14.3.2. Пусть дана SLR(1)-грамматика. Доказать, что у любого слова существует не более одного правого вывода. Построить алгоритм проверки выводимости в SLR(1)-грамматике.

Решение. Аналогично случаю LR(0)-грамматик, только при выборе между сдвигом и сверткой учитывается очередной символ (Next).$\scriptstyle\blacktriangleleft$


$\scriptstyle{\blacktriangleright}$ 14.3.3. Проверить, является ли приведенная выше на с. [*] грамматика (с нетерминалами E, T и F)  SLR(1)-грамматикой.

Решение. Да, является, так как оба конфликта, мешающие ей быть LR(0)-грамматикой, разрешаются с учетом очередного символа: и для слова T, и для слова E+T сдвиг возможен только при ${\hbox{\tt Nеxt}}={\hbox{\tt *}}$, а символ * не принадлежит ни ${\hbox{\rm Послед}}({\hbox{\tt E}}) = \{{\hbox{\tt EOI}},{\hbox{\tt +}},{\hbox{\tt )}}\}$, ни ${\hbox{\rm Послед}}({\hbox{\tt T}}) = \{{\hbox{\tt EOI}},{\hbox{\tt +}},{\hbox{\tt *}},{\hbox{\tt )}}\}$,и поэтому при ${\hbox{\tt Nеxt}}={\hbox{\tt *}}$ свертка невозможна.$\scriptstyle\blacktriangleleft$


pvv
1/8/1999