第 2 章文法与语言

2.1. 符号串与语言

1. 字母表

定义

字母表 $\Sigma$ 是一个有穷符号集合

符号：字母、数字、标点符号

字母表上的运算

乘积
- $\Sigma_1\Sigma_2=\{ab|a\in\Sigma_1,b\in\Sigma_2\}$
$\displaystyle{ n }$ $n$ 次幂
- $\Sigma^0=\{\varepsilon\}$
- $\Sigma^n=\Sigma^{n-1}\Sigma, n\geqslant 1$
- 即为长度为 $\displaystyle{ n }$ 的符号串构成的集合
正闭包
- $\Sigma^{+}=\Sigma\cup\Sigma^2\cup\Sigma^3\cup\cdots$
闭包
- $\Sigma^{*}=\Sigma^0\cup\Sigma\cup\Sigma^2\cup\Sigma^3\cup\cdots$

2. 串

定义

设 $\Sigma$ $Σ$ 为一个字母表， $\forall x\in\Sigma^{*}$ $\forall x \in Σ^{*}$ ， $\displaystyle{ x }$ $x$ 称为 $\Sigma$ $Σ$ 上的一个串。
- 串是字母表中符号的一个有穷序列
串的长度 $\displaystyle{ \left| s \right| }$ ，指符号的个数
空串 $|\varepsilon|$

连接

$\displaystyle{ x }$ 和 $\displaystyle{ y }$ 是串，则 $\displaystyle{ x }$ 和 $\displaystyle{ y }$ 的连接—— $\displaystyle{ x y }$ ，对于非空不相等串有 $xy\ne yx$

空串是连接运算的单位元， $\varepsilon s=s\varepsilon=s$

幂

\begin{cases} s^0=\varepsilon\\ s^n=s^{n-1}s,n\geqslant 1 \end{cases}

2.2. 文法定义

1. 文法的形式化定义

文法

$\displaystyle{ G = \left( V _{ T } , V _{ N } , P , Z \right) }$

$\displaystyle{ V _{ T } }$ $V_{T}$ 终结符集合，为非空有穷集合
- 终结符是文法所定义的语言的基本符号，有时也称为 token
$\displaystyle{ V _{ N } }$ $V_{N}$ 非终结符集合，为非空有穷集合
- 非终结符有时也称为“语法变量”
  - $V_T\cap V_N=\varnothing$
  - $V_T\cup V_N$ 文法符集合
$\displaystyle{ P }$ $P$ 产生式集合
- 产生式描述了将终结符和非终结符组成串的方法
- 产生式的一般形式 $\alpha\rightarrow\beta$ $α \to β$ 或 $\alpha ::=\beta$ $α ::= β$ ，读作 $\alpha$ $α$ 定义为 $\beta$ $β$
  - $\alpha\in(V_T\cup V_N)^{+}$ 且 $\alpha$ 中至少包含 $\displaystyle{ V _{ N } }$ 中的一个元素，称为产生式的头或左部
  - $\beta\in(V_T\cup V_N)^{*}$ 称为产生式的体或者右部
$\displaystyle{ Z }$ $Z$ 开始符号或识别符号
- 第一条产生式规则的左部是识别符号

不引起歧义的前提下，可以只写产生式

产生式的简写

对一组有相同左部的产生式

$\alpha::=\beta_1,\alpha::=\beta_2,\cdots,\alpha::=\beta_n$

可以简写为

$\alpha::=\beta_1|\beta_2|\cdots|\beta_n$

$\beta_i(i=1,2,\cdots,n)$ 称为 $\alpha$ 的候选式

2. 语言的形式化定义

推导与归约

给定文法 $\displaystyle{ G = \left( V _{ T } , V _{ N } , P , Z \right) }$ ，如果 $\alpha\rightarrow\beta\in P$ ，那么可以将符号串 $\gamma\alpha\delta$ 中 $\alpha$ 替换为 $\beta$ ，即将 $\gamma\alpha\delta$ 重写为 $\gamma\beta\delta$ 记作

