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

课程主页：

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

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

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

语法分析基本概念

回顾编译程序总框：

语法分析的前提

• 对语言的语法结构进行描述
  • 采用正规式和有限自动机描述和识别语言的单词符号
  • 用上下文无关文法来描述语法规则

上下文无关文法

• 上下文无关文法$G$是一个四元组

  $$G=(V_T,V_N,S,P)$$

• 其中

  • $V_T$：终结符(Terminal)集合(非空)
  • $V_N$：非终结符(Noterminal)集合(非空)，且$V_T \cap V_N=\varnothing$
  • $S$：文法的开始符号，$S\in V_N$
  • $P$：产生式集合(有限)，每个产生式形式为
    • $P\to \alpha， P\in V_N， \alpha∈ (V_T \cup V_N)^{\star}$
  • 开始符$S$至少必须在某个产生式的左部出现一次

• 定义：称$αAβ$直接推出$αγβ$，即

  $$αAβ\Rightarrow αγβ$$

  仅当$A → γ$是一个产生式，且

  $$\alpha,\beta∈ (V_T \cup V_N)^{\star}$$

• 如果$α_1 \Rightarrow α_2 \Rightarrow\ldots \Rightarrow α_n$，则我们称这个序列是从$α_1$到$α_n$的一个推导。若存在一个从$α_1$到$α_n$的推导，则称$α_1$可以推导出$α_n$

句子、句型和语言

• 定义：假定$G$是一个文法，$S$是它的开始符号。如果$S\overset{\star}\Rightarrow \alpha$，则称$\alpha$是一个句型。

• 仅含终结符号的句型是一个句子。

• 文法$G$所产生的句子的全体是一个语言，将它记为$L(G)$。

  $$L(G)=\left\{\alpha \mid {S} \Rightarrow \alpha, \alpha \in V_{T}^{\star}\right\}$$

语法分析的任务

• 语法分析的任务
  • 分析一个文法的句子的结构
• 语法分析器的功能
  • 按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)

语法分析器在编译器中的地位

语法分析的方法

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

自上而下分析面临的问题

自上而下分析

• 基本思想
  • 从文法的开始符号出发，向下推导，推出句子
  • 针对输入串，试图用一切可能的办法，从文法开始符号(根结点)出发，自上而下地为输入串建立一棵语法树

自上而下分析示例

• 假定有文法$G(S)$:

  • $S\to xAy$
  • $A\to \star\star | \star$

  分析输入串$x\star y$(记为$\alpha$)

分析过程如下：

自上而下分析面临的问题

• 回溯问题

  • 分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的
  • 出错时，不得不“回溯”（从之前例子中可以看出这点）
    • 时间开销很大

• 文法左递归问题

  • 一个文法是含有左递归的，如果存在非终结符$P$

    $$P\overset {+ }\Rightarrow P\alpha$$

  • 可能会陷入死循环

    

$LL(1)$文法

• 自上而下分析面临的问题
  • 文法左递归问题
  • 回溯问题
• 构造不带回溯的自上而下分析算法
  • 消除文法的左递归性
  • 消除回溯

消除文法的左递归

直接左递归的消除

• 产生式中的直接左递归

  $$P→Pα | β (β不以P开头)$$

  考虑其推导的过程

  $$\begin{aligned} P & \Rightarrow P \alpha \\ & \Rightarrow P \alpha \alpha \\ & \cdots \\ & \Rightarrow P \alpha \ldots \alpha \\ & \Rightarrow \beta \alpha \ldots \alpha \end{aligned}$$

• 可以用如下方法将左递归变右递归

  $$\begin{aligned} P&→βP′\\ P′&→αP′|ε \end{aligned}$$

  考虑其推导的过程

  $$\begin{aligned} P & \Rightarrow \beta P^{\prime} \\ & \Rightarrow \beta \alpha P^{\prime} \\ & \Rightarrow \beta \alpha \alpha P^{\prime} \\ & \cdots\\ &\Rightarrow \beta \alpha \ldots \alpha P^{\prime} \\ &\Rightarrow \beta \alpha \ldots \alpha \end{aligned}$$

• 假定$P$关于的全部产生式是

  $$P→Pα_1 | Pα_2 |\ldots | Pα_m | β_1 | β_2|\ldots|β_n$$

  (每个$α$都不等于$ε$，每个$β$都不以$P$开头)

• 左递归变右递归

  $$\begin{aligned} P &→ β_1 P′ | β_2 P′ | \ldots | β_n P′\\ P′&→ α_1 P′ | α_2 P′ |\ldots | α_m P′ | ε \end{aligned}$$

