上下文无关文法

定义

• 终结符的有穷集合 $T$：有限符号集，相当于字母表。
• 非终结符的有穷集合 $V$：非终结符也被称为变元，每个变元代表一个语言。
• 初始符号$S$：其中一个变元，代表语言开始被定义的地方。
• 产生式的有穷集合 $P$，每个产生式包括：
  • 一个变元
  • 一个产生式符号 $\to$
  • 一个包含零个或多个终结符或变元的串

$$G=(V,T,P,S)$$

归约

将产生式右部替换为左部的符号

推导

从产生式的头到体使用规则，得到一个串。

最左推导和最右推导

每一步推导中只将最左边（最右边）的变元替换成该变元的某个产生式的体，称为最左推导（最右推导）。

Example

设一个简单表达式的文法为 $G=(\left\{E,I\right\},T,P,E)$， 其中 $T=\left\{+,\ast ,(,),a,b,0,1\right\}$，$P$ 为

$$\begin{array}{rl}E& \to I\\ E& \to E+E\\ E& \to E\ast E\\ E& \to (E)\\ I& \to a\\ I& \to b\\ I& \to Ia\\ I& \to Ib\\ I& \to I0\\ I& \to I1\end{array}$$

怎么推导 $a\ast (a+b00)$？

---

最左推导：

$$\begin{array}{rl}& E\underset{lm}{\Rightarrow }E\ast E\underset{lm}{\Rightarrow }I\ast E\underset{lm}{\Rightarrow }a\ast E\underset{lm}{\Rightarrow }a\ast (E)\underset{lm}{\Rightarrow }\\ & \ast (E+E)\underset{lm}{\Rightarrow }a\ast (I+E)\underset{rm}{\Rightarrow }a\ast (a+E)\underset{lm}{\Rightarrow }a\ast (a+I)\underset{lm}{\Rightarrow }\\ & a\ast (a+I0)\underset{lm}{\Rightarrow }a\ast (A+I00)\underset{lm}{\Rightarrow }a\ast (a+b00)\end{array}$$

最右推导：

$$\begin{array}{rl}& E\underset{rm}{\Rightarrow }E\ast E\underset{rm}{\Rightarrow }E\ast (E)\underset{rm}{\Rightarrow }E\ast (E+E)\underset{rm}{\Rightarrow }\\ & E\ast (E+I)\underset{rm}{\Rightarrow }E\ast (E+I0)\underset{rm}{\Rightarrow }E\ast (E+I00)\underset{rm}{\Rightarrow }\\ & E\ast (E+b00)\underset{rm}{\Rightarrow }E\ast (I+b00)\underset{rm}{\Rightarrow }E\ast (a+b00)\underset{rm}{\Rightarrow }I\ast (a+b00)\underset{rm}{\Rightarrow }a\ast (a+b00)\end{array}$$

句型

若 $S\stackrel{\ast }{\Rightarrow }\alpha$，则称 $\alpha$ 为 $G$ 的一个句型，

• 若 $S\stackrel{\ast }{\underset{lm}{\Rightarrow }}\alpha$，称 $\alpha$ 为左句型
• 若 $S\stackrel{\ast }{\underset{rm}{\Rightarrow }}\alpha$，称 $\alpha$ 为右句型
• 若 $\alpha \in T^{\ast }$，称 $\alpha$ 为一个句子

设计

例 1

$L=\{0^n{1}^n|n\ge 1\}$

---

$$S\to 0S1|01$$

例 2（有序两字符数量相等）

$L=\left\{0^n{1}^n|n\ge 0\right\}$

---

$$S\to 0S1|ϵ$$

例 3

$L=\{a^m{b}^m{c}^n{d}^n|m,n\ge 1\}$

---

$$\begin{array}{rl}& A\to aAb|ab\\ & B\to cBd|cd\\ & S\to AB\end{array}$$

例 4

$L=\left\{a^n{b}^m{c}^m{d}^n|m,n\ge 1\right\}$

---

$$\begin{array}{rl}S& \to aCd\\ C& \to aCd|D\\ D& \to bDc|bc\end{array}$$

例 5（有序两字符数量不等）

$L=\left\{a^m{b}^n|m,n\ge 0\wedge m\ne n\right\}$

---

$$\begin{array}{rl}& A\to aA|aAb|ϵ\\ & B\to Bb|aBb|ϵ\\ & S\to aA|Bb\end{array}$$

Attention

不能写成

$$\begin{array}{rl}& A\to aAb|ϵ\\ & S\to aA|Ab\end{array}$$

这样写只会接受 $a$ 比 $b$ 多一个或 $b$ 比 $a$ 多一个的情况。

例 6

