北京交通大学计算机与信息技术学院：《编译原理》课程教学资源（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

自顶向下分析方法的特点 若G有左递归,则分析不能正常进行因此,自顶向下分 析必须先消除文法的左递归 2.分析过程是反复进行试探的过程因此难免会出现大 量的回溯特别是当形红LO时,只有在穷举完所有的 试探后才能拒绝ν 由于回溯就需将从出错点到迄今为止已做过的大量 工作废弃,显然会大大降低分析的效率特别是在语法 分析阶段还往往要进行同步的语义分析和处理这些 工作也就白做了因此消除回溯是自顶向下分析的另 目标 3.当拒绝w时,只能知道v不是句子不知出错的性质及 位置

6 自顶向下分析方法的特点 1. 若G有左递归,则分析不能正常进行.因此,自顶向下分 析必须先消除文法的左递归; 2. 分析过程是反复进行试探的过程,因此,难免会出现大 量的回溯.特别是当wL(G)时,只有在穷举完所有的 试探后才能拒绝w. 由于回溯,就需将从出错点到迄今为止已做过的大量 工作废弃,显然会大大降低分析的效率.特别是在语法 分析阶段还往往要进行同步的语义分析和处理,这些 工作也就白做了.因此,消除回溯是自顶向下分析的另 一目标. 3. 当拒绝w时,只能知道w不是句子,不知出错的性质及 位置

4.1.1消除文法的左递归 设文法是已简化的若文法含直接左递归式 A→Aa|B(a∈V+),β不以A打头,则类似正规 式求解方法有A→β{a}(βx*,{a表示中{}的符号 串α可以出现0次或多次。 引入新的非终结符A,令其产生α则有: A→βA;A→aA'E消除直接左递归 对文法:E→TEAT;T→FTMF;F→(E)i;A→+; M→>*|/ 可改写为:E→TE’;E→ATE'e;T→FT T”→MFTE:F>(E);A→+:M

7 4.1.1 消除文法的左递归 设文法是已简化的.若文法含直接左递归式: A→A |  (V+) , 不以A打头，则类似正规 式求解方法,有A→ {} (*). {} 表示中{ }的符号 串可以出现0次或多次。 引入新的非终结符A’,令其产生* ,则有: A→ A’；A’→ A’| 消除直接左递归. 对文法：E→T|EAT; T→F|TMF; F→(E)|i; A→+|-; M→* | / 可改写为：E→TE’；E’→ATE’|；T→FT’ T’→MFT’|；F→(E)|i；A→+|-；M→ *|/

消除文法的左递归 一般地设文法中全部A产生式为 A→Aa|Aa-.1Aanlβ1…JBm,其中,β不以A打头, 则消除直接左递归后的产生式为 A→>B1A-.|BmA;A→A'…,anA’e 消除文法的间接左递归: 将原文法进行代入变换后,再应用上述方法 例如,S→Abc;A→Sa,可将其变换为S→Sabc,再 使用上述方法得S→cS;S→abS|e 消除过程:找出具有左递归(包括间接左递归)的所 有非终结符,对相关的产生式进行代入变换,逐步转 变为直接左递归的产生式,最后统一进行消除

8 消除文法的左递归 一般地,设文法中全部A-产生式为 A→A1|A2|…|An| 1|…| m,其中, i不以A打头, 则消除直接左递归后的产生式为 A→1A’|…| mA’；A’→ 1A’|…| nA’|  消除文法的间接左递归： – 将原文法进行代入变换后，再应用上述方法 – 例如, S → Ab|c；A→Sa,可将其变换为S →Sab|c,再 使用上述方法,得S →cS’；S’ →abS’ |  消除过程：找出具有左递归（包括间接左递归）的所 有非终结符，对相关的产生式进行代入变换，逐步转 变为直接左递归的产生式，最后统一进行消除

消除文法左递归的矩阵方法 设文法的非终结符为X,X2,…,Xn,其中,的产生式 可分为以非终结符和终结符打头的两类类似正规式 方法将“改写为‘+’,有 XiX1O1H+x202+…+Xn+pi 其中,β是以终结符打头的产生式之和,aki(a∈V+) 可以为φ,这样,文法G可表示为 1112 (x12X2…;Xn)=(X12X2…Xn +(β12,…Bn) C, d 或写成向量和矩阵形式:X=XA+B

9 消除文法左递归的矩阵方法 设文法的非终结符为 X1, X2, …, Xn, 其中,Xi的产生式 可分为以非终结符和终结符打头的两类.类似正规式 方法,将‘|’改写为‘+’ ,有 Xi=X11i+X22i+…+Xnni+i 其中, i 是以终结符打头的产生式之和, ki (kiV+) 可以为 ，这样,文法G可表示为 ( , , , ) ( , , , ) ( , , , ) 1 2 1 2 2 1 2 2 2 1 1 1 2 1 1 2 1 2 n n n n n n n X X Xn X X Xn +                         =         或写成向量和矩阵形式: X=XA+B

矩阵求解 该方程有解:X=BA*。而 A*=I+A+A2+A3+ I+AA> 其中,I 则有:X=BZ;Z=IHAZ 其中X的产生式以终结符打头,因此无直接左递归和 间接左递归;而Z的产生式以ak∈V+打头,因此不含直 接左递归,又因B以终结符打头,也不含间接左递归 由此所得的文法含有无用符号和无用产生式需化简

10 矩阵求解 该方程有解: X=BA*。而 则有: X=BZ; Z=I+AZ 其中X的产生式以终结符打头，因此无直接左递归和 间接左递归；而Z的产生式以kiV+打头,因此不含直 接左递归，又因B以终结符打头， 也不含间接左递归. 由此所得的文法含有无用符号和无用产生式,需化简           = =           = = + + + + = + n n n n Z Z Z Z I A Z A I A A A I AA        1 1 1 1 2 3 , , * * * 其中 令    