具体例子：

给定文法$G(E)$：

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

利用之前的方法消除左递归得到：

$$\begin{aligned} {E} &\rightarrow {TE}^{\prime} \\ {E}^{\prime}& \rightarrow+{TE}^{\prime} \mid \varepsilon \\ {T} &\rightarrow {FT}^{\prime} \\ {T}^{\prime} &\rightarrow {\star} {FT}^{\prime} \mid \varepsilon \\ {F} &\rightarrow({E}) \mid {i} \end{aligned}$$

间接左递归的消除

• 给定文法$G(S)$:

  $$\begin{aligned} S&→Qc|c\\ Q&→Rb|b\\ R&→Sa|a\\ \end{aligned}$$

  该文法没有直接左递归，但$S,Q,R$都是左递归的

  $$S\Rightarrow Qc\Rightarrow Rbc\Rightarrow Sabc$$

• 一个文法消除左递归的条件(该条件绝大多数情况都能满足)

  • 不含以$ε$为右部的产生式

  • 不含回路

    $$P\overset{+}\Rightarrow P$$

• 依然以之前文法为例：

  给出如下消除间接左递归的方法：首先给定非终结符的排序$R,Q,S$，将按照此顺序消除左递归，具体方法为每次将当前终结符之前的非终结符的推导代入到当前终结符的推导中，具体步骤如下：

  

  将此步骤归纳即可得到算法。

消除左递归的算法

• 把文法$G$的所有非终结符按任一种顺序排列$P_1,P_2,\ldots,P_n$；按此顺序执行：
• FOR i:=1 TO n DO(把$P_i$的规则改造成$P_i→a\ldots| P_{i+1}\ldots| P_{i+2}\ldots| \ldots| P_{i+k}\ldots$)
  • BEGIN
    • FOR j:=1 TO i-1 DO
      • 把形如$P_i→P_jγ$的规则改写成$P_i→ δ_1γ | δ_2γ |\ldots | δ_kγ$;(其中$P_j→ δ_1 | δ_2 |\ldots | δ_k$是关于$P_j$的所有规则，第$j$轮中，$P_i$的形式为$P_i→a\ldots| P_{j+1}\ldots| P_{j+2}\ldots| \ldots| P_{j+k}\ldots$)
    • 消除关于$P_i$规则的直接左递归性
  • END
• 化简前一步所得的文法，去除从开始符号出发永远无法到达的非终结符的产生规则。

例子

$$\begin{aligned} S&→Qc|c\\ Q&→Rb|b\\ R&→Sa|a\\ \end{aligned}$$

假定顺序为$R,Q,S$，下面进入循环

i=1

什么都不做

i=2

将$R$的推导代入到$Q$的推导中，得到

$$\begin{aligned} S&→Qc|c\\ Q&→Sab|ab|b\\ R&→Sa|a\\ \end{aligned}$$

i=3

将$R,Q$的推导依次代入到$S$的推导中，得到

$$\begin{aligned} S&→Sabc|abc|b|c\\ Q&→Sab|ab|b\\ R&→Sa|a\\ \end{aligned}$$

注意此时$S$的推导中有左递归，利用之前的方法进行转换可得

$$\begin{aligned} S &\to abcS′ | bcS′ | cS′\\ S′&→ abcS′ | ε\\ Q&→Sab|ab|b\\ R&→Sa|a\\ \end{aligned}$$

由于从$S$无法推导到$R,Q$，对齐化简可得

$$\begin{aligned} S &\to abcS′ | bcS′ | cS′\\ S′&→ abcS′ | ε \end{aligned}$$

补充：

• 注意，由于对非终结符排序的不同，最后所得的文法在形式上可能不一样。但不难证明，它们都是等价的。

• 例如，若对文法的非终结符排序选为$S,Q,R$，那么，最后所得的无左递归文法是：

  $$\begin{aligned} S &\rightarrow Q C \mid C \\ Q &\rightarrow R b \mid b \\ R &\rightarrow b c a R^{\prime}\left|c a R^{\prime}\right| a R^{\prime} \\ R^{\prime} & \rightarrow b c a R^{\prime} \mid \varepsilon \end{aligned}$$

• 上述两个文法是等价的。

消除回溯

• 为了消除回溯必须保证
  • 对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。

FIRST集合

