北京交通大学计算机与信息技术学院：《编译原理》课程教学资源（PPT课件讲稿）第四章 语法分析和语法分析程序（4.1）自顶向下的语法分析

第四章语法分析和语法分析程序 口对象:单词流形式的源程序 口任务:根据语法规则,分析源程序的语法结 构,同时进行语法检查 口输出:语法树 口假定:先不考虑语义问题 口分析方法:自顶向下和自底向上 以前最常用的两种方法:递归下降法和算符 优先分析法

1 第四章 语法分析和语法分析程序 对象：单词流形式的源程序 任务：根据语法规则，分析源程序的语法结 构，同时进行语法检查 输出：语法树 假定：先不考虑语义问题 分析方法：自顶向下和自底向上 以前最常用的两种方法：递归下降法和算符 优先分析法

两种方法的结合 递归下降分析方法自顶向下 根据文法中各语法变量递归定义的特点,用一组相 互递归的子程序来完成语法分析。 算符优先分析方法自底向上 利用各个算符之间的优先关系与结合规则来指导语 法分析,适合于分析算术表达式。 优点:简单,便于手工实现;经常结合起来使 用。 另两种流行方法:预测分析方法(自顶向下) 和LR分析方法(自底向上),广泛用于语法 分析程序的自动生成工具

2 两种方法的结合 递归下降分析方法——自顶向下 – 根据文法中各语法变量递归定义的特点，用一组相 互递归的子程序来完成语法分析。 算符优先分析方法——自底向上 – 利用各个算符之间的优先关系与结合规则来指导语 法分析，适合于分析算术表达式。 优点：简单，便于手工实现；经常结合起来使 用。 另两种流行方法：预测分析方法（自顶向下） 和LR分析方法（自底向上），广泛用于语法 分析程序的自动生成工具

本章内容 自顶向下的语法分析 预处理:消除文法的左递归、消除回溯 递归下降分析法 预测分析法、非LL(1)文法的改造 自底向上的语法分析 简单优先 算符优先、优先函数 LR分析法

3 本章内容 自顶向下的语法分析 – 预处理：消除文法的左递归、消除回溯 – 递归下降分析法 – 预测分析法、非LL(1)文法的改造 自底向上的语法分析 – 简单优先 – 算符优先、优先函数 – LR分析法

4.1自顶向下的语法分析 自顶向下的分析:对已给的输入串w,试图自上而下地 建立一棵语法树;或者说,从S出发,为v构造一个最左 推导(可以一边输入,一边分析)若成功,则 weL闭G,否则拒绝 般说来在为w寻求最左推导的每一步都涉及使用 何产生式进行替换的问题最简单的方法是,逐一试探 遗憾的是,逐一试探也不能完全解决问题例如,在含 有左递归的文法中,就会出现不能终止的替换现象

4 4.1 自顶向下的语法分析 自顶向下的分析:对已给的输入串w,试图自上而下地 建立一棵语法树;或者说,从S出发,为w构造一个最左 推导（可以一边输入，一边分析）.若成功,则 wL(G),否则拒绝. 一般说来,在为w寻求最左推导的每一步,都涉及使用 何产生式进行替换的问题.最简单的方法是,逐一试探. 遗憾的是,逐一试探也不能完全解决问题.例如,在含 有左递归的文法中,就会出现不能终止的替换现象

左递归的文法示例 例:E→TEAT; T->FTMF;F→(E)i;A→>+-;M→*/ 设=计+i每个产生式从左至右尝试从E出发: E→T→F→(E) →TMF→FMF→(E)MF →iMF→iF →i/F → TMFME→ → TMEMEME. E→EAT→TAT→FAT→iAT→计+I→i+TMF→→i+FMF →i+iMF→i+iF→i+i*i

5 左递归的文法示例 例:E→T|EAT; T→F|TMF; F→(E)|i; A→+|-; M→* | / 设w=i+i*i,每个产生式从左至右尝试.从E出发: ETF(E) i TMFFMF(E)MF iMF i*F i/F TMFMF … TMFMFMF... EEATTATFATiATi+Ti+TMFi+FMF i+iMF  i+i*Fi +i*i