鸭梨公共文档

主题

第四章：语法分析 1 ​

4.1 自顶向下分析概述 ​

4.1.1 自顶向下的分析（Top-Down Parsing） ​

  • 从分析树的顶部向底部方向构造分析树
  • 可以看成是文法的开始符合 SS 推出词串 ww 的过程

例如文法：

G:  E→E+EE→E∗EE→(E)E→id\begin{aligned} G:\; & E \rightarrow E + E \\ & E \rightarrow E * E \\ & E \rightarrow (E) \\ & E \rightarrow \text{id} \end{aligned}

输入 id+(id+id)\text{id} + (\text{id} + \text{id})

分析树：

推导过程：

E⇒E+E⇒E+(E)⇒E+(E+E)⇒E+(id+E)⇒id+(id+E)⇒id+(id+id)\begin{aligned} E & \Rightarrow E + E \\ & \Rightarrow E + (E) \\ & \Rightarrow E + (E + E) \\ & \Rightarrow E + (\text{id} + E) \\ & \Rightarrow \text{id} + (\text{id} + E) \\ & \Rightarrow \text{id} + (\text{id} + \text{id}) \end{aligned}

每一步推导中，都需要做两个选择：

  • 替换当前句型中的哪个非终结符
  • 用该非终结符的哪个候选式进行替换

4.1.2 最左推导（Left-most Derivation） ​

在最左推导中，总是选择每个句型的最左非终结符进行替换。

如上面的例子，推导过程：

E⇒lmE+E⇒lmid+E⇒lmid+(E)⇒lmid+(E+E)⇒lmid+(id+E)⇒lmid+(id+id)\begin{aligned} E & \Rightarrow_{lm} E + E \\ & \Rightarrow_{lm} \text{id} + E \\ & \Rightarrow_{lm} \text{id} + (E) \\ & \Rightarrow_{lm} \text{id} + (E + E) \\ & \Rightarrow_{lm} \text{id} + (\text{id} + E) \\ & \Rightarrow_{lm} \text{id} + (\text{id} + \text{id}) \end{aligned}

与最左推导相对的过程是最右归约，最右归约是最左推导的逆过程。

如果 S⇒lm∗αS\Rightarrow_{lm}^*\alpha，则称 α\alpha 是当前文法的 最左句型（Left-Sentential Form）。

4.1.3 最右推导（Right-Most Derivation） ​

在最右推导中，总是选择每个句型的最右非终结符进行替换。

E⇒E+E⇒rmE+(E)⇒rmE+(E+E)⇒rmE+(E+id)⇒rmE+(id+id)⇒rmid+(id+id)\begin{aligned} E & \Rightarrow E + E \\ & \Rightarrow_{rm} E + (E) \\ & \Rightarrow_{rm} E + (E + E) \\ & \Rightarrow_{rm} E + (E + \text{id}) \\ & \Rightarrow_{rm} E + (\text{id} + \text{id}) \\ & \Rightarrow_{rm} \text{id} + (\text{id} + \text{id}) \end{aligned}

同样地，最左归约是最右推导的逆过程。

注意：在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导。

最左推导和最右推导的唯一性：最左推导和最右推导总是唯一的。

自顶向下的语法分析采用最左推导方式：

  • 总是选择每个句型的最左非终结符进行替换
  • 根据输入流中的下一个终结符，选择最左非终结符的一个候选式

G:  (1)  E→TE′(2)  E′→+TE′∣ε(3)  T→FT′(4)  T′→∗FT′∣ε(5)  F→(E)∣id\begin{aligned} G:\; &(1)\; E \rightarrow TE' \\ &(2)\; E' \rightarrow +TE' \mid \varepsilon \\ &(3)\; T \rightarrow FT' \\ &(4)\; T' \rightarrow *FT' \mid \varepsilon \\ &(5)\; F \rightarrow (E) \mid \text{id} \end{aligned}

输入 id+id∗id\text{id} + \text{id} * \text{id}