• 令$G$是一个不含左递归的文法，对$G$的所有非终结符的每个候选$α$定义它的终结首符集$\text{FIRST}(α)$为：

  $$\mathrm{F I R S T}(\alpha)=\left\{a \mid \alpha \overset{\star}{\Rightarrow} a \ldots, a \in V_{T}\right\}$$

  特别是，若$\alpha \overset{\star}\Rightarrow \varepsilon$，则规定

  $$\varepsilon \in \text{FIRST}(\alpha)$$

• 如果非终结符$A$的所有候选首符集两两不相交，即对$A$的任何两个不同候选$α_i$和$α_j$

  $$\mathrm{FIRST}\left(\alpha_{\mathrm{i} }\right) \cap \mathrm{FIRST}\left(\alpha_{\mathrm{j} }\right)=\varnothing$$
• 当要求$A$匹配输入串时，$A$能根据它所面临的第一个输入符号$a$，准确地指派某一个候选去执行任务。这个候选就是那个终结首符集含$a$的$α$。

提取公共左因子

• 假定关于$A$的规则是 $$A → δβ_1 | δβ_2 | \ldots| δβ_n | γ_1 | γ_2 | \ldots | γ_m$$ (其中，每个$γ$不以$δ$开头)

• 那么，可以把这些规则改写成

  $$\begin{aligned} A &→ δA′ | γ_1 | γ_2 | \ldots | γ_m\\ A′&→ β_1 | β_2 |\ldots| β_n \end{aligned}$$

• 经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交

$\varepsilon$候选

• 考虑文法$G(E)$：

  $$\begin{aligned} {E} &\rightarrow {TE}^{\prime} \\ {E}^{\prime}& \rightarrow+{TE}^{\prime} \mid \varepsilon \\ {T} &\rightarrow {FT}^{\prime} \\ {T}^{\prime} &\rightarrow {\star} {FT}^{\prime} \mid \varepsilon \\ {F} &\rightarrow({E}) \mid {i} \end{aligned}$$

• 分析：$i + i$

FOLLOW集合

• 假定$S$是文法$G$的开始符号，对于$G$的任何非终结符$A$，我们定义$A$的$\text{FOLLOW}$集合 $$\text {FOLLOW}(A)=\left\{a \mid S \overset{\star}\Rightarrow \ldots A a \ldots, a \in V_{T}\right\}$$ 特别是，若 $$S \overset{*}{\Rightarrow} \ldots A$$ 则规定 $$\sharp \in \mathrm{F O L L O W}(A)$$

$LL(1)$文法

• 构造不带回溯的自上而下分析的文法条件

  • 文法不含左递归

  • 对于文法中每一个非终结符$A$的各个产生式的候选首符集两两不相交。即，若

    $$A \rightarrow \alpha_{1}\left|\alpha_{2}\right| \ldots \mid \alpha_{n}$$

    则

    $$\mathrm{FIRST}\left(\alpha_{ {i} }\right) \cap \mathrm{FIRST}\left(\alpha_{ {j} }\right)=\varnothing \quad({i} \neq {j})$$

    这一点可以通过反复提取左公共因子来接近该条件。

  • 对文法中的每个非终结符$A$，若它存在某个候选首符集包含$ε$，则 $$\mathrm{FIRST}\left(\alpha_{i}\right) \cap \mathrm{FOLLOW}(\mathrm{A})=\varnothing, {i}=1,2, \ldots, \mathrm{n}$$

• 如果一个文法$G$满足以上条件，则称该文法$G$为$LL(1)$文法。

  • 第一个$L$: 从左到右扫描输入串
  • 第二个$L$: 最左推导
  • $1$:每一步只需向前查看一个符号

$LL(1)$分析法

• 对于$LL(1)$文法，可以对其输入串进行有效的无回溯的自上而下分析。

• 假设要用非终结符$A$进行匹配，面临的输入符号为$a$，$A$的所有产生式为

  $$A→α_1 | α_2 |\ldots | α_n$$
  • 若$a∈\text{FIRST}(α_i)$，则指派$α_i$执行匹配任务；
  • 若$a$不属于任何一个候选首符集，则：
    • (1)若$ε$属于某个$\text{FIRST}(α_i )$且$a∈\text{FOLLOW}(A)$，则让$A$与$ε$自动匹配。
    • (2)否则，$a$的出现是一种语法错误。

FIRST和FOLLOW集合的构造

构造$\text{FIRST}(α)$

$$\text{FIRST}(\alpha)=\{a|\alpha\overset \star\Rightarrow a,\ldots,a\in V_T\}$$

分两种情况讨论：

• $\alpha = X,X\in V_T\cup V_N$
• $\alpha =X_1X_2\ldots X_n$