$\gamma\alpha\delta\Rightarrow\gamma\beta\delta$

称文法中的符号串 $\gamma\alpha\delta$ 直接推导出 $\gamma\beta\delta$

其中，从 $\gamma\alpha\delta$ 推导出 $\gamma\beta\delta$ 只用了一次推导，称之为直接推导，或者称 $\gamma\beta\delta$ 直接归约到 $\gamma\alpha\delta$

简言之，用产生式右部替换产生式左部

若存在推导序列

$\alpha_0\Rightarrow\alpha_1\Rightarrow\alpha_2\Rightarrow\cdots\Rightarrow\alpha_n$

称串 $\alpha_0$ 经过 $\displaystyle{ n }$ 步推导出 $\alpha_n$ 可简记为 $\alpha_0\overset{n}{\Rightarrow}\alpha_n$ ，这个序列是一个从 $\alpha_0$ 到 $\alpha_n$ 的长度为 $\displaystyle{ n }$ 的推导

$\alpha\overset{0}{\Rightarrow}\alpha$
$\alpha_0\overset{+}{\Rightarrow}\alpha_n$ 表示经过正数步推导
$\alpha_0\overset{*}{\Rightarrow}\alpha_n$ 表示经过若干（可以是 0）步推导

归约是推导的逆过程

句型和句子

如果 $Z\overset{*}{\Rightarrow}\alpha,\alpha\in(V_T\cup V_N)^{*}$ $Z \Rightarrow * α, α \in (V_{T} \cup V_{N})^{*}$ ，则称 $\alpha$ $α$ 是文法 $\displaystyle{ G }$ $G$ 的一个句型
- 一个句型中既可包含终结符，又可包含非终结符，也可能是空串
如果 $Z\overset{*}{\Rightarrow}\alpha,\alpha\in V_T^{*}$ ，则称 $\alpha$ 是 $\displaystyle{ G }$ 的一个句子

Note

句型中可以包含非终结符
句子中不可以包含非终结符

语言

由文法 $\displaystyle{ G }$ 的开始符号 $\displaystyle{ Z }$ 推导出的所有句子构成的集合称为文法 $\displaystyle{ G }$ 生成的语言，记为 $\displaystyle{ L \left( G \right) }$

$L(G)=\{x|Z\overset{+}{\Rightarrow}x,x\in V_T^*\}$

由语言的定义可知，当文法给定时，语言也就确定了。语言 $\displaystyle{ L \left( G \right) }$ 是 $\displaystyle{ V _{ T } ^{ \cdot } }$ 的子集， $\displaystyle{ L \left( G \right) }$ 中的每个符号均由非终结符组成，且该符号串能由 $\displaystyle{ Z }$ 推导出来。

3. 短语直接短语句柄

设 $\displaystyle{ G \left[ Z \right] }$ 是一个文法，假定 $\alpha\beta\delta$ 是 $\displaystyle{ G }$ 的一个句型，如果有

Z\overset{+}{\Rightarrow}\alpha A\delta, A\overset{+}{\Rightarrow}\beta

则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对于非终结符 $\displaystyle{ A }$ 的短语。特别的，如果有 $\displaystyle{ A }$ 直接推导到 $\beta$ ，则称 $\beta$ 是句型 $\alpha\beta\delta$ 相对于产生式规则 $A\rightarrow\beta$ 的直接短语，一个句型的最左直接短语称为该句型的句柄。

Caution

短语、直接短语、句柄一定是相对于某一句型的

例设有文法 $\displaystyle{ G \left[ E \right] }$

\begin{aligned} E&\rightarrow E+T \mid E-T \mid T\\ T&\rightarrow T*F \mid T/F \mid F\\ F&\rightarrow (E) \mid i \end{aligned}