递归下降分析

  1. 文法开始，使用 (1) 得到 TE′TE'
  2. 使用 (3) 替换 TT，得到 FT′E′FT'E'
  3. 使用 (5) 替换 FF，得到 idT′E′\text{id}T'E'
  4. 使用 (4) 替换 T′T'，得到 idεE′\text{id}\varepsilon E'
  5. 使用 (2) 替换 E′E'，得到 idε+TE′\text{id}\varepsilon+TE'
  6. 使用 (3) 替换 TT，得到 idε+FT′E′\text{id}\varepsilon+FT'E'
  7. 使用 (5) 替换 FF，得到 idε+idT′E′\text{id}\varepsilon+\text{id}T'E'
  8. 使用 (4) 替换 T′T'，得到 idε+id∗FT′E′\text{id}\varepsilon+\text{id}*FT'E'
  9. 使用 (5) 替换 FF，得到 idε+id∗idT′E′\text{id}\varepsilon+\text{id}*\text{id}T'E'
  10. 使用 (4) 替换 T′T'，得到 idε+id∗idεE′\text{id}\varepsilon+\text{id}*\text{id}\varepsilon E'
  11. 使用 (2) 替换 E′E'，得到 idε+id∗idεε\text{id}\varepsilon+\text{id}*\text{id}\varepsilon\varepsilon

即得到 id+id∗id\text{id} + \text{id} * \text{id}。

4.1.4 递归下降分析（Recursive-Descent Parsing） ​

  • 由一组过程组成，每个过程对应一个非终结符
  • 从文法开始符号 SS 对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果 SS 对应的过程体恰好扫描了整个输入串，则成功完成语法分析

注意

此算法可能需要回溯（Backtracking），导致效率较低。需要回溯的算法是不确定的。

算法如下：

【算法】

void  A()  {选择一个A产生式，A→X1X2⋯Xn;for  (i=1  to  k)  {if  (Xi是非终结符)  调用过程Xi();else  if  (Xi==输入符号a)  读入下一个符号;else  产生一个错误;}}\begin{array}{ll} \mathrm{void}\;A()\;\{ \\ \qquad \qquad \text{选择一个} A \text{产生式，}A\rightarrow X_1X_2\cdots X_n;\\ \qquad \qquad\mathrm{for}\;(i=1\;\mathrm{to}\;k)\;\{\\ \qquad \qquad \qquad \qquad\mathrm{if}\;(X_i \text{是非终结符})\;\text{调用过程} X_i();\\ \qquad \qquad \qquad \qquad\mathrm{else\;if}\;(X_i == \text{输入符号} a)\;\text{读入下一个符号};\\ \qquad \qquad \qquad \qquad\mathrm{else}\; \text{产生一个错误};\\ \qquad \qquad\}\\ \} \end{array}

4.1.5 预测分析（Predictive Parsing） ​

预测分析是递归下降分析技术的一个特例，通过在输入中向前看固定个数（通常是一个）符号来选择正确的 AA 产生式。

可以对某些文法构造出向前看 kk 个输入符号的预测分析器，该类文法有时也称为 LL(k)LL(k) 文法类。

预测分析不需要回溯，是一种确定的自顶向下分析方法。

4.2 文法转换 ​

4.2.1 递归的产生 ​

给定文法

G:  S→aAd∣aBeA→cB→b\begin{aligned} G:\; & S \rightarrow aAd \mid aBe \\ & A \rightarrow c \\ & B \rightarrow b \end{aligned}

输入 abcabc，选择候选式时不确定是哪一个，将产生回溯。

同一个非终结符的多个侯选式存在共同前缀，将导致回溯现象。

另外一个例子：

G:  (1)  E→E+T∣E−T∣T(2)  T→T∗F∣T/F∣F(3)  F→(E)∣id\begin{aligned} G:\; & (1)\; E \rightarrow E+T \mid E-T \mid T \\ & (2)\; T \rightarrow T*F \mid T/F \mid F \\ & (3)\; F \rightarrow (E) \mid \text{id} \end{aligned}

输入 id+id∗id\text{id}+\text{id}*\text{id}，由于侯选式没有与 id\text{id} 对于的侯选式，首先尝试 E+TE+T，然后继续尝试第一个式子，产生单程递归。

E⇒E+T⇒E+E+T⇒E+E+T⇒⋯\begin{aligned} E & \Rightarrow E+T \\ & \Rightarrow E+E+T \\ & \Rightarrow E+E+T \\ & \Rightarrow \cdots \end{aligned}

含义 A→AαA\rightarrow A\alpha 的产生式的文法称为是 直接左递归（Immediate Left Recursive）的。

如果一个文法中有一个非终结符 AA 使得对某个串 α\alpha 存在一个推导 A⇒+AαA \Rightarrow^+ A\alpha 那么这个文法就是 左递归 的。

经过两步或两步以上推导产生的左递归称为是 间接左递归 的。

