编译原理——自上而下分析与递归下降分析构造（笔记）

目的

构造不带回溯的自上而下分析程序

• 要消除文法的左递归性
• 克服回溯

主要思路

• 分析程序由一组递归过程组成， 对每一语法变量 ( 非终结符 ) 构造一个相应的子程序，识别对应的语法单位
• 通过子程序间的相互调用实现对输入串的识别
• 这样的分析程序称为递归下降分析器 ( 因为文法的定义
  通常是递归的 )

过程与变量

• ADVANCE：把输入串指示器 IP 指向下一个输入符号，即读入一个单字符号（调用词法分析器，取下一个符号）

• SYM：IP 当前所指的输入符号（取得的符号）

• ERROR ：出错处理子程序

实例

每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开 ( 推导 ) 时，就调用这个非终结符对应的子程序。

也即是，每个子程序对应一个非终结符（语法单位），遇到这个语法单位时，就掉用对应的子程序。

如，Ｅ就有一个子程序，负责E的识别、推导。该则程序负责调用T和E’。T等同理。
注意，文法必须是LL(1)文法才可以（动作唯一）。

模板

1

2

第一种写法，

ELSE IF检查的是，是否为终结符，是就结束，不是就是报错。
另外一种

两种都没有问题。

第二种，虽然没有检查follow集合，但下一个字符的会检查first集合。换言之，即是让后面的程序去检查当前的结果是否正确。
这样导致的是，程序报错位置的区别。

主程序就是开始符，是就开始。

巴科斯范式文法

在元符号“→”和“ |” 的基础上，扩充几个元语言符号

如

成图

参考文献

[1] 《程序设计语言编译原理》第三版 陈火旺
[2] 编译原理教程以及课件