国防科技大学编译原理第10讲语法分析——自下而上分析1

课程主页：

https://www.icourse163.org/course/NUDT-1003101005?tid=1460976445

这次回顾第10讲：语法分析——自下而上分析1。

第10讲语法分析——自下而上分析1

自下而上分析的基本问题

语法分析的方法

自上而下(Top-down)
- 从文法的开始符号出发，反复使用各种产生式，寻找”匹配”的推导
- 推导：根据文法的产生式规则，把串中出现的产生式的左部符号替换成右部
- 从树的根开始，构造语法树
- 递归下降分析法、预测分析程序
自下而上(Bottom-up)
- 从输入串开始，逐步进行归约，直到文法的开始符号
- 归约：根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号
- 从树叶节点开始，构造语法树
- 算符优先分析法、LR分析法

自下而上分析示例

考虑文法$\mathrm{G}(\mathrm{E})$：

$\mathrm{E} \rightarrow \mathrm{i}|\mathrm{E}+\mathrm{E}| \mathrm{E}-\mathrm{E}\left|\mathrm{E}^{\star} \mathrm{E}\right| \mathrm{E} / \mathrm{E} |(\mathrm{E})$

示例，语法分析以及语法树为：

自下而上分析的基本思想

采用“移进－归约”思想进行自下而上分析
基本思想
- 用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

移进-归约分析示例

考虑文法：

$\begin{aligned} \mathrm{S} &\rightarrow \mathrm{aAcBe} \\ \mathrm{A} &\rightarrow \mathrm{b} \\ \mathrm{A} &\rightarrow \mathrm{Ab} \\ \mathrm{B} &\rightarrow \mathrm{d} \end{aligned}$

对abbcde进行“移进－归约”分析。

规约过程以及对应的文法树：

小结：

自下而上分析过程：边输入单词符号，边归约
核心问题：识别可归约串
分析树和语法树不一定一致

短语

定义：令$G$是一个文法，$S$是文法的开始符号，假定$\alpha\beta\delta$是文法$G$的一个句型，如果有

$S\overset{\star}⇒αAδ 且 A\overset{+}⇒β$

则称$\beta$是句型$\alpha\beta\delta$相对于非终结符$A$的短语。

如果有${A} \Rightarrow \beta$，则称$\beta $是句型$\alpha\beta\delta$相对于规则$A\to b$的直接短语。

测试：短语和直接短语

在一个句型对应的语法树中
- 以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语
- 如果子树只有两代，则该短语就是直接短语

考虑文法$\mathrm{G(E)}$

$\begin{array}{l} \mathrm{E} \rightarrow \mathrm{T} \mid \mathrm{E}+\mathrm{T} \\ \mathrm{T} \rightarrow \mathrm{F} \mid \mathrm{T}{\star} \mathrm{F} \\ \mathrm{F} \rightarrow(\mathrm{E}) \mid \mathrm{i} \end{array}$

和句型

$\mathrm{i}_{1}{\star} \mathrm{i}_{2}+\mathrm{i}_{3}$

文法树为：

短语：

$\mathrm{i}_{1} ,\mathrm{i}_{2}, \mathrm{i}_{3} , \mathrm{i}_{1}^{*} \mathrm{i}_{2}, \mathrm{i}_{1}{\star} \mathrm{i}_{2}+\mathrm{i}_{3}$

直接短语：

$\mathrm{i}_{1} ,\mathrm{i}_{2}, \mathrm{i}_{3}$

分析过程描述

考虑文法$\mathrm{G(E)}$

分析过程如下：

算符优先分析方法

基本思想
- 从输入串开始，逐步归约，直到文法的开始符号
- 归约：根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号
- 从树叶节点开始，构造语法树
算符优先分析法
- 按照算符的优先关系和结合性质进行语法分析
- 适合分析表达式
LR分析法
- 规范归约：句柄作为可归约串

算符优先文法

运算的优先级

四则运算的优先规则
先乘除后加减，同级从左到右
考虑文法$G’(E)$：
$E → i | E+E | E-E | E\star E | E/E | (E)$
句子$i+i-i\star (i+i)$ 有几种不同的归约
归约顺序不同，计算的顺序也不同，结果也不一样
如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的

