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

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

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\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 基本思路

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

4.4.2 流程设计

4.5 预测分析法

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

Comments

Your browser is out-of-date!

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

×