编译原理 第四章 自上而下语法分析

编译原理 第四章 自上而下语法分析

4.1 概述

语法分析的本质:是按文法的产生式,识别输入符号串是否为一个句子。即是否能从文法的开始符号出发推导出这个输入串,或者建立一棵与输入串相匹配的语法分析树。

4.2 自上而下语法分析面临的问题

自上而下分析的过程实质上是不断建立直接推导的过程。实质上是一种试探过程,是反复使用不同产生式去试图匹配输入串的过程。

每当对于某个非终结符号的某个选择匹配失败时,必须抹去所构造的失败分支,从而选取另一个选择再行尝试,这种过程称为回溯。

此外,含有左递归的文法将使得自上而下分析过程陷入无限循环。

(左递归产生式:左部符号与右部第一个符号相同。)

任何上下文无关文法都可以通过回溯分析进行识别,但代价很高、效率很低。

4.3 LL(1) 分析法

  • 第一个 L 表示从左到右扫描输入串
  • 第二个 L 表示分析采用最左推导
  • 1 表示分析的每一步只需向前查看一个输入符号,就能确定采取何种动作。

4.3.1 左递归的消除

假定 A 的产生式为:

\[A \rightarrow A\alpha|\beta\]

此产生式称为直接左递归产生式,其中,β 的首字符不是 A。可以改写成如下等价的非直接左递归形式:

\[A \ \rightarrow \beta A' \\ A' \rightarrow \alpha A' | \epsilon\]

一般而言,假定关于 A 的全部产生式如下:

\[A \rightarrow A\alpha_1 | A\alpha_2 | ...|A\alpha_m | \beta_1| \beta_2|...| \beta_n\]

其中 \(\beta_i\) 的首字符不是 A,于是可以改写成:

\[A \ \rightarrow \beta_1 A'|\beta_2 A'|...|\beta_n A' \\ A' \rightarrow \alpha_1 A'|\alpha_2 A'|...|\alpha_m A' | \epsilon \]

1
2
3
4
5
6
7
8
9
算法 4.1 消除文法的全部左递归
(1) 将文法 G 的所有非终结符按任意一种顺序排列成 A1, A2, …,An;
(2) for (i=1; i<=n; i++) {
for (j=1; j<i; j++) {
将形如 Ai→Aj 的产生式改写成 Ai→|δ1γ|δ2γ|,,,|δkγ; //其中Ai→|δ1γ|δ2γ|,,,|δkγ 是关于 Aj 的所有产生式
}
消除关于 Ai 产生式的直接左递归
}
(3) 化简(2)所得的文法,即删除从开始符号出发无法到达的非终结符的产生式。

4.3.2 消除回溯,提左因子

为了消除回溯就必须保证当文法的任何非终结符去匹配输入串时,该非终结符能够根据所面临的输入符号准确地指派某一个候选式去执行任务。

对文法所有非终结符的每个候选 α,定义其终结首符集 FIRST(α) 为:

\[FIRST(\alpha)=\{ \alpha | \alpha \overset{*}\Rightarrow a...,a \in V_T \}\]

特别地,若 \(\alpha \overset{*}{\Rightarrow}\epsilon\),则规定 \(\epsilon \in FIRST(\alpha)\)。即 FIRST(α) 是 α 的所有可能推导出的开头终结符或可能的 ε。

如果非终结符 A 的所有候选首符集两两不相交, 即 A 的任何两个不同候选 \(α_i\)\(α_j\)\[FIRST(\alpha_i) \cap FIRST(\alpha_j)=\emptyset\],那么当要求 A 匹配输入串时,A 就能根据它所面临的第一个输入符号 a,准确地指派某一个候选式,就是那个终结首符集含 a 的 α。

将一个文法改造成任何非终结符的所有候选首符集两两不相交的办法是提取公共左因子。例如,假定关于 A 的产生式如下:

\[A\rightarrow \delta \beta_1 | \delta \beta_2 | ...|\delta \beta_n | \gamma_1|\gamma_2|...|\gamma_m|\]

其中,每个 γ 不以 δ 开头,那么,可以将这些产生式改写成:

\[A \ \rightarrow \delta A'|\gamma_1|\gamma_2|...|\gamma_m \\ A' \rightarrow \beta_1 | \beta_2 | ...|\beta_n\]

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

定义文法非终结符 A 的后随符号集 FOLLOW(A) 如下:

\[FOLLOW(A)= \{ \alpha | S \overset{*}{\Rightarrow}...Aa...,a \in V_T \}\]

特别地,若 \(S \overset{*}{\Rightarrow}A\),则规定 \(\# \in FOLLOW(A)\)。即 FOLLOW(A) 是所有句型中出现在紧接 A 之后的终结符或 #

当非终结符 A 面临输入符号 a,且 a 不属于 A 的任意候选首符集,但 A 的某个候选首符集包含 ε 时,且 a∈FOLLOW(A),就允许 A 自动匹配。

4.3.3 LL(1) 文法

  • 文法不含左递归

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

    \(A\rightarrow \alpha_1|\alpha_2|...|\alpha_n\)

    则: \(FIRST(\alpha_j) \cap FIRST(\alpha_i)=\empty \ \ \ (i\neq j)\)

  • 对文法中的每个非终结符 A,若它存在某个候选首符集包含 ε,则: \(FIRST(A) \cap FOLLOW(A)= \empty\)

若一个文法 G 满足以上条件,就是 LL(1) 文法。

对于一个 LL(1) 文法,可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符 A 进行匹配,面临的输入符号为 a,A 的所有产生式为:

\[A \rightarrow \alpha_1 | \alpha_2 | ...|\alpha_n\]

  • \(a \in FIRST(\alpha_j)\),则指派 \(\alpha_j\) 去执行任务。
  • 若 a 不属于任何一个候选首符集,则:
    • 若 ε 属于某个 \(FIRST(\alpha_j)\),且 a ∈FOLLOW(A),则指派 \(\alpha_j\) 去执行匹配任务;
    • 否则,a 的出现是一种语法错误

4.4 递归下降分析法

对一个 LL(1) 文法,可以构造一个不带回溯的自上而下的语法分析程序——递归下降分析器,该分析程序由一组递归子程序组成,每个子程序对应文法的一个非终结符。

4.4.1 基本思路

  • 为每个非终结符构造一个子程序
  • 每个子程序的函数体按非终结符的候选式分情况展开:
    • 遇到终结符直接匹配
    • 遇到非终结符就调用相应非终结符的子程序
  • 如果所有非终结符都展开为终结符并得到匹配,分析成功结束

可以用某种高级语言写出这样的递归过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool match(int expectedSym) {
if (sym == expectedSym) {
getSymbol();
return true;
} else {
error();
return false;
}
}

// 产生式 F -> (E)|i
void F() {
if (match('(')) {
E();
if (match(')')) return;
else exit;
}
if (match('i')) return;
else exit;
}

4.4.2 流程设计

为了更加紧密地映射递归下降分析程序的代码,可以扩展如下元语言符号:

  • 用花括号 {a} 表示闭包运算 a*;
  • \(\{a\}_n^0\) 表示 a 可任意重复 0 次至 n 次;
  • 用方括号 [a] 表示 \(\{a\}_1^0\)

引入上述元富豪的文法亦称为扩充的巴科斯范式(BNF)。

例如,文法

\[\begin{align}&E\rightarrow T|E+T \\ &T\rightarrow F|T*F\\ &F\rightarrow i|(E) \end{align}\]

可表示成

\[\begin{align}&E\rightarrow T\{+T\} \\ &T\rightarrow F\{*F\}\\ &F\rightarrow i|(E) \end{align}\]

可以用如下语法图来表示:

4.5 预测分析法

实现 LL(1) 而分析的另一种有效方法是使用一张分析表和一个栈进行联合控制——预测分析法。

4.5.1 预测分析程序工作过程

预测分析表是一个 M[A, a] 形式的矩阵。其中 A 是非终结符,a 是终结符或 ## 不是文法的终结符,总是当成输入串的结束符,并不是文法的一部分)。

文法 G:

\[\begin{align}&E'\rightarrow +TE'|\epsilon \\ &T\rightarrow FT' \\ &T' \rightarrow *FT'|\epsilon \\ &F\rightarrow (E)|i \end{align}\]

其对应的 LL(1) 分析表为:

栈 STACK 用于存放文法符号,分析开始时,栈底先放一个 #,然后,放进文法开始符号,同时假定输入串最后也总有一个 #,标识输入串结束。

预测分析程序的总控程序在任何时候都是按 STACK 栈顶符号 X 和当前的输入符号 a 行事的,对于任何 (X, a),总控程序执行以下动作之一:

  • \(X=a=\#\),则宣布分析成功,停止分析过程。
  • \(X=a\not=\#\),则把 X 从 STACK 栈顶逐出,让 a 指向下一个输入符号
  • 若 X 是一个非终结符,查看分析表 M,若 M 中存放着一个关于 X 的产生式,那么首先把 X 逐出 STACK 栈顶,然后把产生式由右部的符号按反序一一推进 STACK 栈(若右部为 ε,则无动作)。在把产生式右部符号推进栈的同时应做这个产生式相应的语义动作。若 M 中存放着出错标志,则调用出错程序。

对文法 G,其输入串为 \(i_1*i_2+i_3\),利用分析表进行预测分析的步骤为:

4.5.2 预测分析表的构造

为了构造预测分析表,首先要构造文法 G 有关的集合 FIRST 和 FOLLOW。

对每一个文法符号 X,构造 FIRST 集合的构造方法:

  1. 若 X 是终结符,则 \(FIRST(X)=\{X\}\)
  2. 若 X 是非终结符,则有产生式 \(X\rightarrow a...\),把 a 加入到 FIRST(X) 中,若 \(X\rightarrow \epsilon\) 也是一条产生式,把 ε 也加到 FIRST(X) 中;
  3. \(X\rightarrow Y...\) 是一个产生式且 Y 是非终结符,则把 FIRST(Y) 所有的非 ε 元素都加到 FIRST(X) 中;若 \(X\rightarrow Y_1Y_2...Y_k\) 是一个产生式,且 \(Y_1,...,Y_{i-1}\) 都是非终结符,而且对于任何 j,其 \(FIRST(Y_j),1\leq j\leq i-1\) 都含有 ε,则把 \(FIRST(Y_i)\) 中的所有非 ε 元素都加到 FIRST(X) 中;若所有的 \(FIRST(Y_j),j=1,2,...,k\) 都含有 ε,则把 ε 加到 FIRST(X) 中。

连续使用以上规则,直至每个集合 FIRST 不再增大为止。

对于文法的每个非终极符 A 否早 FOLLOW(A) 的办法是,连续使用下面的规则,直至每个 FOLLOW 不再增大为止。

  1. 对于文法的开始符号 S,将 # 至于 FOLLOW(S) 中;
  2. \(A\rightarrow \alpha B\beta\) 是一个产生式,则把 FIRST(β)\{ε} 加至 FOLLOW(B) 中;
  3. \(A\rightarrow \alpha B\) 是一个产生式,或 \(A\rightarrow \alpha B\beta\) 是一个产生式且 \(\epsilon \in FIRST(\beta)\),则把 FOLLOW(A) 加至 FOLLOW(B) 中。

上文文法 G 的 FIRST 和 FOLLOW 集合为:

有了 FIRST 和 FOLLOW 集合,构造预测分析表 M 的方法是:

  1. 对文法 G 的每个产生式 \(A\rightarrow \alpha\) 执行第二步和第三步;
  2. 对每个终结符 \(a\in FIRST(\alpha)\),则把 \(A\rightarrow \alpha\) 加至 M[A, a] 中;
  3. \(\epsilon \in FIRST(\alpha)\),则对任何 \(b\in FOLLOW(A)\),把 \(A\rightarrow \alpha\) 加至 M[A, b] 中;
  4. 把所有无定义的 M[A, a] 标上“出错标志”。

对于某些文法,M[A, a] 可能持有若干个产生式,或者说 M[A, a] 是多重定义的。如果 G 是左递归或二义的,那么 M 至少含有一个多重定义入口。因此,消除左递归和提取左因子将有助于获得无多重定义的分析表 M。

可以证明,一个文法 G 的预测分析表 M 不含多重定义入口,当且仅当该文法为 LL(1) 的。

4.6 LL(1) 分析中的错误处理

发现语法错误的两种情况;

  • 栈顶的终结符与当前的输入符号不匹配;
  • 非终结符 A 处于栈顶,面临的输入符号为 a,但 M[A, a] 为空。

错误恢复的基本做法:

  • 跳过输入串中的一些符号,直至遇到“同步符号”为止。

同步符号集的基本取法就是对应非终结符的 FOLLOW 集合。

上文文法 G 加入同步符号的 LL(1) 分析表为:

其对输入串 )i*+i 的带有错误恢复的语法分析过程为:

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×