Теория и реализация языков программирования



             

LR(1)-грамматики - часть 2


Кроме того, работая с LR(k)-грамматикой, мы всегда знаем, допустить ли данную входную цепочку или продолжать разбор.

Пример 4.13. Рассмотрим грамматику G с правилами

S

Sa|a

Согласно определению, G не LR(0)-грамматика, так как из трeх условий

(1)

S' \Rightarrow^0_{G^{'r}} \; S' \Rightarrow_{G^{'r}} \; S;

S' \Rightarrow_{G^{'r}} \; S \Rightarrow_{G^{'r}} \; Sa;

(3)FIRST0(e) = FIRST0(a) = e

не следует, что S'a = S: Применяя определение к этой ситуации, имеем

= e; ? = S; ? = e; ? = e; A = S', B = S; x = e и y = a. Проблема здесь заключается в том, что нельзя установить, является ли S основой правовыводимой цепочки Sa, не видя символа, стоящего после S (т.е. наблюдая "нулевое" количество символов). В соответствии с интуицией G не должна быть LR(0)- грамматикой и она не будет ею, если пользоваться первым определением. Это определение мы и будем использовать далее.

Пример 4.14. Пусть G - леволинейная грамматика с правилами

\begin{align*} & S \rightarrow Ab \mid Bc \\ & A \rightarrow Aa \mid e \\ & B \rightarrow Ba \mid e \end{align*}

Заметим, что G не является LR(k)-грамматикой ни для какого k.

Допустим, что G - LR(k)-грамматика. Рассмотрим два правых вывода в пополненной грамматике G':

\begin{align*} & S' \Rightarrow_r S \Rightarrow^*_r Aa^kb \Rightarrow_r a^kb\\ & \text{и} \\ & S' \Rightarrow_r S \Rightarrow^*_r Ba^kc \Rightarrow_r a^kc\\ \end{align*}

Эти два вывода удовлетворяют условию из определения LR(k)- грамматики при

= e, ? = e, ? = akb, ? = e и y = akc: Но так как заключение неверно, т.е. A
B, то G - не LR(k)-грамматика. Более того, так как LR(k)-условие нарушается для всех k, то G - не LR-грамматика.

Если грамматика не является LR(1), то анализатор типа сдвиг-свертка при анализе некоторой цепочки может достигнуть конфигурации, в которой он, зная содержимое магазина и следующий входной символ, не может решить, делать ли сдвиг или свертку (конфликт сдвиг/свертка), или не может решить, какую из нескольких сверток применить (конфликт свертка/свертка).

В частности, неоднозначная грамматика не может быть LR(1). Для доказательства рассмотрим два различных правых вывода

(1)

S \Rightarrow_r u_1 \Rightarrow_r \ldots \Rightarrow_r u_n \Rightarrow_r w , \text{ и }

(2)

S \Rightarrow_r v_1 \Rightarrow_r \ldots \Rightarrow_r v_m \Rightarrow_r w ,

Нетрудно заметить, что LR(1) - условие (согласно второму определению LR(1)-грамматики) нарушается для наименьшего из чисел i, для которых un-i

vm-i.

Пример 4.15. Рассмотрим ещe раз грамматику условных операторов:

\begin{align*} & S \rightarrow if \; E \; then \; S \mid if \; E \; then \; S \; else \; S \mid a \\ & E \; \rightarrow \; b \end{align*}

Если анализатор типа сдвиг-свертка находится в конфигурации, такой, что необработанная часть входной цепочки имеет вид else ... $, а в магазине находится ...


Содержание  Назад  Вперед