对于$\alpha = X,X\in V_T\cup V_N$：

• 对每一$X\in V_T\cup V_N$，连续使用下面的规则，直至每个集合FIRST不再增大为止：
  • 1.若$X\in V_T$，则$\text{FIRST}(X)＝\{X\}$。
  • 2.若$X\in V_N$，且有产生式$X\to a\ldots $，则把$a$加入到$\text{FIRST}(X)$中；若$X\to \varepsilon$也是一条产生式，则把$\varepsilon$也加到$\text{FIRST}(X)$中。
  • 3.
    • 若$X\to Y\ldots $是一个产生式且$Y\in V_N$，则把$\text{FIRST}(Y)$中的所有非$\varepsilon-$元素都加到$\text{FIRST}(X)$中；
    • 若$X\to Y_1Y_2\ldots Y_{i-1}Y_i\ldots Y_k$是一个产生式，$Y_1,\ldots ,Y_{i-1}$都是非终结符，
      • 对于任何$j$，$1\le j\le i-1$，$\text{FIRST}(Y_j)$都含有$\varepsilon$(即$Y_1\ldots Y_{i-1}\overset{\star}\Rightarrow \varepsilon$)，则把$\text{FIRST}(Y_i)$中的所有非$ε-$元素都加到$\text{FIRST}(X)$中。
      • 若所有的$\text{FIRST}(Y_j)$均含有$ε,j＝1,2,\ldots ,k$，则把$ε$加到$\text{FIRST}(X)$中。

对于$\alpha =X_1X_2\ldots X_n$：

• 对文法$G$的任何符号串$α=X_1X_2\ldots X_n$构造集合$\text{FIRST}(α)$
  • 1.置$\text{FIRST}(\alpha)＝\text{FIRST}(X_1)\verb|| \{\varepsilon\}$；
  • 2.若对任何$1≤j≤i-1,\varepsilon \in \text{FIRST}(X_j)$，则把$\text{FIRST}(X_i)\verb||\{\varepsilon\}$加至$\text{FIRST}(α)$中；特别是，若所有的$\text{FIRST}(X_j)$均含有$ε$，$1≤j≤n$，则把$ε$也加至$\text{FIRST}(α)$中。显然，若$α＝ε$则$\text{FIRST}(α)＝\{ε\}$。

构造$\text{FOLLOW}(A)$

$$\text{FOLLOW}(A)=\{a|S\overset \star\Rightarrow \ldots Aa\ldots ,a\in V_T \}$$

构造每个非终结符的FOLLOW集合

• 对于文法$G$的每个非终结符$A$构造$\text{FOLLOW}(A)$的办法是，连续使用下面的规则，直至每个$\text{FOLLOW}$不再增大为止：
  • 1.对于文法的开始符号$S$，置$\sharp$于$\text{FOLLOW}(S)$中；
  • 2.若$A→αBβ$是一个产生式，则把$\text{FIRST}(β)\verb||\{ε\}$加至$\text{FOLLOW}(B)$中；
  • 3.若$A→\alpha B$是一个产生式，或$A→αBβ$是一个产生式而$β\overset{\star }⇒ε$(即$ε∈\text{FIRST}(β)$)，则把$\text{FOLLOW}(A)$加至$\text{FOLLOW}(B)$中

下面解释规则2，3。

规则2：

若$A\to \alpha B \beta$是一个产生式，因为$\forall a∈ \text{FIRST}(\beta) \verb|| \{\varepsilon\}$，有$\beta \overset{\star}\Rightarrow a\ldots $，则有$S\overset{\star} ⇒\ldots A\ldots \Rightarrow \ldots \alpha B\beta \ldots \overset{\star}\Rightarrow \ldots \alpha Ba\ldots$，则$a\in \text{FOLLOW(B)}$

规则3：

若$A→\alpha B$是一个产生式，因为$\forall a\in \text{FOLLOW}(A)$，有$S\overset{\star}⇒\ldots Aa \ldots$，所以$S\overset{\star} \Rightarrow \ldots Aa \ldots \Rightarrow \ldots \alpha Ba\ldots$，从而$a ∈ \text{FOLLOW}(B)$。

若$A→\alpha B \beta$是一个产生式而$β\overset{\star }⇒ε$，因为因为$\forall a\in \text{FOLLOW}(A)$，有$S\overset{\star}⇒\ldots Aa \ldots$，所以$S\overset{\star} \Rightarrow \ldots Aa \ldots \Rightarrow \ldots \alpha B\beta a\ldots \overset{\star} \Rightarrow \ldots \alpha Ba\ldots$，从而$a ∈ \text{FOLLOW}(B)$。

