第5章 语法分析(2)自下而上分析 (编译原理 陈火旺).ppt

1、1,自上而下 从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导（最左推导），若能推导出与输入字串相同的句子,则表示输入字符串是合法的； 特点 从文法开始符开始； 推导中始终使用产生式的右部替换左边的非终结符； 自下而上 根据文法,对输入符号串进行归约,若能正确地归约为文法的初始符号,则表示输入字串是合法的。 归约：在输入串中，寻找一条产生式的右部，如果找到用产生式的左边的非终结符替换右部。 特点 从输入串开始； 归约中始终使用产生式的左部替换右边的候选式；,2,5.1 自下而上分析的基本问题- 重点 自下而上分析的基本思想、归约、规范归约、短语、直接短语、句柄等概念， 规

2、范归约自下而上分析法 5.2 算符优先分析- 重点难点 算符优先文法、算符优先分析算法、优先表的构造、最左素短语、优先函数 * 5.3 LR分析法 5.4 语法分析器的自动产生工具 YACC-了解,自下而上语法分析：教学内容,3,5.1 自下而上分析的基本问题,自下而上分析法的基本思想： 从输入串出发，反复利用产生式逐步进行“归约”，如果最后能归约到文法的开始符号，则输入串是句子，否则输入串有语法错误。 各种不同自下而上分析法一个共同特点是： 边输入单词符号（移进栈），边归约；,4,5.1 自下而上分析的基本问题,自下而上分析的基本技术是采用归约栈,如下图所示: 把输入符号依次移入栈内,当栈顶

3、符号串形成某产生式的右部时，就归约为产生式左部非终结符; 继续移入输入字串，直到栈中归约为文法初始符号S. 这种方法也称为“移进归约法”.,5,5.1 自下而上分析的基本问题,定义：栈顶形成的某产生式的候选称为归约串。 自底向上分析方法，也称移进归约分析法，粗略地说它的实现思想是对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个归约串时，（某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号串，这称为归约。重复这一过程直到归约到栈顶中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。,6,例5.1 GS: SaAcB

4、e Ab|Ab Bd 分析句子 abbcde 是否为合法的句子 分析栈 动作 源串 分析栈 动作 源串,经分析,判定该句子是G合法的句子.,7,5.1.1 归约,归约串分为：可归约串、非可归约串 在上例中,当栈中为aAb时,存在两个归约串:b及Ab,都可以归约为A； 若使用b进行归约，栈中得到aAA,导致最终不能归约为S,因此，判定输入字符串非法； 这是一种错误归约, 原因在于栈中同时存在多个归约串,而只有一个归约串的选择是正确的,如Ab； 把Ab称为可归约串，而b为非可归约串,8,5.1.1 归约,自下而上分析的核心问题：就是寻找句型中的“可归约串”进行归约。 对“可归约串”概念的不同定义，

5、就形成了不同的自下而上的分析方法。 在“规范归约”中，则用“句柄”来刻画“可归约串” 在“算符优先分析法”用“最左素短语”来刻画”可归约串”,9,5.1.1 归约,语法分析树: 一棵倒立的树,可用于描述语法分析的过程； 自上而下分析采用的方法是推导，从根到叶子构造分析树。 或者说从文法的开始符号产生句子。 自下而上分析采用的方法是归约，从叶子到根构造分析树。 或者说从句子开始归约出文法的开始符号。 语法树的一个子树：由该树的某个结连同它的所有子孙组成。 在自下而上分析过程中，每一步归约都可画出一棵子树。 例如,上例中的归约过程可描述为如下分析树:,例5.2：文法GS, 其4条产生式如下： Sa