假设句型 $\displaystyle{ F - T \cdot \left( E - T \right) }$ 的推导过程

\begin{aligned} E&\Rightarrow E-T\Rightarrow E-T*F\Rightarrow E-T*(E)\Rightarrow E-T*(E-T)\\ &\Rightarrow T-T*(E-T)\Rightarrow F-T*(E-T) \end{aligned}

语法分析树如下

其中

最左边的 $\displaystyle{ F }$ 为句柄
短语有 $\displaystyle{ \ \left\lbrace F , E - T , \left( E - T \right) , T \cdot \left( E - T \right) , F - T \cdot \left( E - T \right) \ \right\rbrace }$
直接短语有 $\displaystyle{ \ \left\lbrace F , E - T \ \right\rbrace }$

4. 规范推导和规范归约

一般最右推导为规范推导，最左归约为规范归约

最右推导的逆过程为最左归约
最左推导的逆过程为最右归约

最右推导就类似如下递归

def f(root):
    process(root)
    f(root.right)
    f(root.left)

2.3. 语法分析树与文法的二义性

1. 语法分析树

例子见上面

有助于理解一个句子语法结构的层次

$\displaystyle{ G \left[ Z \right] = \left( V _{ N } , V _{ T } , P , Z \right) }$ 是一个上下文无关文法

根节点标记为 $\displaystyle{ Z }$
根节点外的每一个节点也有一个标记，是 $V_N\cup V_T\cup\{\varepsilon\}$ 中的符号
每一个内部节点的标记 $\displaystyle{ A }$ 必在 $\displaystyle{ V _{ N } }$ 中
若某个内部节点标记为 $\displaystyle{ A }$ ，其孩子节点的标记从左到右分别为 $X_1,X_2,\cdots X_n$ ，则 $A\rightarrow X_1 X_2\cdots X_n$ 必为 $\displaystyle{ P }$ 中的一条产生式规则
若结点有标记 $\varepsilon$ ，则该节点为叶子，且是它父亲唯一的孩子

对于文法 $\displaystyle{ G \left[ E \right] }$

\begin{aligned} E&\rightarrow E+T \mid E-T \mid T\\ T&\rightarrow T*F \mid T/F \mid F\\ F&\rightarrow (E) \mid i \end{aligned}

可以发现，先有的规则，运算符优先级更低；而对应到二叉树中，下层运算未结束，上层的运算不能进行。

2. 文法的二义性

如果一个文法存在某个句子对应两棵不同的语法树，则这个文法是二义的。即，若一个文法中存在某个句子，它有两个不同的最左（右）推导，则它是二义的。

例设 $\displaystyle{ G \left[ E \right] }$

E\rightarrow i \mid E+E \mid E*E \mid (E)

关于 $\displaystyle{ i \cdot i + i }$ 有两种不同的最右推导

从该例来看，因为不同优先级的运算符都写在了一个推导语句中，前面提到了规则写在前面的优先级更低一些，此处的二义性就源自混淆了优先级。

3. 二义性的消除

改写原有的文法，构造一个等价的新文法，把排除二义性的规则合并到原文法中
不改变原有文法，附加限制性条件
- 运算符优先级顺序
- 结合规则（左结合、右结合）

4. 文法的化简

若一个非终结符不能推导出终结符号串，则该非终结符是无用的
- 函数递归没有出口
若一个符号不能出现在文法的任何句型中，则该符号是无用的
- 定义了函数 func 但是从来没有被调用

文法化简思路源于语言的生成

从识别符号开始进行推导，若推导出的某句型包括某个不能推导出终结符号的非终结符，则删除包括该非终结符号的所有产生式规则
- 递归没有出口
从终结符号逆向归约，若归约得到的某个非终结符不能归约到文法的符号，则删除包括该非终结符的所有产生式规则
- 归约没有溯源（函数没有定义）
删除不能出现在句型中的所有符号对应的产生式规则
- 函数没有调用