例子

依然是之前的文法：

$$\begin{aligned} {E} &\rightarrow {TE}^{\prime} \\ {E}^{\prime}& \rightarrow+{TE}^{\prime} \mid \varepsilon \\ {T} &\rightarrow {FT}^{\prime} \\ {T}^{\prime} &\rightarrow {\star} {FT}^{\prime} \mid \varepsilon \\ {F} &\rightarrow({E}) \mid {i} \end{aligned}$$

FIRST构造：

首先可以直接得到

$$\begin{aligned} \mathrm{FIRST}({E})&=\{(, {i}\}\\ \mathrm{FIRST}\left({E}^{\prime}\right)&=\{+, \varepsilon\}\\ \mathrm{FIRST}({T})&=\{(,{i} \}\\ \mathrm{FIRST}\left({T}^{\prime}\right)&=\left\{ {\star}, \varepsilon\right\}\\ \mathrm{FIRST}({F})&=\{(,{i}\} \end{aligned}$$

根据情形1得到：

$$\begin{aligned} \mathrm{FIRST}\left({E}^{\prime}\right)&=\{+, \varepsilon\}\\ \mathrm{FIRST}\left({T}^{\prime}\right)&=\left\{ {\star}, \varepsilon\right\}\\ \mathrm{FIRST}({F})&=\{(,{i}\} \end{aligned}$$

根据情形2得到：

$$\begin{aligned} \mathrm{FIRST}({E})=\{(, {i}\}\\ \mathrm{FIRST}({T})=\{(,{i} \} \end{aligned}$$

FOLLOW构造：

初始化：

$$\mathrm {FOLLOW}(E) =\{ \sharp \}$$

对于推导

$${E} \rightarrow {TE}^{\prime}$$

匹配规则2：

$$\begin{aligned} A& =E\\ \alpha&= 空 \\ B&= T\\ \beta &= E' \end{aligned}$$

把$\text{FIRST}(β)\verb||\{ε\}$加至$\text{FOLLOW}(B)$中，所以

$$\begin{aligned} \mathrm { FOLLOW }(E)&=\{\sharp\}\\ \mathrm { FOLLOW } \left(E^{\prime}\right)&=\{ \}\\ \mathrm { FOLLOW }({T})&=\{+\}\\ \mathrm { FOLLOW }\left(T^{\prime}\right)&=\{ \}\\ \mathrm{FOLLOW}({F})&=\left\{\right\} \end{aligned}$$

匹配规则3：

$$\begin{aligned} A&=E \\ \alpha & = T\\ B&= E' \end{aligned}$$

把$\text{FOLLOW}(A)$加至$\text{FOLLOW}(B)$中，此时

$$\begin{aligned} \mathrm { FOLLOW }(E)&=\{\sharp\}\\ \mathrm { FOLLOW } \left(E^{\prime}\right)&=\{\sharp \}\\ \mathrm { FOLLOW }({T})&=\{+\}\\ \mathrm { FOLLOW }\left(T^{\prime}\right)&=\{ \}\\ \mathrm{FOLLOW}({F})&=\left\{\right\} \end{aligned}$$

继续匹配规则3：

$$\begin{aligned} A&=E \\ \alpha & =空 \\ B & = T\\ \beta&= E' \end{aligned}$$

把$\text{FOLLOW}(A)$加至$\text{FOLLOW}(B)$中，此时

$$\begin{aligned} \mathrm { FOLLOW }(E)&=\{\sharp\}\\ \mathrm { FOLLOW } \left(E^{\prime}\right)&=\{\sharp \}\\ \mathrm { FOLLOW }({T})&=\{+,\sharp\}\\ \mathrm { FOLLOW }\left(T^{\prime}\right)&=\{ \}\\ \mathrm{FOLLOW}({F})&=\left\{\right\} \end{aligned}$$

对每条推导依次使用上述步骤，最终得到

$$\begin{aligned} \mathrm { FOLLOW }(E)&=\{\sharp,)\}\\ \mathrm { FOLLOW } \left(E^{\prime}\right)&=\{\sharp ,)\}\\ \mathrm { FOLLOW }({T})&=\{+,\sharp,)\}\\ \mathrm { FOLLOW }\left(T^{\prime}\right)&=\{ +,\sharp,)\}\\ \mathrm{FOLLOW}({F})&=\left\{\star, +,\sharp,)\right\} \end{aligned}$$