Лои. Лекция 2025-09-09

Операторная грамматика

эпсилон-свободная грамматика называется операторной грамматикой, если в правых частях ее правил вывода нет нетерминалов, стоящих рядом, то есть ее правила вывода имеют вид

$$A\to {\gamma }_0{\alpha }_1{\gamma }_1{\alpha }_2{\gamma }_2\dots {\alpha }_n{\gamma }_n$$

• $n\ge 0$
• ${\gamma }_i\in \Gamma \cup \{\epsilon \},i=0\dots n$
• $a_i\in \Sigma ,i=0\dots n$

---

Среди терминалов грамматики могут отдельно выделяться символы операций (операторы). Остальные терминальные символы считаются операндами

Link to original

Свойства операторных грамматик

LR(0)-автомат. LR(0)-грамматика. Анализатор на основе LR(0)- автомата

Ключевые определения

r-форма

Пусть $S\Rightarrow {\gamma }_1\Rightarrow \cdots \Rightarrow {\gamma }_m=\omega$ - правосторонний вывод цепочки $\omega$ из аксиомы $S$ грамматики $G=(\_,\_,\_,S)$. Тогда $r$-формой называется каждая цепочка ${\gamma }_i,i=1\dots m$

Link to original

Основа r-формы

Пусть в каком-то правостороннем выводе было использовано правило $A\to \beta$ в контексте $\alpha Au\Rightarrow \alpha \beta u,\alpha ,\beta ,u\in (\Sigma \cup \Gamma {)}^{\ast }$. Основой r-формы $\alpha \beta u$ называется цепочка $\beta$

Link to original

Активный префикс r-формы

Пусть $\alpha \beta u$ - r-форма, $\beta$ - основа r-формы.

Активным префиксом называется любой префикс цепочки $\alpha \beta$

т.е. префикс r-формы, не выходящий за правый конец основы этой r-формы

Link to original

LR(0)-пункт

Набор $(A,{\beta }_1,{\beta }_2)$, где $A\to {\beta }_1{\beta }_2$ - правило грамматики, ${\beta }_1,{\beta }_2\in (\Sigma \cup \Gamma {)}^{\ast }$

Обозначается $[A\to {\beta }_1\bullet {\beta }_2]$

x

Link to original

Все LR(0)-пункты — допустимые. Определение допустимости будет позже.

Очевидно, для любой грамматики количество всех возможных пунктов конечно

Расширенная грамматика

Пусть $G=(\Sigma ,\Gamma ,P,S)$ - контекстно-свободная грамматика. Расширенной грамматикой называется грамматика

$$G^{\prime }=(\Sigma ,\Gamma \cup \{S^{\prime }\},P\cup \{S^{\prime }\to S\},S^{\prime })$$

где $S^{\prime }\notin \Gamma$

Link to original

Автомат LR(0)-пунктов

Автомат LR(0)-пунктов

Автоматом LR(0)-пунктов расширенной грамматики $G=(\Sigma ,\Gamma ,P,S^{\prime })$ называется неполный эпсилон-НКА $(Q,\Sigma \cup \Gamma ,\delta ,q_0,Q)$, где

• $Q$ — множество LR(0)-пунктов грамматики $G$
• $q_0=[S^{\prime }\to \bullet S]$

Функция переходов $\delta$ задается следующим образом:

$$\delta (q,x)=\{\begin{array}{ll}\{[A\to {\beta }_{1}x\bullet {\beta }_2]\}& q=[A\to {\beta }_1\bullet x{\beta }_2],x\in \Sigma \cup \Gamma \\ \{[B\to \bullet \gamma ]\}& q=[A\to {\beta }_1\bullet B{\beta }_2],x=\epsilon ,B\in \Gamma \end{array},{\beta }_1,{\beta }_2,\gamma \in (\Sigma \cup \Gamma {)}^{\ast }$$Link to original

### Пример [[Автомат LR(0)-пунктов|автомата пунктов]]

Нужно замкнуть на себя состояние ${\epsilon }^2$ по $\epsilon$. Но это бессмысленно. Поэтому на картинке этот переход опущен

LR(0)-автомат

LR(0)-автомат

эпсилон-замыкание автомата LR(0)-пунктов

Link to original

Идея построения LR(0)-автомата

1. Каждое состояние LR(0)-автомата — набор пунктов, где

$$A\to \alpha \bullet B\beta \Rightarrow B\to \bullet \gamma$$

2. Один пункт может содержаться в нескольких состояниях.
3. Состояния равны, только если множества пунктов совпадают.

Пример построения LR(0)-автомата