Лои. Лекция 2025-10-14

Вернемся к LR(0)-пунктам (обсуждалось в лекции лекции)

Введем понятие допустимого для активного префикса LR(0)-пункта

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

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

Определяется аналогично допустимому для активного префикса LR(1)-пункту

В расширенной грамматике $G=(\Sigma ,\Gamma ,\_,S^{\prime })$ её LR(0)-пункт $[A\to {\beta }_1\bullet {\beta }_2]$ допустим для активного префикса $\gamma ={\gamma }^{\prime }{\beta }_1$ некоторой r-формы ${\gamma }^{\prime }{\beta }_1{\beta }_{2}v$, если существует правосторонний вывод

$$S^{\prime }{\Rightarrow }^{\ast }{\gamma }^{\prime }Av\Rightarrow {\gamma }^{\prime }{\beta }_1{\beta }_{2}v{\Rightarrow }^{\ast }uv$$

• ${\gamma }^{\prime },{\beta }_1,{\beta }_2\in (\Sigma \cup \Gamma {)}^{\ast }$
• $u,v\in \Sigma$

Link to original

Иллюстрация определения допустимого для активного префикса LR(0)-пункта

Здесь r-форма ${\gamma }^{\prime }{\beta }_1{\beta }_{2}v$ обозначена также через $\gamma \alpha$

Теорема. Основная теорема 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-анализа

Доказательство основной теоремы 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

Link to original

Следствия основной теоремы LR-анализа

Следствие 1

Следствие. Язык, распознаваемый автоматом пунктов грамматики, совпадает с языком всех активных префиксов грамматики

Из основной теоремы LR-анализа:

todo дать определение языка

Язык, распознаваемый автоматом пунктов расширенной грамматики $G$ совпадает с языком всех активных префиксов грамматики $G$

Link to original

Следствие 2

Следствие. О равенстве множества пунктов состояний LR(0)-автомата и множества пунктов, допустимых для активного префикса

Из основной теоремы LR-анализа:

Состояние LR(0)-автомата, достижимого из его начального состояния по пути, помеченному цепочкой $\gamma$ совпадает с множеством LR(0)-пунктов, допустимых для активного префикса $\gamma$

Доказатетельство:

Следует из теоремы и того факта, определения LR(0)-автомата как эпсилон-замыкания автомата LR(0)-пунктов

Link to original