编译原理_05自底向上的语法分析方法.ppt

《编译原理_05自底向上的语法分析方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章自底向上优先分析法1主要内容6.1自底向上优先分析概述6.3算符优先分析法2课题：自底向上分析方法、算符优先文法目的要求：1.理解自底向上的语法分析方法的基本思想；2.掌握算符文法、算符优先文法的定义和性质教学重点：1.优先分析法的基本思想和术语；2.算符文法、算符优先文法的定义和性质教学难点：算符优先关系的定义教学课时：2教学方法：多媒体教学教学内容和步骤：（如下）第十二讲3自底向上分析方法，也称移进归约分析法实现思想（是推导的逆过程）：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，

2、一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，称为归约。重复这一过程，直到归约到栈中只剩下文法的开始符号时，则分析成功。自底向上分析方法的基本思想4例1：文法:SaAcBeAbAAbBd输入串abbcde#分析最右推导：SaAcBeaAcdeaAbcdeabbcde规约分析过程如下：5步骤符号栈输入符号串动作1#abbcde#移进2#abbcde#移进3#abbcde#归约A→b4#aAbcde#移进5#aAbcde#归约A→Ab6#aAcde#移进7#aAcde#移

3、进8#aAcde#归约B→b9#aAcBe#移进10#aAcBe#规约S→aAcBe11#S#接受6上述的每一步规约可以构造一颗语法树：AbBdAAbbSAbbaceBdA7问题的提出：①在构造语法树的过程中，何时规约？当句柄出现在栈顶符号串中就可以规约。②如何知道在栈顶符号串中已经形成句柄？通过自底向上的分析算法来解释（优先关系）8优先分析法又可分简单优先分析法和算符优先分析法。①简单优先分析法（规范归约）－对文法按一定原则求出所有文法符号间的优先关系；②算法优先分析法（不规范归约）－规定算符之间的优先关系）6.1自底向上

4、优先分析法概述96.3算符优先分析法算符优先优先分析法只规定算符（终结符）之间的优先关系。在归约过程中只要找到句柄就归约，不必考虑归约到哪个非终结符，因此不是规范归约。特点：速度快，特别适合于表达式的分析通过算符之间的优先关系来确定句柄10先看一个例题：例.已知文法G[E]：E→E+EE→E*EE→i输入串i+i*i，归约过程如下11步骤符号栈输入符号串优先关系1）#i+i*i##+规约3）#E+i*i##<+移进4）#E+i*i#+*规约6）#E+E*i#

5、+<*移进7）#E+E*i#*#规约9）#E+E*E#+<*>#规约10）#E+E##<+>#规约11）#E#接受动作12分析可知：若只从移进—归约的角度来考虑，在第6步时栈顶已出现了句柄E+E，可以进行归约了，但是明显是错误的，因为这样就不符合算术运算规律。所以对于表达式，我们可以人为地规定其算符的优先顺序，即给出优先级别和同一级别的结合性。13算符文法定义：设有一文法G，如果G中没有形如A→…BC…的产生式，其中B和C为非终结符，则称G为算符文法(或称OG文法)。即任何一个产生式中都不包

6、含两个非终结符相邻的情况，就是算符文法。14性质1：在算符文法中任何句型都不包含两个相邻的非终结符。性质2：如果Ab或（bA）出现在算符文法的句型中，其中AVN，bVT，则中任何含b的短语必含有A。（含b的短语必含A，含A的短语不一定含b）15算符优先关系的定义：设G是一个算符文法，a和b是任意两个终结符，A，B，C是非终结符，算符优先关系如下：(1)a=b当且仅当G中含有形如A→…ab…或A→…aBb…的产生式;(2)ab当且仅当G中含

7、有形如A→…Bb…的产生式，且B…a或B…aC。＋＋＋＋16算符优先文法的定义：设有一不含产生式的算符文法G，如果对任意两个终结符a，b之间至多只有=，<和>三种关系的一种成立，则称G是一个算符优先文法(也称OPG文法)。即ab，ab，ab只有一种成立，但允许ab，ba同时存在。17例：已知表达式文法G[E]：E→E+E

8、E*E

9、(E)

10、i证明G[E]不是OPG文法。证明如下：因为：E→E+E，EE*E则有+<*又因为：E→E*E,EE+E则有+>*所以不是算符优先文法。＋＋18自底向上分析方法，也称移进归约分析法

11、，是推导的逆过程。算法优先分析法（不规范归约）－规定算符之间的优先关系）文法符号之间的优先关系有三种：大于、小于和等于。算符优先文法(也称OPG文法)，它是一个算符文法，不含产生式，且对任意两个终结符a，b之间至多只有=，<和>三种关系的一种成立。教学总结19教材P122练习:2(1)，