297
правок
Изменения
Нет описания правки
LR(0)-разбор означает, что разборщик для принятия решения не смотрит на символы строки, а смотрит только на состояние стека и определяет переходы по нему.
== LR(0)-Разбор ==
|id=def_LRk_item)
|definition=
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика и <tex>A \to w_1 w_2 \in P</tex>. Композицию <tex>[A \to w_1 \cdot w_2, u] </tex>, где <tex>u \in \Sigma^{*k}</tex>, назовем '''LR(k)-ситуацией''' (англ. ''LR(k)-item'')
}}
LR(0)-ситуации не должны содержать терминальной цепочки, так как <tex>k=0</tex>, то есть мы можем записывать их следующим образом: <tex>[A \to w_1 \cdot w_2]</tex>
<tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\text{B}} {[} A \to \alpha B \cdot \beta] </tex>
Получаем следующий недетерминированный конечный автомат[[Недетерминированные конечные автоматы|НКА]]:
[[Файл:eps-dfa.png|600px]]
Избавимся от <tex>\epsilonvarepsilon</tex>-переходов и получим детерминированный автомат[[Детерминированные конечные автоматы|ДКА]]:
[[Файл:LRk_dfa.png|600px]]