$L=\left\{a^m{b}^n|m,n\ge 0\wedge 2m\le n\le 3m\right\}$

---

考虑先实现边界情况，

$$\begin{array}{r}S\to aSbb|aSbbb|ϵ\end{array}$$

发现文法恰好实现了区间关系。

• 扫描法：从左向右进行扫描，找到第一个满足 xx 条件的 xx 字符，将串分为若干容易表示的部分，然后再进行组合。
• 有分治的思想

例 7（无序两字符数量相等）

$L=\left\{w|w\in {\left\{a,b\right\}}^{\ast }\wedge w中a和b的数量相等\right\}$

---

三种情况：

1. 空串
2. 以 $a$ 开头，在剩下的串中找第一个使 $b$ 的数量比 $a$ 多的 $b$，它将剩下的串分为两部分 $a$ 和 $b$ 数量相等的两个串。
3. 类似地，以 $b$ 开头，……

$$S\to aSbs|bSaS|ϵ$$

• ~ 两字符数量相同的文法，经常使用

例 8（无序两字符数量差固定）

$L=\left\{w|w\in {\left\{a,b\right\}}^{\ast }\wedge w中a和b的数量相差2\right\}$

---

• 若 $a$ 比 $b$ 多 2 个：找第一个使 $a$ 的数量比 $b$ 多的 $a$，再类似的找第二个 $a$，可以把串分为 $5$ 个部分。
• 若 $b$ 比 $a$ 多 2 个：……

$$\begin{array}{rl}& S\to A|B\\ & A\to CaCaC\\ & B\to CbCbC\\ & C\to aCbC|bCaC|ϵ\end{array}$$

例 9（无序两字符数量不等）

$L=\left\{w|w\in {\left\{a,b\right\}}^{\ast }\wedge w中a和b的数量不相等\right\}$

---

$$\begin{array}{rlr}& S\to A|B& \\ & A\to CaD& \\ & B\to CbE& \\ & C\to aCbC|bCaC|ϵ& a和b数量相等\\ & D\to aDbD|bDaD|aD|Da|ϵ& a的数量不少于b\\ & E\to aEbE|bEaE|bE|Eb|ϵ& b的数量不少于a\end{array}$$

习题

习题 5.1.1. (b)

$L=\left\{a^i{b}^j{c}^k|i\ne j或j\ne k\right\}$

---

$$\begin{array}{rlr}S& \to A|B& \\ A& \to aC|Db|Ac& a,b不等\\ B& \to bE|Fc|aB& b,c不等\\ C& \to aC|aCb|ϵ& a\ge b\\ D& \to Db|aDb|ϵ& a\le b\\ E& \to bE|bEc|ϵ& b\ge c\\ F& \to Fc|bFc|ϵ& b\le c\end{array}$$

二义性

$\exists w\in T^{\ast }$，可以找到两颗不同的语法分析树，它们的根都是 $S$，产物都是 $w$。

• 有多个不同的推导不代表文法是二义的
• 不存在判断文法是否有歧义的算法

Theorem

$w$ 具有两颗不同的分析树 $\iff$ 存在两个不同的最左/最右推导

Example

文法

$$\begin{array}{rl}E& \to EOE\\ E& \to (E)\\ E& \to v\\ E& \to d\\ O& \to +\\ O& \to \ast \end{array}$$

对于串 $v+v\ast d$，存在两颗不同的语法分析树。

消除二义性

例 1

$L=\left\{a^n{b}^m|0\le n\le m\right\}$

---

考虑优先匹配最外层或最内层的 $a,b$ 对 优先匹配最外层：

$$\begin{array}{rl}S& \to aSb|B\\ B& \to bB|ϵ\end{array}$$

优先匹配最内层：

$$\begin{array}{rl}S& \to AB\\ A& \to aAb|ϵ\\ B& \to bB|ϵ\end{array}$$

例：表达式

有两个问题导致了文法的二义性。 算符优先级：引入多个变元

例 2

$$\begin{array}{rl}E& \to E+E|T\\ T& \to T\ast T|(E)|v|d\end{array}$$

可以使 $v+v\ast d$ 存在唯一的语法分析树。 此时 $v+v+d$ 仍有两个可能的语法分析树。

相同的运算符的结合顺序

例 3

$$\begin{array}{rl}E& \to E+T|T\\ T& \to T\ast F|F\\ F& \to v|d|(E)\end{array}$$

此时文法是一个无二义文法。

例：悬挂 else

$$S\to ϵ|iS|iSeS$$

对于 iie，有两种语法分析树：

例 4

采用最近嵌套匹配，不让 ie 中间出现单 i 分支

$$\begin{array}{rl}S& \to ϵ|iS|iMeS\\ M& \to ϵ|iMeM\end{array}$$