297
правок
Изменения
→Замечание о пополненной грамматике
===Замечание о пополненной грамматике===
Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует <tex>SE</tex> в правых частях правил, то свертка основы в <tex>SE</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>S'E_0</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>S'E_0</tex> нигде, кроме начальной сентенциальной формы, не встречается.
Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Пусть пополненная грамматика имеет следующие правила:
<tex>
(0)\ S' E_0 \to S E \\(1)\ S E \to Sa Ea \\(2)\ S E \to a \\
</tex>
Если игнорировать <tex>0</tex>-е правило, то, не заглядывая в правый контекст основы <tex>SaEa</tex>, можно сказать, что она должна сворачиваться в <tex>SE</tex>. Аналогично основа <tex>a</tex> безусловно должна сворачиваться в <tex>SE</tex>. Создается впечатление, что данная грамматика без <tex>0</tex>-го правила есть LR(0)-грамматика. С учетом же <tex>0</tex>-го правила, после свертки в <tex>SE</tex>, просматривая <tex>k=0</tex> символов, нельзя определить, делать ли свертку в <tex>S'E_0</tex>, следовательно это не LR(0)-грамматика. Получили противоречие.
--------- TODO тут надо либо дать более формальное объяснение, либо объяснить почему k не должно меняться от пополнения грамматики.
----------------