6、ABe Ab AAbc Bd 对句子abbcde的分析 最右推导 最左归约,A,aAbcde,A,aAde,B,S,aABe,S,SaABeaAdeaAbcdeabbcde,abbcde,，aAbcde,，aAde,，aABe,，S,11,一个简单的归约过程,a b b c d e,例5.3 设文法为： S aAcBe A b A Ab B d (5.1) 句子abbcde的分析：abbcde, S , aAcBe , aAcde , aAbcde ,12,5.1.1 归约,归约与推导关系： 推导与归约互逆关系 最右推导称为 最右推导得到的句型称为规范句型 最左归约称为,规范推导,规范归约,1

7、3,5.1.2 规范归约简述,令G是一个文法，S是文法的开始符号 短语 假定是文法G的一个句型，如果有： S*A 且 A + 则称是句型 相对于非终结符A的短语。 直接短语 如果有 S*A 且 A 则称是句型 相对于规则 A 的直接短语。 句柄：一个句型的最左直接短语。 注意：短语的两个条件缺一不可, A是句型，符号串可由A出发推导出来。,14,例5.4 求P85.(5.2)文法的另一个句型 E+T*F+i 的短语。 解：EE+TE+T+TE+T*F+TE+T*F+FE+T*F+i EE+T*F+i EE+T*F TT*F T+i Fi 短语有4个：E+T*F+i (相对于E)； E+T*F(

8、相对于E)； T*F(相对于T)；i (相对于T、F) 。 T*F 和 i 为直接短语 T*F为句柄。,15,5.1.2 规范归约简述,语法树的一个子树的所有叶结点的自左至右排列形成一个相对于子树根的短语。P86 有多少棵子树就有多少个相对于子树根结(非终结符)的短语, 短语由某子树的全部叶结点组成。 若短语是由某子树根经过1步推导得到的，则称之为该子树根的直接短语。,16,例5.4 求P85.(5.2)文法的另一个句型 E+T*F+i 的短语。 解：EE+TE+T+TE+T*F+TE+T*F+F E+T*F+i 短语有4个：E+T*F+i (相对于E)； E+T*F(相对于E)； T*F(相

9、对于T)； i (相对于T、F) 。 T*F 和 i 为直接短语 (相对于规则 T T*F 和 F i ) 。 T*F为句柄。,17,练习,文法G(S): S (L)|aS|a L L , S |S (1) 画出句型 (S,(a) 的语法树。 (2) 写出上述句型的所有短语、直接短语和句柄。,18,5.1.2 规范归约简述,一个句型只有一个句柄，不同句型一般有不同句柄，每次归约都对句柄进行归约 - 这就是规范归约。 规范归约 假定是文法G的一个句子, 称序列 n , n-1 , n-2, , 0 是的一个规范归约，如果此序列满足： (1) n = ; (2) 0 为文法的开始符,即 0 =S;

10、 (3) 对于任何的i，0i n, i-1 是从 i 经把句柄替换为相应产生式的左部符号而得到的。,例5.5文法GS, SaABe Ab AAbc Bd求句子abbcde的规范归约。,abbcde,aAbcde,aAde,aABe,S,abbcde的规范归约为： abbcde，aAbcde，aAde，aAB，S,20,5.1.2 规范归约简述,规范归约是一种较常用的自下而上分析方法。 规范归约：是关于句子的一个最右推导的逆过程。 也称最左归约。 规范归约采用句柄来刻画可归约串。 每次归约总是句型的句柄归约。,21,5.1.2 规范归约简述,为加深对句柄和归约等概念的理解，用修剪语法树方法进一步

11、阐明规范归约这一自下而上分析过程。 一个句型的句柄是该句型对应的语法树中最左直接短语 。 可采用修剪语法树方法实现归约，即寻找当前语法树的句柄，将句柄中的树叶剪去(归约)，不断修剪直到只剩根结点，完成整个规范归约过程.,22,例5.6 文法GS, SaABe Ab AAbc Bd求对句子abbcde的规范归约。,a,b,b,c,d,e,abbcde 4,A,aAbcde3,A,aAde 2,B,aABe 1,S 0,归约-剪子树,S,规范归约为： abbcde，aAbcde，aAde，aABe，S,句型abbcde的句柄是b ，把句柄剪去（归约）就形成了句型aAbcde的语法树。,23,练习：

12、文法G(S): S (L) | aS | a L L , S | S （1）指出句子 (a,(a) 的规范归约; （2）指出每次归约用的句柄。,解：（1）规范归约： (a,(a),(S,(a),(L,(a),(L,(S),(L,(L),(L,S),(L),S,（2）每次归约用的句柄：,24,自下而上分析器结构,i + i i #, #,移进归约 控制程序,输出,核心是分析表，如P90.表5.1；P101.图5.5 与LL(1)分析器的体系结构比较 - 类似,分析栈,输入缓冲区,分析表,25,移进归约：系统框架,输入缓冲区：保存输入符号串，设符号串以#为结束符,有一个指针,指向当前输入符号。 分

13、析栈(符号栈)：保存文法符号,记载分析的历史 已经得到的部分结果；指示分析的下一步动作 -展望未来。 控制程序：控制分析的过程，输出分析结果。分析中，栈顶未形成可归约串时则移进当前输入符号到栈；当栈顶形成可归约串(是某个非终结符的某个候选式)时则归约: 栈顶的可归约串出栈, 该非终结符进栈。,26,5.1.3 符号栈的使用与语法树的表示,符号栈的使用 自下而上分析法要使用一个符号栈(语法分析的一种基本数据结构),分析中根据符号栈顶是否形成句柄决定是移进还是归约。 符号栈 输入串 分析开始： # # 分析中： # # 分析结束时： # S # 则成功，达不到这种格局则输入串有错误。 分析中任何时

14、候： 栈中符号串+剩余输入串 = 规范句型。,移进归约例(5.1):分析输入串abbcde,28,规范归约分析算法,1. 在栈底放入# ，在输入串尾附上#; 2. 逐个移入输入符号,当栈顶形成句柄时，进行归约; 3. 重复(2) 直到输入串已全部进栈，仅剩#, 4. 若栈中归约为#S, 表示分析成功，输入串为合法的句子,否则为非法句子.,29,5.1.3 符号栈的使用与语法树的表示,语法分析对符号栈的使用有四类操作：P88 1) 移进：将当前输入符号移入栈。 2)归约：用产生式左侧的非终结符替换栈顶的可归约串。 3) 接受：分析成功,分析结束,接受输入串。 4) 出错：出错处理。,注意: 可归

15、约的串在栈顶，不会在内部,例5.7 i1*i2+i3 的规范归约步骤(P88.),0 # i1 * i2 + i3# 预备 i1 * i2 + i3 1 #i1 * i2 + i3 # 读入 i1 , i1进栈 2 #F * i2 + i3 # 归约，Fi F * i2 + i3 3 #T * i2 + i3 # 归约，T F T * i2 + i3 4 #T* i2 + i3 # 读入* , *进栈 5 #T* i2 + i3 # 读入 i2 , i2进栈 6 #T*F + i3# 归约，F i T * F + i3 7 #T + i3 # 归约，T T*F T + i3 8 #E + i3

16、 # 归约，E T E + i3 9 # E+ i3 # 读入+ , +进栈 10 #E+ i3 # 读入 i3 , i3进栈 11 #E+F # 归约, F i E + F 12 #E+T # 归约, T F E + T 13 #E # 归约，E E+T E 开始符号 14 #E # 接受,步骤 符号栈 输入串 动作 句型和句柄,31,作业： P133 1 2,32,回顾：,自下而上语法分析方法 - “移进-归约”法 符号栈顶 没有形成 可归约串, 决定是 移进 形成 归约 定义可归约串要解决： 1. 定义什么样的符号串是可归约串； 2. 在分析时怎样判定符号栈顶出现了可归约串； 3. 如何

17、归约。,33,5.2 算符优先分析,算符优先分析的基本思路: (1) 解决谁先归约: 规定算符(终结符)的优先关系和结合性质,(2) 确定可归约串: 采用比较相邻运算符(终结符)的优先顺序来确定可归约串 - 最左素短语 (3) 进行归约,算符优先文法及优先表的构造 (5.2.1),优先函数及构造 (5.2.3),34,例5.8 表达式文法GE ： EEE|E-E|E*E|E/E|EE|(E)|i 对这个二义文法可能会有好几个规范推导和归约，真正运算时也有几种不同结果。 如果规定算符(终结符)的优先级从高到低为：乘幂运算符，乘、除运算符，加、减运算符；同级运算符服从左结合原则；有括号时，先括号内

18、后括号外，那么，句子的归约过程就是唯一的。 注：对所有的终结符定义某种优先关系，借助这种关系找出可归约的串，进行归约，达到自下而上分析的目的。,35,如： i+i-i*(i+i)归约过程如下： 1) i+i-i*(i+i) 设算数级别最高，最先归约； E+i-i*(i+i) E+E-i*(i+i) ，同级，先归约左边“” E-i*(i+i) E-E*(i+i) ，不同级，先归约右边“” E-E*(i+i) ，（不同级，先归约右边“（” E-E*(i+i) E-E*(E+E) 先算括号内，再算括号外 E-E*(E) E-E*E 先归约“”，再归约“” E-E E,栈顶的终结符跟要进栈的终结符对比

19、优先级,上述归约过程是唯一的。 上述归约过程中起决定作用的是相邻两个终结符之间的优先关系。一旦确定了这种优先关系，就可以借助这种关系去寻找可归约串并进行归约。,36,什么是算符优先分析法？ 所谓算符优先分析法是仿效四则运算的计算过程而构造的一种语法分析方法。 算符优先分析法的特点： 简单直观，特别方便于表达式分析，易于手工实现，是自下而上的归约过程，但未必按照句柄归约。 算符优先分析法的关键： 规定算符（终结符）的优先级而决定应采用的动作。,5.2 算符优先分析,37,5.2 算符优先分析,要完成运算符间优先级的比较，可以先定义各种可能相继出现的运算符的优先级，并表示为矩阵的形式（优先表），使

20、得能够在分析中通过查询矩阵元素而得到算符之间的优先关系。 终结符号a与b之间的优先关系有三种： a b 表示a的优先级低于b a b 表示a的优先级等于b a b 表示a的优先级高于b,这三个关系不同于数学中的 ,38,5.2.1 算符优先文法及优先表的构造,算符文法 一个文法，如果它的任何产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部： QR 则称该文法为算符文法。 在后面的定义中，a、b代表任意终结符；P、Q、R代表任意非终结符；代表由终结符和非终结符组成的任意序列，包括空字。,39,例5.9：文法 GE: EEE|E-E|E*E|E/E|EE|(E)|-E|i

21、是算符文法， 例5.10: 文法 EEAE|(E)|-E|i A|*| / | 不是算符文法,因为它的任何产生式的右部都不含两个相继(并列)的非终结符,因为产生式EEAE的右部EAE具有相继并列的非终结符号。,40,算符优先关系的定义,假定G是一个不含产生式(P)的算符文法。对于任何一对终结符(a,b)，有序对, a在前b在后, 定义： (1) a b 当且仅当文法G中含有形如 P ab或P aQb的产生式;,a,b在产生式中相邻, 将同时被归约,a,b在句型中相邻, 而b将先于a被归约,(2) ab当且仅当G中含有形如 P aR 的产生式, 而 R+ b 或 R + Qb;,(3) ab当且

22、仅当G中含有形如 P Rb 的产生式， 而 R+ a 或 R + aQ;,a,b在句型中相邻, 而a将先于b被归约,41,算符优先关系的定义,说明: 终结符号对(a, b)的优先关系是有序的, a、b在句型中相邻，a在前而b在后。 优先关系和代数中的大于小于关系不同，aa，终结符所处的左右位置很重要。 例如：有+ +。,42,算符优先文法,算符优先文法(OPG) 如果一个算符文法G中的任何终结符序偶(a, b)至多只满足下述三种关系之一： a=b, ab 则称G是一个算符优先文法。 例5.4 P90.文法(5.3)是算符优先文法, 因为 它是算符文法; 它的任何终结符号对至多只有一种优先关系，

23、见P90.表5.1的优先表。,43,算符优先表,44,例5.11 试说明下述文法G是算符文法，但不是算符优先文法。 EE+EE*E(E)i 解: 由于文法G的任一产生式右部都不含两个相邻的非终结符，故文法G是算符文法。 (1)由于存在EE+E，而E+E中第二个E可推出E*E， 故有+* 可见, 运算符+和*之间同时存在两种不同的优先关系，故文法G不是算符优先文法。,45,P 133 2 （a，（a，a）,46,算符优先表 注：,1）在此表中，包括，*包括/，“”是一个特殊符号，用于语句的开始符号和结束符号。 2）这张表满足通常数学上的习惯约定。值得注意的是： a、运算量i的优先级高于算符； b

24、、语句开始和结束符号“”与终结符a相继出现时，应该有#,以此来保证语句内先归约。 3）(= )表示括号是成对归约的。 4）优先关系和代数中的大于小于关系不同，aa，终结符所处的左右位置很重要。,47,优先关系表的构造,设文法G是算符优先文法, 下面讨论算符优先表的构造方法, 即确定文法的任意终结符号对(a, b)的优先关系。 找出满足关系 a=b 的符号对，只要检查文法的每条产生式即可确定。 如 P90.文法(5.3), 因为有E(E), 故有( = ) 。 为了找出满足关系 ab 的符号对, 需要先定义非终结符P的FIRSTVT(P)(首终结符集)和LASTVT(P)(尾终结符集)集合。,4

25、8,FIRSTVT(P)集合与LASTVT(P)集合,非终结符P 的FIRSTVT(P)集合定义： FIRSTVT(P) =a|P+a或P +Qa, aVT而 QVN 由非终结符P能够推出来的第一个终结符的集合。 非终结符P 的LASTVT(P)集合定义: LASTVT(P) =a|P+a或P +aQ, aVT而 Q VN 由非终结符P能够推出来的最后一个终结符的集合。,49,构造集合FIRSTVT(P)的算法P91,按定义, 可用下面两条规则来构造集合FIRSTVT(P): (1) 若有产生式 Pa或 P Qa, 则aFIRSTVT(P) (2) 若aFIRSTVT(Q)，且有产生式 P Q

26、, 则aFIRSTVT(P) 注：规则1 是求P FIRSTONE a的关系； 规则2 是求P FIRST* Q的关系。 P91.有一个形式化的构造算法。不讲。,50,同样可用下面两条规则来构造集合LASTVT(P)的算法： (1) 若有产生式 P a或 P aQ， 则aLASTVT(P) (2) 若aLASTVT(Q),且有产生式P Q, 则aLASTVT(P),构造集合LASTVT(P)的算法,51,例5.12 试构造文法GE的FIRSTVT集。 GE: EE+TT TT*FF F(E)i 解: 根据规则(1)知： 由EE+得, FIRSTVT(E)=+； 由TT*得, FIRSTVT(T

27、)=*； 由F(和Fi得,FIRSTVT(F)=(,i 根据规则(2)知： 由TF和FIRSTVT(F)=(,i得, FIRSTVT(T)=*, (, i； 由ET和FIRSTVT(T)得, FIRSTVT(E)=+, *, (, i,52,例5.13 试构造文法GE的LASTVT集。 GE: EE+TT TT*FF F(E)i 解: 根据规则(1)知： 由E+T得, LASTVT(E)=+ 由T*F得, LASTVT(T)=* 由F)和Fi得,LASTVT(F)=),i 根据规则(2)知： 由TF和LASTVT(F)得, LASTVT(T)=*, ), i; 由ET和LASTVT(T)得,

28、LASTVT(E)=+, *, ), i。,53,练习 求下列文法GS中每个非终结符的FIRSTVT和LASTVT集合： SSaF|F F FbP|P P c|d 解：每个非终结符的FIRSTVT集合： FIRSTVT(S) = a, b, c, d FIRSTVT(F) = b, c, d FIRSTVT(P) = c , d 每个非终结符的LASTVT集合： LASTVT(S)= a, b, c, d LASTVT(F) = b, c, d LASTVT(P) = c, d ,54,由FIRSTVT(P)和LASTVT(P)集合确定优先关系 P91,有了FIRSTVE和LASTVT这两个集

29、合后，就可以通过检查每个产生式的候选式确定满足关系的所有终结符对。 例如：假定有个产生式的一个候选式 为 aP 那么，对任何 bFIRSTVT(P)，有ab。,55,构造优先关系表的方法,对形如ab或aQb的产生式候选式,有a= b； 对形如aP的产生式候选式, 若 bFIRSTVT(P),则ab； 对文法开始符号S,有# #， 且对#S#，有# = #。,为了考虑语句的开始符号与结束符号“#”，对文法拓广加一个产生式S#S#，,56,例5.14 构造文法GE的算符优先关系表。 GE:EE+TT TT*FF F(E)i 解:对每个非终结符,求出: FIRSTVT(F)= ( , i LASTV

30、T(F)= ) , i FIRSTVT(T)= * , ( , i LASTVT(T)= * , ) , i FIRSTVT(E)= + , * , ( , i LASTVT(E)= + , * , ) , i ,构造优先关系表 根据规则(1), 由“(E)”知, (=)。 根据规则(2), 由E+T知, + FIRSTVT(T),即 +*, +(, +i 由T*F知, * FIRSTVT(F),即*(, *i 由F(E知, ( FIRSTVT(E),即(+, (*, (,(i,57,根据规则(3)知： 由EE+知,LASTVT(E)+,即+,*+,)+，i+ 由TT*知, LASTVT(T)

31、*，即*，)*，i* 由FE)知,LASTVT(E),即+)，*)，)，i) 由#E#知, #=#；#, 即+#,*#,)#,i#,故算术表达式文法的优先关系表如下:,58,构造优先表：练习(1),文法GS为算符优先文法, 求优先关系矩阵。 SSaF|F F FbP|P P c|d,解：每个非终结符的FIRSTVT集合 FIRSTVT(S) = a, b, c, d FIRSTVT(F) = b, c, d FIRSTVT(P) = c , d 每个非终结符的LASTVT集合 LASTVT(S)= a, b, c, d LASTVT(F) = b, c, d LASTVT(P) = c, d

32、,59,因为SSaF 则 LASTVT(S) a 且aa, ba, ca, da; ab 且bb, c b, d b; b#, 即a#,b#,c#,d# 优先关系表：,60,P133 3（1） （2）,61,规范归约 严格按照句柄进行归约，终结符和非终结符一起考虑，只要栈顶形成句柄，不管句柄内是否包含终结符都要进行归约。 算符优先分析 在算符优先分析中，仅研究终结符之间的优先关系，而不考虑非终结符之间的优先关系，但句柄是由终结符和非终结符一起构成的，所以算符优先分析相对来说是非规范的分析。,5.2.2 算符优先分析算法,62,5.2.2 算符优先分析算法,由于算符优先分析法仅在终结符之间定义了

33、优先关系而未对非终结符定义优先关系，因此算符优先分析法不是用句柄而是用最左素短语来刻画“可归约串” 。 先定义算符优先文法句型的“最左素短语”，用来刻画算符优先分析法的“可归约串” 。,63,5.2.2 算符优先分析算法,素短语 是指这样的一个短语， 它至少含有一个终结符， 并且除它自身外，不再含有更小的素短语。 最左素短语，是指处于句型最左边的那个素短语。 例5-15：考虑非二义的表达式文法G(E)： E E+T|T T T*F|F F (E)|i 句型T+T*F+i#的素短语为什么？ EE+TE+T+TT+T+TT+T*F+TT+T*F+FT+T*F+i 素短语有: T*F，i,64,寻找

34、最左素短语,算符优先文法句型的一般形式： #N1a1N2a2Nnan Nn+1# (5.4) 括在两个#号之间的部分，其中每个ai都是终结符， Ni是可有可无的非终结符。 一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串： # NjajNiaiNi+1 # aj-1ai+1 则， NjajNiaiNi+1一定能归约为某非终结符。,aj-1,ai+1,=,65,寻找最左素短语,寻找句型的最左素短语的过程：从左到右扫描句型的各个符号，扫描过程中依次查看两相继终结符号之间的优先关系，直到找到满足ai ai+1的终结符号ai 为止，记下ai 的位置。再从ai 开始向左扫描，直到找到满足

35、关系aj-1 aj的终结符号aj 为止，此时形如NjajNiaiNi+1的子串就是最左素短语。,i1 *( i2 + i3) # # * + ) # i1，i2，i3是素短语；i1是最左素短语。,66,例：P90.(5.3)文法,EE+T|T TT*F|F FPF|P P(E)|i 求句型 T+T*F+i 的最左素短语:,练习: 文法EE+E|E*E|(E)|i 求句型i+E*i+i的最左素短语。, # + E* i+ # i是最左素短语。, # +i# T*F是最左素短语。,67,求最左素短语及归约：例,P90.(5.3)文法 表5.1的优先表 句型 算符优先关系 最左素短语 归约用规则 #

36、T+T*F+i# #+ T*F TT*F #T+N+i# #+ T+N EE+T #N+i# #+ i Pi #N+N# # N+N EE+T #N#,在查找最左素短语归约的过程中, 全然没有用到非终结符, 因此对归约得到的非终结符可以任意取名(如用N), 只要该非终结符的产生式右部符号串与最左素短语的符号一一对应(非终对非终, 终对终)即可。,68,算符优先分析算法(参见P93.),根据最左素短语的定义, 可以构造算符优先分析算法, 设a=栈顶终结符号, b=当前输入符号 if (ab) or (a b) then begin /* 移进* / 把b推入栈中； 使ip前进到下一个符号； en

37、d if ab then /* 归约* / repeat 从栈中弹出符号 until 栈顶终结符号最近弹出的终结符号 else error,例: i+i*i 的分析过程,# i+i*i# 初始 #i +i*i# #+, #*, +#, *#, +#, # +, 归约NN+N,符号栈 输入串 分析动作 .,70,算符分析算法小结,非终结符对规约没有影响，非终结符并不进栈; 算符优先分析并不等价于规范规约，由于算符分析未对非终结符定义优先关系，也就无法发现单个非终结符构成的可规约串: 显然算符优先分析要比规范规约快的多，因为它跳过了所有单个非终结符对应的规约步骤 算符优先分析法是一种使用广泛、行之

38、有效的方法，常常用于分析各类表达式。 缺点在于有些文法不满足算符优先文法，必须先改写，有些甚至无法改写。若终结符数目多，优先表可能会占有太多空间。,71,5.2.3 优先函数,为了节约存储空间和便于执行比较运算, 在实际实现算符优先分析算法时，一般不用优先表而是用两个优先函数f 和g。 把每个终结符号与两个自然数f()和g() 相对应，使得 若1 2 则 f(1) g(2) f称为入栈优先函数，g称为比较优先函数。 可以由优先表构造优先函数。,72,1. aVT#, 建立两个结点fa和ga; 2. a，b VT # ， 若a = b，则从fa 至 gb 画一条箭弧； 若a = b，则从gb 至 fa 画一条箭弧; 3. 对每个结点赋予一个数, 此数等于从该结点出发沿着箭弧所能到达的结点