编译原理：自上而下语法分析

发表于 2022-01-04 分类于编译原理本文字数： 1.8k

自上而下分析遇到的问题

左递归
回溯

消除左递归

直接左递归

P \to P α | β

文法 $P \to P α | β$ 表示非终结符 $P$ 可以通过左递归生成以 $β$ 开头、后接零个或多个 $α$ 的字符

$β$ 不以 $P$ 开头，推导后可得

\begin{aligned} P & \Rightarrow P α | β \\ \Rightarrow P α α \\ \Rightarrow P α α . . . α \\ \Rightarrow β α α . . . α \end{aligned}

也就是会进入不断地递归，但是这个文法结束的时候一定是开头为 $β$ 的时候

void ParseP() {
	ParseP(); //开头仍为 P ，需要继续分析，陷入死循环
   	...
}

左递归转右递归

既然能够确定 $P$ 结束的时候一定是以 $β$ 开头，不如直接将文法转化为：

P \to β P^{'} P^{'} \to α P^{'} | ε

于是递归就转换到了产生式右边的结尾。

在进行语法分析时，产生式将不断地将源程序读入与终结符 $α$ 进行匹配，故在面对有限长度的程序输入时不会陷入死循环

void ParseP() {
	if (curToken == 'b') {
        nextToken(); // 匹配到了一个 b，所以可以读入下一个单词
        ParseP2();
    }
    ...
}
void ParseP2() {
    if (curToken == 'a') {
        nextToken();// 匹配到了一个 a，所以可以读入下一个单词
        ParseP2();
    }
    ...
}

左递归文法：

P \to P α_{1} | P α_{2} | . . . | P α_{m} | β_{1} | β_{2} | . . . | β_{n}

转化为右递归：

\begin{aligned} P & \to β_{1} P^{'} | β_{2} P^{'} | . . . | β_{n} P^{'} \\ P^{'} & \to α_{1} P^{'} | α_{2} P^{'} | . . . | α_{m} P^{'} | ε \end{aligned}

例题：

&& E \rightarrow E+T|T \\ 转化后：&& \\ &&E \rightarrow TE' \\ &&E' \rightarrow +TE'

间接左递归

直接看产生式没有左递归，但是在推导过程中产生了左递归

文法消除左递归的条件：

不含以 $ε$ 为右部的产生式
不含回路，，即不含 $P \overset{+}{\Rightarrow} P$

消除思路：

将文法 G 的所有非终结符按照任一种顺序排列 $P_{i}$
把 $P_{i}$ 的规则改造成 $P_{i} \to a . . | P_{i + 1} . . . | P_{i + 2}$ … ，即产生式右部若以非终结符开头，一定要是按照第 1 步的顺序 $P_{i}$ 往后的非终结符，如果不是，则用其定义进行替换
化简，删除无用的产生式

由于排序不同，得到的产生式可能不一样，但是是等价的

消除回溯

A \to B | C B \to a b d C \to a b c d

A 可能的两个候选都是非终结符开头，若选择用 B 去匹配，若源程序为 “abcd”，则匹配到 ‘c’ 的时候发现不符合 B 的文法规则，于是需要回溯到 ‘a’，再使用 C 进行匹配。

解决思路

A \to α_{1} | α_{2} | α_{3} | . . . | α_{n}

终结首符集 (FIRST 集合)：将来若干步推导后在开头出现的终结符集合

F I R S T (α_{i}) = {α_{i} | α_{i} \overset{*}{\Rightarrow} a . . ., a \in V_{T}}

可能包含空字

FIRST( $α$ ) 也就是选择非终结符候选 $α$ 后，经过若干步推导、可能存在于首部的非终结符的集合

要根据 FIRST( $α$ ) 确定选择哪个候选，前提条件是任意两个候选的 FIRST 集合都不相交。

提取公共左因子

引进非终结符和新的产生式

A \to \var β_{1} | \var β_{2} | \var β_{3} . . .

可改写为

A \to \var A^{'} A^{'} \to β_{1} | β_{2} | . . . | β_{n}

候选含有空字

A \to α_{1} | α_{2} | α_{3} | . . . | α_{n} | ε

若此时遇到了要匹配的字符 a，是否应该使用 A 的空字去匹配，应该取决于 A 之后是否有其他符号可以匹配 a，所以需要有 FOLLOW 集合（S 为开始符号）

F O L L O W (A) = {a | S \overset{*}{\Rightarrow} . . . A a . . ., a \in V_{T}}

就是在某个句型里，可能跟在 A 后面的终结符

若存在 $S \overset{*}{\Rightarrow} . . . A$ 则规定 # $\in$ FOLLOW(A)‘

LL(1) 文法

含义

L: 从左到右

L: 最左推导

1: 根据当前单词分析

规则

不含左递归
所有产生式的所有候选的 FIRST 集合不相交
对每个非终结符 A 如果候选的 FIRST 集合包含空字，则
$F I R S T (α_{i}) \cap F O L L O W (A) = ϕ$
也就是当需要使用 $ε$ 的时候，一定是不得已而为之（候选 FIRST 集合内没有当前这个输入字符），且之后有其它推导可以匹配当前的这个字符，如果之后也没有，则报错。

分析

A \to α_{1} | α_{2} | α_{3} | . . . | α_{n}

若 $a \in F I R S T (α_{i})$ ，则指派 $α_{i}$ 执行任务
若 $a \notin F I R S T (α_{i})$ ：
1. $ε \in F I R S T (α_{i})$ 且 $a \in F O L L O W (A)$ ，则让 A 与 $ε$ 匹配
2. 否则出错

SELECT 集合

S E L E C T (A \to α) = {\begin{array}{rcl} (F I R S T (α) - {ε}) \cup F O L L O W (α) & α \overset{*}{\Rightarrow} ε \\ F I R S T (α) & α \overset{*}{⇏} ε \end{array}

代表的是当遇到某个字符 a 的时候，如果 $a \in S E L E C T (A \to α)$ ，则应该使用 A 的候选 $α$ 来匹配 a

FIRST 与 FOLLOW 的构造

F I R S T (α_{i}) = {α_{i} | α_{i} \overset{*}{\Rightarrow} a . . ., a \in V_{T}}

对每一个 $X \in V_{T} \cup V_{N}$ :

若 X 本身就是终结符，则 FIRST(X) =
若 $X \to a . . .$ ，则 a 加入 FIRST(X) 中，若推出空字也加入
若 $X \to Y . . .$ 是一个产生式，则 FIRST(Y) 的所有非空字（因为 Y 后可能还有其他符号）元素加入 FIRST(X)
若 X 可以推出很长的符号串，且前 j 个符号都是非终结符，且都能推出 $ε$ ，则需要将第 j + 1个符号的 FIRST 集合加入 FIRST(X)
如果 X 可以推出的符号串中的所有符号都可以推出 $ε$ ，则 $ε$ 应该加入 FIRST(X)

F O L L O W (A) = {a | S \overset{*}{\Rightarrow} . . . A a . . ., a \in V_{T}}

对每个非终结符 A

对于文法的开始符号，将 # 加入 FOLLOW(S)
若 $A \to α B β$ 是一个产生式，则把 $F I R S T (β) - {ε}$ 加入 FOLLOW(B)（ $β$ 的第一个字符就是 B 的后继字符）
若 $A \to α B$ 是一个产生式，或 $A \to α B β$ 是一个产生式而 $β \overset{*}{\Rightarrow} ε$ ，则把 FOLLOW(A) 加入 FOLLOW(B) 中（B 在 A 产生式的最右边，所以跟在 A 后面的元素也可能跟在 B 后面）

总结：

看有没有产生式是一个非终结符跟在另一个非终结符后面的，有的话，就要考虑将后面的 FIRST 加入前面 FOLLOW
看有没有位于产生式末尾的非终结符，或者位于产生式末尾的非终结符可能推出 $ε$ ，有的话，则考虑将左部的 FOLLOW 加入末尾的 FOLLOW

预测分析

总控程序
分析表： $M [A, a]$ 矩阵， $A \in V_{n}, a \in V_{T} \cup {#}$
分析栈：
- 初始状态：#E
- 读入新的符号 a，查表 M[E, a]，并将查询结果压入分析栈

构造预测分析表

构造 FIRST 集合和 FOLLOW 集合
构造分析表

A \to α

应该放到分析表中的 A 行，放到 $F I R S T (α)$ 中所有元素的列中

A \to ε

应该放到分析表中的 A 行，放到 $F O L L O W (α)$ 中所有元素的列中

所有没有定义的格子上放上出错标志

若文法满足 LL(1)，其上不会有多重定义入口（也就是表格内的一个单元格有两个值）

若含左递归 / 二义性则有多重定义入口