国防工业出版社《编译原理》教材（消除回溯）

今天学习了编译原理中的句法分析一章——自上而下分析中的基本问题。 我参考了国防工业出版社的《编译原理》教材1和中国大学MOOC-国防科技大学的《编译原理》PPT。 ，我整理了这一章的内容，希望能够了解这部分知识。

2. 语法分析 2.1． 语法分析的前提是使用形式形式和有限自动机来描述和识别语言的单词符号。 使用上下文无关语法来描述语法规则。 2.2. 语法分析的任务。 2.3 语法分析器的功能编译时使用语法分析器。 在船上的位置

语法分析器在编译器2.4中的位置。 语法分析方法2.4.1． 自下而上（-向上）2.4.2。 自上而下（自上而下）2.5。 2.5.1 自上而下分析方法的问题语法左递归问题

P\P\阿尔法\\

包含左递归的语法使得上述自上而下的分析过程陷入无限循环。

2.5.2. 回溯问题3.消除语法3.1中的左递归。 消除直接左递归

P - P \ | P | \cdots | P | \ | \|\cdots|\ \\

（每个\alpha不等于\，并且每个\beta不以P开头）

P\\P'|\P'|\cdots|\P'\\P'\\P'|\P'|\cdots|\P'|\\\

3.2. 消除间接左递归

S\ Qc|c \\Q\ Rb|b \\R\ Sa|a \\

虽然没有直接左递归，但S、Q、R都是左递归。 例如，

S\Qc\Rbc\Sabc\\

按任意顺序排列文法 G 的所有非终结符 P_1, P_2, \cdots, P_n； 按此顺序执行以下伪代码

FOR i:=1 TO n DO
BEGIN
    FOR j:=1 TO i-1 DO
        (1)
    (2)
END

(1) 将 P_i \ P_j \gamma 形式的规则重写为 Pi \ \\gamma | \ \伽玛| …… | \ \伽玛；

（其中P_j \ \ | \ | \cdots | \都是关于P_j的规则）

(2)消除关于P_i规则的直接左递归

3、简化2得到的语法，去掉生成从起始符号永远无法到达的非终结符的规则。

S\ Qc|c \\Q\ Rb|b \\R\ Sa|a \\

将非终结符排序为R、Q、S。对于R，不存在直接左递归。将R带入Q的相关候选后，我们将Q的规则更改为

Q\ Sab|ab|b \\

现在Q也不包含直接左递归。 带入S的相关候选后，S变为

S \ Sabc|abc|bc|c \\

然后消除S的直接左递归，最终得到的语法为

S \ abcS'|bcS'|cS' \\S' \ abcS' | \ \\Q\ Sab|ab|b \\R\ Sa|a \\

3. 显然，关于Q和R的规则是多余的，我们可以对其进行简化，最终结果如下。

S \abcS'|bcS'|cS' \\S' \abcS' | \ \\

4.消除回溯

即假设现在轮到非终结符A执行匹配任务，A共有n个候选，即

一个\ \| \| \cdots | \ \\

当A面对一个输入符号x时，如果输入的字符串是一个合法的句子，那么A可以分配一个唯一的候选\来匹配x。 如果不能匹配x，则说明输入的字符串不是合法的句子。

4.1. 第一个系列

FIRST(\alpha) = \{ a| \alpha \ a, \cdots a \in V_T \} \\

特别是，如果是 \\，则指定：

\\ 在 FIRST(\alpha) \\

换句话说，FIRST(\alpha)是\alpha的起始终结符或可能的\的可能推导。 如果非终结符A的所有候选第一个符号的集合不相交，即A的任意两个不同候选者\和\

第一(\) \ 第一(\) = \ \\

然后，当需要A匹配输入字符串时，A可以根据它面对的第一个输入符号a准确地分配一个候选者来执行任务。 该候选者是 α，其终端初始符号集包含 a。

4.2. 提取左公因子

假设A的规则是

A \ \delta \ | \delta \ | ……| \delta \ | \ | \ | …… | \ \\

（其中，每个\gamma不以\delta开头）

那么，这些规则可以重写为

A \ \delta A' | \ | \ | \cdots | \ \\A' \ \ | \ | \cdots | \ \\

通过重复提取左因子，可以将每个非终结符（包括新引入的符号）的所有候选第一符号集变为成对不相交。

如果空格词\属于某个非终结符的候选第一符号集，那么问题就更复杂了。 介绍收藏。

4.3. 收藏

假设S是文法G的起始符号。对于G的任何非终结符A，我们定义A的集合

(A) = \{a|S \ ...Aa..., a \in V_T \} \\

特别是，如果

S \ \c点 A \\

规则规定

\＃ \在一个） \\

意思是如果A在句子的结尾，那么标记句子结尾的\#就在A的集合中。

注：部分内容整理自国防工业出版社、中国大学MOOC教材《编译原理》-国防科技大学《编译原理》PPT

5. 参考文献

[1] 陈火旺. 编译原理[M]． 北京：国防工业出版社，2010。

联系电子邮件：

:/

欢迎转载/Star/Fork，如有问题请邮件沟通。