左递归文法会使递归下降分析器陷入无限循环。

4.2.2 消除直接左递归 ​

A⇒Aα∣βA \Rightarrow A\alpha \mid \beta

A⇒A⇒Aα⇒Aαα⇒Aααα⋯⇒βα⋯α\begin{aligned} A & \Rightarrow A \\ & \Rightarrow A\alpha \\ & \Rightarrow A\alpha\alpha \\ & \Rightarrow A\alpha\alpha\alpha\cdots \\ & \Rightarrow \beta\alpha\cdots\alpha \end{aligned}

那么上面的产生式可以替换为正则表达式 βα∗\beta\alpha^*。

那么

A⇒Aα∣β⇔{A→βA′A′→αA′∣εA \Rightarrow A\alpha \mid \beta \Leftrightarrow \left\{ \begin{aligned} A &\rightarrow \beta A' \\ A' &\rightarrow \alpha A' \mid \varepsilon \end{aligned} \right.

事实上，这种消除过程就是把左递归转换成了右递归。

例如 E→E+T∣TE \rightarrow E + T \mid T

G:  E→E+T⏞α∣T⏞βT→T∗F⏟α∣F⏟βF→(E)∣id\begin{aligned} G:\; & E \rightarrow E\overbrace{+T}^{\alpha} \mid \overbrace{T}^{\beta} \\ & T \rightarrow T\underbrace{*F}_{\alpha} \mid \underbrace{F}_{\beta} \\ & F \rightarrow (E) \mid \text{id} \end{aligned}

第一个式子中，消除左递归后

G:  E→TE′E′→+TE′∣εT→FT′T′→∗FT′∣εF→(E)∣id\begin{aligned} G:\; & E \rightarrow TE' \\ & E' \rightarrow +TE' \mid \varepsilon \\ & T \rightarrow FT' \\ & T' \rightarrow *FT' \mid \varepsilon \\ & F \rightarrow (E) \mid \text{id} \end{aligned}

4.2.3 消除直接左递归的一般形式 ​

A→Aα1∣Aα2∣⋯∣Aαn∣β1∣β2∣⋯∣βm  (αi≠ε,  βj不以A开头)A \rightarrow A \alpha_1 \mid A \alpha_2 \mid \cdots \mid A \alpha_n \mid \beta_1 \mid \beta_2 \mid \cdots \mid \beta_m \;(\alpha_i \neq \varepsilon,\;\beta_j \text{不以} A \text{开头})

可以得出

A→β1A′∣β2A′∣⋯∣βmA′A′→α1A′∣α2A′∣⋯∣αnA′∣ε\begin{aligned} A \rightarrow \beta_1 A' \mid \beta_2 A' \mid \cdots \mid \beta_m A'\\ A' \rightarrow \alpha_1 A' \mid \alpha_2 A' \mid \cdots \mid \alpha_n A' \mid \varepsilon \end{aligned}

消除左递归是要付出代价的 —— 引进了一些非终结符和 ε\varepsilon 产生式。

4.2.4 消除间接左递归 ​

G:  S→Aa∣bA→Ac∣Sd∣ε\begin{aligned} G:\; & S \rightarrow Aa \mid b \\ & A \rightarrow Ac \mid Sd \mid \varepsilon \end{aligned}

推导

S⇒Aa⇒Sda\begin{aligned} S & \Rightarrow Aa \\ & \Rightarrow Sda \\ \end{aligned}

可以使用代入的方法消除 A→Ac∣Aad∣bd∣εA \rightarrow Ac \mid Aad \mid bd \mid \varepsilon，然后消除直接左递归。

4.2.5 消除左递归算法 ​

输入不含循环推导（如 A⇒+AA \Rightarrow^+ A ）和 ε\varepsilon 产生式的文法 GG，输出等价的无左递归文法。

【算法】

按照某个顺序将非终结符号排序为A1, A2, ⋯ , Anfor  (i=1  to  n)  {for  (j=1  to  i−1)  {将每个形如Ai→Ajγ的产生式;替换为产生式组Ai→δ1γ∣δ2γ∣⋯∣δkγ  ;//  其中Aj→δ1∣δ2∣⋯∣δk是所有的Aj产生式}消除Ai产生式之间的直接左递归;}\begin{array}{lc} \text{按照某个顺序将非终结符号排序为} A_1,\, A_2,\, \cdots,\, A_n \\ \mathrm{for}\;(i = 1\;\mathrm{to}\; n)\;\{ \\ \qquad \qquad \mathrm{for}\;(j=1 \;\mathrm{to}\;i-1)\;\{ \\ \qquad \qquad \qquad \qquad \text{将每个形如} A_i \rightarrow A_j \gamma \text{的产生式}; \\ \qquad \qquad \qquad \qquad \text{替换为产生式组} A_i \rightarrow \delta_1\gamma \mid \delta_2\gamma \mid \cdots \mid \delta_k\gamma \;; \\ \qquad \qquad \qquad \qquad // \;\text{其中} A_j \rightarrow \delta_1 \mid \delta_2 \mid \cdots \mid \delta_k \text{是所有的} A_j \text{产生式} \\ \qquad \qquad \} \\ \qquad \qquad \text{消除} A_i \text{产生式之间的直接左递归}; \\ \} \end{array}

4.2.6 提取左公因子（Left Factoring） ​

通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信息后再做出正确的选择。

【输入】文法 GG，输出等价的提取了左公因子的文法

【算法】

对于每个非终结符 AA，找出它的两个或多个选项之间的最长公共前缀 α\alpha。如果 α≠ε\alpha \neq \varepsilon，即存在一个 非平凡的（Nontrivial）公共前缀，那么将所有 A−A- 产生式

A→αβ1∣αβ2∣⋯∣αβn∣γ1∣γ2∣⋯∣γmA \rightarrow \alpha\beta_1 \mid \alpha\beta_2 \mid \cdots \mid \alpha\beta_n \mid \gamma_1 \mid \gamma_2 \mid \cdots \mid \gamma_m

替换为

A→αA′∣γ1∣γ2∣⋯∣γmA \rightarrow \alpha A' \mid \gamma_1 \mid \gamma_2 \mid \cdots \mid \gamma_m

A′→β1∣β2∣⋯∣βmA' \rightarrow \beta_1 \mid \beta_2 \mid \cdots \mid \beta_m

其中，γi\gamma_i 表示所有不以 α\alpha 开头的产生式体。

A′A' 是一个新的非终结符。不断应用这个转换，直到每个非终结符的任意两个产生式体都没有公共前缀为止。

4.3 LL(1)LL(1) 文法 ​

4.3.1 预测分析法的工作过程 ​

从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符 AA 和当前输入符号 aa，选择正确的 A−A- 产生式。为保证分析的确定性，选出的候选式必须是唯一的。

4.3.2 S_文法 ​

S_文法（简单的确定性文法，Korenjak & Hopcroft，1966）：

  • 每个产生式的右部都以终结符开始
  • 同一非终结符的各个候选式的首终结符都不同

根据定义，S_文法不含 ε\varepsilon 产生式。

例如文法：

G:  1.  S→aBC2.  B→bC3.  B→dB4.  B→ε5.  C→c6.  C→a7.  D→e\begin{aligned} G:\; & 1.\; S \rightarrow aBC \\ & 2.\; B \rightarrow bC \\ & 3.\; B \rightarrow dB \\ & 4.\; B \rightarrow \varepsilon \\ & 5.\; C \rightarrow c \\ & 6.\; C \rightarrow a \\ & 7.\; D \rightarrow e \end{aligned}

输入 ada\text{ada}，推导

aBC⇒adBC⇒adC⇒adaaBC \Rightarrow adBC \Rightarrow adC \Rightarrow ada

如果输入 ade\text{ade}，推导

aBC⇒adBC⇒adC⇒?aBC \Rightarrow adBC \Rightarrow adC \Rightarrow ?

这个例子无法推导出，那么什么时候使用 ε\varepsilon 产生式？

如果当前某非终结符 AA 与当前输入符 aa 不匹配时，若存在 A→εA \rightarrow \varepsilon，可以通过检查 aa 是否可以出现在 AA 的后面，来决定是否使用产生式 A→εA \rightarrow \varepsilon（若文法中无 A→εA \rightarrow \varepsilon，则应报错）。

4.3.3 非终结符的后继符号集 ​

非终结符 AA 的后继符号集是可能在某个句型中紧跟在 AA 后边的终结符 aa 的集合，记为 FOLLOW(A)FOLLOW(A) ：

FOLLOW(A)={a∣S⇒∗αAaβ, a∈VT, α, β∈(VT∪VN)∗}FOLLOW(A) = \{a \mid S \Rightarrow^* \alpha A a \beta,\, a \in V_T,\, \alpha,\, \beta \in (V_T \cup V_N)^* \}

如果 AA 是某个句型的的最右符号，则将结束符 '$' 添加到 FOLLOW(A)FOLLOW(A) 中。

例如：

G:  1.  S→aBC2.  B→bC3.  B→dB4.  B→ε5.  C→c6.  C→a\begin{aligned} G:\; & 1.\; S \rightarrow aBC \\ & 2.\; B \rightarrow bC \\ & 3.\; B \rightarrow dB \\ & 4.\; B \rightarrow \varepsilon \\ & 5.\; C \rightarrow c \\ & 6.\; C \rightarrow a \end{aligned}

那么 FOLLOW(B)={a, c}FOLLOW(B) = \{a,\,c\}。

4.3.4 产生式的可选集 ​

产生式 A→βA \rightarrow \beta 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为 SELECT(A→β)SELECT(A \rightarrow \beta)

SELECT(A→aβ)={a} SELECT(A \rightarrow a\beta) = \{a\}

SELECT(A→ε)=FOLLOW(A) SELECT(A \rightarrow \varepsilon) = FOLLOW(A)

4.3.5 q_文法 ​

  • 每个产生式的右部或为 ε\varepsilon，或以终结符开始
  • 具有相同左部的产生式有 不相交的可选集

那么，q_文法不含右部以非终结符打头的产生式。

4.3.6 串首终结符集 ​

串首终结符：串首第一个符号，并且是终结符，简称 首终结符。

给定一个文法符号串 α\alpha，α\alpha 的串首终结符集 FIRST(α)FIRST(\alpha) 被定义为可以从 α\alpha 推导出的所有串首终结符构成的集合。

如果 α⇒∗ε\alpha \Rightarrow^* \varepsilon，那么 ε\varepsilon 也在 FIRST(α)FIRST(\alpha) 中：

  • 对于 ∀α∈(VT∪VN)+, FIRST(α)={a∣α⇒∗aβ, a∈VT, β∈(VT∪VN)∗}\forall \alpha \in (V_T \cup V_N)^+,\, FIRST(\alpha) = \{a \mid \alpha \Rightarrow^* a\beta,\, a \in V_T,\, \beta \in (V_T \cup V_N)^*\}
  • 对于 α⇒∗ε\alpha \Rightarrow^* \varepsilon，那么 ε∈FIRST(α)\varepsilon \in FIRST(\alpha)

产生式 A→αA \rightarrow \alpha 的可选集 SELECTSELECT ：

  • 如果 ε∉FRIST(α)\varepsilon \notin FRIST(\alpha)，那么 SELECT(A→α)=FRIST(α)SELECT(A \rightarrow \alpha) = FRIST(\alpha)
  • 如果 ε∈FISRT(α)\varepsilon \in FISRT(\alpha)，那么 SELECT(A→α)=(FRIST(α)−{ε})∪FOLLOW(A)SELECT(A \rightarrow \alpha) = (FRIST(\alpha) - \{\varepsilon\}) \cup FOLLOW(A)

4.3.7 LL(1)LL(1) 文法 ​

文法 GG 是 LL(1)LL(1) 的，当且仅当 GG 的任意两个具有相同左部的产生式 A→α∣βA \rightarrow \alpha \mid \beta 满足下面的条件：

  1. 如果 α\alpha 和 β\beta 均不能推导出 ε\varepsilon，则 FIRST(α)∩FIRST(β)=∅FIRST(\alpha) \cap FIRST(\beta) = \emptyset
  2. α\alpha 和 β\beta 至多有一个能推导出 ε\varepsilon
    • 如果 β⇒∗ε\beta \Rightarrow^* \varepsilon，则 FIRST(α)∩FOLLOW(A)=∅FIRST(\alpha) \cap FOLLOW(A) = \emptyset
    • 如果 α⇒∗ε\alpha \Rightarrow^* \varepsilon，则 FIRST(β)∩FOLLOW(A)=∅FIRST(\beta) \cap FOLLOW(A) = \emptyset

那么，同一非终结符的各个产生式的可选集互不相交。

4.3.8 为 LL(1)LL(1) 文法构造预测分析器 ​

LL(1)LL(1) 的含义：

  • 第一个 L 表示从左向右扫描输入
  • 第二个 L 表示产生最左推导
  • 1 表示在每一步中只需要向前看一个输入符号来决定语法分析动作