规约过程：

优先关系

任何两个可能相继出现的终结符$a$与$b$可能三种优先关系
- $a<b$: $a$的优先级低于$b$
- $a=b$: $a$的优先级等于$b$
- $a>b$: $a$的优先级高于$b$
算符优先关系与数学上的$<>=$不同
- $+<+$
- $aa$，如$(<+$和$+<($

算符文法

一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含$…QR…$形式的产生式右部，则称该文法为算符文法。
约定：
- $a,b$代表任意终结符
- $P,Q,R$代表任意非终结符
- $”…”$代表由终结符和非终结符组成的任意序列，包括空字
假定$G$是一个不含$ε-$产生式的算符文法。对于任何一对终结符$a,b$，我们说：
- $a=b$，当且仅当文法$G$中含有形如$P→…ab…$或
  $P→…aQb…$的产生式；
- $a<b$，当且仅当$G$中含有形如$P→…aR…$的产生式，而${R} \overset{+}{\Rightarrow} {b} \ldots$或${R} \overset{+}{\Rightarrow}Q {b} \ldots$；
- $a>b$，当且仅当$G$中含有形如$P→…Rb…$的产生式，而${R} \overset{+}{\Rightarrow} \ldots {a}$或${R} \overset{+}{\Rightarrow} \ldots {a}Q$。
如果一个算符文法$G$中的任何终结符对$(a,b)$至多只满足$a=b,ab$这三个关系之一，则称$G$是一个算符优先文法。

示例：算符优先文法

考虑文法$\mathrm{G(E)}$：

$\begin{aligned} \mathrm{E} &\rightarrow \mathrm{E}+\mathrm{T} \mid \mathrm{T} \\ \mathrm{T} &\rightarrow \mathrm{T}{\star} \mathrm{F} \mid \mathrm{F} \\ \mathrm{F} &\rightarrow \mathrm{P} \uparrow \mathrm{F} \mid \mathrm{P} \\ \mathrm{P} &\rightarrow(\mathrm{E}) \mid \mathrm{i} \end{aligned}$

优先关系表为：

推导过程：

由规则$\mathrm{P}→(\mathrm{E})$，所以有$(=)$
由规则$\mathrm {E}→\mathrm {E}＋\mathrm {T}$和$\mathrm {T}\rightarrow \mathrm {T}\star \mathrm {F}$，所以有$+<\star$

构造优先关系表的算法——FIRSTVT和LASTVT集合

构造优先关系表的算法

FIRSTVT和LASTVT的定义：

$\begin{aligned} \text {FIRSTVT}(P)&=\left\{a \mid P \stackrel{+}{\Rightarrow} a \ldots \text { 或 } P \stackrel{+}{\Rightarrow} Q a \ldots, a \in V_{T} \text { 且 } Q \in V_{N}\right\}\\ \text {LASTVT}(P)&=\left\{a \mid P \stackrel{+}{\Rightarrow} \ldots a \text { 或 } P \Rightarrow \ldots a Q, a \in V_{T} \text { 且 } Q \in V_{N}\right\} \end{aligned}$

根据FIRSTVT和LASTVT集合，检查每个产生式的候选式，确定满足关系$<$和$>$的所有终结符对
- 假定有个产生式的一个候选形为$…aP…$，那么，对任何$b∈\text{FIRSTVT}(P)$，有$a<b$
- 假定有个产生式的一个候选形为$…Pb…$，那么，对任何$a∈\text{LASTVT}(P)$，有$a>b$

构造集合$\text{FIRSTVT}(P)$的算法

反复使用下面两条规则构造集合$\text{FIRSTVT}(P)$
- 1.若有产生式$P→a…$或$P→Qa…$，则$a∈\text{FIRSTVT}(P)$
- 2.若$a∈\text{FIRSTVT}(Q)$，且有产生式$P→Q…$，则$a∈\text{FIRSTVT}(P)$
算法的一种实现
- 步骤1：
  - 布尔数组$F[P,a]$，使得$F[P,a]$为真的条件是，当且仅当$a\in\text{FIRSTVT}(P)$。开始时，按上述的规则1对每个数组元素$F[P,a]$赋初值。
  - 栈STACK，把所有初值为真的数组元素$F[P,a]$的符号对$(P,a)$全都放在STACK之中。
- 步骤2：
  - 若栈STACK不空，就将栈顶项弹出，记此项为$(Q,a)$。对于每个形如$P→Q…$的产生式，若$F[P,a]$为假，则变其值为真且将$(P,a)$推进STACK栈。
  - 上述过程一直重复，直至栈STACK为空为止。

伪代码：

算法的工作结果得到一个二维数组$F$，从它可得任何非终结符$P$的$\text{FIRSTVT}$ $\text { FIRSTVT}(P)=\{a \mid F[P, a]=\text{TRUE}\}$

构造集合LASTVT(P)的算法

反复使用下面两条规则构造集合$\text{LASTVT}(P)$
- 1.若有产生式$P→… a$或$P→ … aQ$，则$a∈\text{LASTVT}(P)$
- 2.若$a∈\text{LASTVT}(Q)$，且有产生式$P→… Q$，则$a∈\text{LASTVT}(P)$

构造优先关系表的算法——FIRSTVT和LASTVT集合计算示例

示例：FIRSTVT和LASTVT的计算

考虑文法$\mathrm{G(E)}$：

$\begin{aligned} (1)\ \mathrm{E} &\rightarrow \mathrm{E}+\mathrm{T} \mid \mathrm{T} \\ (2)\ \mathrm{T} &\rightarrow \mathrm{T}{\star} \mathrm{F} \mid \mathrm{F} \\ (3)\ \mathrm{F} &\rightarrow \mathrm{P} \uparrow \mathrm{F} \mid \mathrm{P} \\ (4)\ \mathrm{P} &\rightarrow(\mathrm{E}) \mid \mathrm{i} \end{aligned}$

计算文法$\mathrm G$的$\text{FIRSTVT}$和$\text{LASTVT}$。

$\text{FIRSTVT}$：

$\text{LASTVT}$：

构造优先关系表的算法

通过检查$G$的每个产生式的每个候选式，可找出所有满足$a=b$的终结符对。
根据$\text{FIRSTVT}$和$\text{LASTVT}$集合，检查每个产生式的候选式，确定满足关系$<$和$>$的所有终结符对
- 假定有个产生式的一个候选形为$…aP…$，那么，对任何$b∈\text{FIRSTVT}(P)$，有$a<b$
- 假定有个产生式的一个候选形为$…Pb…$，那么，对任何$a∈\text{LASTVT}(P)$，有$a>b$

算法伪代码：

FOR 每条产生式$P→X_1X_2…X_n$ DO
- FOR $i:=1$ TO $n-1$ DO
- BEGIN
  - IF $X_i$和$X_{i+1}$均为终结符
    - THEN置$X_i=X_{i+1}$
  - IF $i≤n-2$且$X_i$和$X_{i+2}$都为终结符, 但$X_{i+1}$为非终结符
    - THEN置$X_i=X_{i+2}$
  - IF $X_i$为终结符而$X_{i+1}$为非终结符
    - THEN
      - FOR $\text{FIRSTVT}(X_{i+1})$中的每个$a$
        
        DO置$X_i<a$
  - IF $X_i$为非终结符而$X_{i+1}$为终结符
    - THEN
      - FOR $\text{LASTVT}(X_i)$中的每个$a$
        
        DO 置$a>X_{i+1}$
- END

构造优先关系表示例

依然考虑之前的文法$\mathrm{G(E)}$：

$\text{FIRSTVT}$集合为：

$\begin{aligned} \text { FIRSTVT }(\mathrm{E})&=\left\{+,\star, \uparrow,(, \mathrm{i}\}\right. \\ \text { FIRSTVT }(\mathrm{T})&=\left\{\star, \uparrow,(, \mathrm{i}\}\right. \\ \text { FIRSTVT }(\mathrm{F})&=\{\uparrow,(, \mathrm{i}\} \\ \text { FIRSTVT }(\mathrm{P})&=\{(, \mathrm{i}\} \end{aligned}$

$\text{LASTVT}$集合为：

$\begin{aligned} \text { LASTVT }(\mathrm {E})&=\{+, \star , \uparrow,), \text { i}\}\\ \text { LASTVT }(\mathrm T)&=\left\{\star, \uparrow,\right),\text { i}\}\\ \text { LASTVT }(\mathrm F)&=\{\uparrow,), \text { i}\}\\ \text { LASTVT }(\mathrm P)&=\{ ) , \text { i}\} \end{aligned}$

优先关系表如下：

算符优先分析算法

最左素短语

可归约串，句型，短语
一个文法$G$的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语
最左素短语是指处于句型最左边的那个素短语

示例：各类短语的识别

考虑文法$\mathrm{G}(\mathrm E)$：

以及句型：

$\mathrm {T+F\star P+i}$

语法树为：

各类短语为：

短语：$\mathrm{T,F,P,i,F\star P,T+F\star P,T+F\star P+i}$
直接短语：$\mathrm{T,F,P,i}$
素短语：$\mathrm{i,F\star P}$
最左素短：$\mathrm{F\star P}$

最左素短语定理

算符优先文法句型(括在两个$\sharp$之间)的一般形式：
$\sharp {N}_{1} {a}_{1} {N}_{2} {a}_{2} \ldots {N}_{ {n} } {a}_{ {n} } {N}_{ {n}+1} \sharp$
其中，$a_i$都是终结符，$N_i$是可有可无的非终结符。
定理：一个算符优先文法$G$的任何句型的最左素短语是满足如下条件的最左子串$N_ja_j…N_ia_iN_{i+1}$：
$\begin{aligned} &a_{j-1} < a_j\\ &a_j=a_{j+1},\ldots, a_{i-1}=a_i\\ &a_i > a_{i+1} \end{aligned}$
具体来说：
$\sharp N_{1} a_{1} N_{2} a_{2} \ldots a_{j-1}\{ N_{j} a_{j} \ldots N_{i} a_{i} N_{i+1}\} a_{i+1} \ldots N_{n} a_{n} N_{n+1} \sharp$

算符优先分析算法

使用一个符号栈$S$，用它寄存终结符和非终结符，$k$代表符号栈$S$的使用深度（即栈顶位置）
在正确的情况下，算法工作完毕时，符号栈$S$应呈现：$\sharp N \sharp$

伪代码：

第一步执行$S[k]=’\sharp ‘$：然后进入repeat循环，$S[k]$为最靠近栈顶的终结符，蓝色部分的伪代码保证最靠近栈顶的终结符优先级比外面的终结符优先级高：

此时进入紫色部分的循环（最左素短语内部的优先级相同），得到下图红色部分，然后执行红色伪代码（进行规约）：

规约后的结果如下：

最终结果如下：

分析树vs.语法树

算符优先分析结果不一定是语法树

算符优先分析程序构成

总控程序，根据现行栈顶符号和当前输入符号，执行动作
优先关系表，用于指导总控程序进行移进-归约
分析栈STACK，用于存放文法符号

算符优先分析法

特点
- 优点: 简单，快速
- 缺点: 可能错误接受非法句子
使用广泛
- 用于分析各类表达式
- ALGOL 60

小结

算符文法与算符优先文法
优先关系
- 计算$\text{FIRSTVT}$和$\text{LASTVT}$集合
- 构造算符优先关系表
算符优先分析算法
- 最左素短语

第10讲 语法分析——自下而上分析1

自下而上分析的基本问题

语法分析的方法

自下而上分析示例

自下而上分析的基本思想

移进-归约分析示例

短语

测试：短语和直接短语

分析过程描述

算符优先分析方法

算符优先文法

运算的优先级

优先关系

算符文法

示例：算符优先文法

构造优先关系表的算法——FIRSTVT和LASTVT集合

构造优先关系表的算法

构造集合$\text{FIRSTVT}(P)$的算法

构造集合LASTVT(P)的算法

构造优先关系表的算法——FIRSTVT和LASTVT集合计算示例

示例：FIRSTVT和LASTVT的计算

构造优先关系表的算法

构造优先关系表示例

算符优先分析算法

最左素短语

示例：各类短语的识别

最左素短语定理

算符优先分析算法

分析树vs.语法树

算符优先分析程序构成

算符优先分析法

小结

第10讲语法分析——自下而上分析1