ppt编译原理5章555

《ppt编译原理5章555》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第五章语法分析-自下而上分析自底向上分析方法是从输入符号串开始，查找当前句柄，并用产生式将它归约成相应的非终结符号，最后归约为识别符号的一种分析方法。(1)对输入符号串的扫描，采用自左向右的顺序；(2)分析过程是自下而上进行的(对语法树来说从末端结点开始，最后归约到根结点)；(3)每次归约是对最左简单短语(句柄)进行的；(4)算法的关键是确定最左简单短语；注意以下几点：重点掌握：(1)素短语、最左素短语、算符文法、算符优先文法等概念及判断法；(2)优先关系和优先函数的概念及判断方法。例：设有

2、文法G:SaAcBeAbAAbBd输入串:abbcdeSaAcBeAbbd其推导与归约过程为（示范最左/右推导与归约）自下而上分析采用最左归约即规范归约。5.1自底向上分析的一般过程一、一般过程：一般的自底向上分析法，也称为“移进—归约”法，其一般过程为:(1)设置一个存放符号的栈称为符号栈，用于记录分析的过程和确定下一步的动作。(2)把输入符号按扫描顺序逐个移进栈里(符号栈)，当栈顶的符号组成的符号串形成一个句柄时(正好是某条产生式的右部)，就进行归约。即把该符号串用与它对应的产生式左

3、部的非终结符号代替，仍然置于栈顶。(3)接着检查新栈顶，若形成新的句柄，再进行归约，若没有形成新句柄，则从符号串中移进新的符号。如此重复，直到整个输入符号串处理完毕为止。(4)若最终栈底为识别符号，则表明所分析的输入串合法，报告分析成功；否则是不合法的符号串，报告出错信息。一、举例：设有文法G:SaAcBeAbAAbBd输入串:abbcde步骤符号栈内容输入符号串内容所做动作1#abbcde#“#”移进2#abbcde#a进栈—移进3#abbcde#b进栈—移进4#aAbcde#用Ab

4、归约5#aAbcde#b进栈—移进6#aAcde#归约(AAb)7#aAcde#c进栈—移进8#aAcde#d进栈—移进9#aAcBe#归约(Bd)10#aAcBe#e进栈—移进11#S#归约12接受输入串，报告成功！输入仍用#做为左右分界符，即#abbcde#，一步步归约当前句柄，归约目标为#S#总结以上过程可以发现：(1)在此算法中所归约的短语都是最左简单短语，即为规范归约。(2)并没有彻底解决句柄的识别问题。5#aAbcde#在上例中当进行完步骤5后，符号栈和剩余输入符号串的内容为：即

5、输入符号串已经归约为：#aAbcde#，根据上述算法，下一步Ab和b都可以归约(它们都在符号栈的栈顶且有产生式AAb和Ab)。假若判b为句柄，则可把b归约为A，即符号串归约为：#aAAcde#。那么，后面的工作无论怎样做，都无法归约成功。以上问题我们从语法树角度看：最初输入符号串对应的语法树为：SaAcBeAbbd当前句柄进行一次归约后语法树为：此时，Ab和d为句型aAbcde的简单短语，Ab为句柄，所以不能归约b。可见，算法并没有提供识别真正句柄的方法。所以，如何找到当前句型的句柄，是自底

6、向上分析方法的关键。P85-88复习短语、句柄、规范归约等概念。5.2算符优先分析法一、方法概述：算符优先分析法是自底向上分析方法中的一种，虽然它不是规范归约，但它具有分析速度快，特别适合表达式分析的特点，因而得到普遍应用。在算术表达式的运算过程中，为了确保计算过程和结果的唯一性，规定了四则运算法则，实际上就是规定了运算之间的优先顺序，如：先乘除后加减；同级运算从左向右；有括号先做括号内的运算；一目运算减(负号)的优先级高于加减低于乘除。所谓算符优先分析法就是仿照上述算术四则运算的运算过程，而设

7、计的一种语法分析方法。它首先要规定运算符之间的优先关系，然后利用这种关系确定句型的“句柄”，并进行归约。例如：有文法G[E]：EE+E

8、E-E

9、E*E

10、E/E

11、(E)

12、i并有输入串i+i-i*(i+i)这个文法是一个二义性文法，但若采用了四则运算法则，归约过程就唯一了。1i+i-i*(i+i)2E+i-i*(i+i)3E+E-i*(i+i)4E-i*(i+i)5E-E*(i+i)6E-E*(E+i)7E-E*(E+E)8E-E*(E)9E-E*E10E-E11E相邻的终结符号的优先关系，决定了

13、归约顺序，解决了句柄和二义性问题。二、直观的算符优先分析法：实际上，在真正的算符优先分析方法中，需定义任意两个相继出现的终结符号a和b之间的优先关系(a与b之间可有一个非终结符)，一旦确定了这种优先关系，就可以用它来确定“句柄”进行归约。1.优先关系，两个相继出现的终结符之间的优先关系有三种：a的优先级高于b记为:>.baa的优先级等于b记为:.abab<.a的优先级低于b记为:注意：与数学中的<、=、>含义不同，如：若有：ab<.，不一定有：>.ab但>.-+<+-.同样：，不一定有：.ab.