Доказательство основной теоремы LR-анализа

Теорема. Основная теорема LR-анализа

Пусть:

• $G$ - расширенная грамматика
• $I_G=(\_,\_,\_,q_0,\_)$ - Автомат LR(0)-пунктов, построенный по грамматике $G$

Тогда

LR(0)-пункт $q=[A\to {\beta }_1\bullet {\beta }_2]$ грамматики $G$ допустим для активного префикса $\gamma$ некоторой r-формы $\iff$ в автомате пунктов $I_G$ есть путь из начального состояния $q_0$ в $q$, помеченный цепочкой $\gamma$

Доказательство основной теоремы LR-анализа

Link to original

Для доказательства теоремы требуется ввести понятие базисного LR(0)-пункта

Базисный LR(0)-пункт

LR(0)-пункт $q=[A\to {\beta }_1\bullet {\beta }_2]$ расширенной грамматики $G^{\prime }=(\Sigma ,\Gamma \cup \{S^{\prime }\},P\cup \{S^{\prime }\to S\},S^{\prime })$ называется базисным, если

• либо ${\beta }_1\ne \epsilon$ ($\bullet$ не в начале)
• либо $q=[S^{\prime }\to \bullet S]$

Link to original

И базисного перехода

Базисный переход

В автомате LR(0)-пунктов $A=(Q,\Sigma \cup \Gamma ,\delta ,\_,Q)$ базисными переходами называется переходы из состояния $q_i\in Q$ в состояния из $Q_j\subseteq Q$ согласно функции перехода $\delta$

$$\delta (q_i,x)=Q_j$$

если

• $x\ne \epsilon$

То есть переходы с “пометками”, не равными $\epsilon$

Link to original

Замечание: В базисные пункты ведут базисные переходы, и только они

Для доказательство теоремы, сформулируем лемму 1

Лемма. О существовании базисного пункта, допустимого для активного префикса

Лемма. О существовании базисного пункта, допустимого для активного префикса

Пусть: $\gamma$ - активный префикс какой-то r-формы. Тогда: Найдется базисный пункт, допустимый для активного префикса $\gamma$ Доказательство: Доказательство леммы о существовании базисного пункта, допустимого для активного префикса

Link to original

И Лемма 2

Лемма. Об эквивалентности допустимости пункта для активного префикса и достижимости этого пункта по эпсилон-переходам

Пусть:

• $G$ - расширенная грамматика
• $I_G=(\_,\_,\_,q_0,\_)$ - Автомат LR(0)-пунктов, построенный по грамматике $G$

Тогда:

LR(0)-пункт $q=[B\to \bullet \beta ]$ грамматики $G$ допустим для активного префикса $\gamma$ некоторой r-формы $\iff$ состояние $q$ достижимо по $\epsilon$- переходам в автомате пунктов $I_G$ из некоторого состояния, соответствующего базисному пункту $[A\to {\beta }_1\bullet {\beta }_2]$, допустимого для $\gamma$

Доказательство: Доказательство леммы об эквивалентности допустимости пункта для активного префикса и достижимости этого пункта по эпсилон-переходам

Link to original