自底向上优先分析法

《自底向上优先分析法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章自底向上优先分析法16.1概述对待分析的符号串，自左向右逐个扫描，输入符号栈，一旦栈顶符号串形成某个句型的句柄或可归约串（对应于某产生式的右部），就用该产生式的左部非终结符代替相应右部的文法符号，即归约成识别符号。在分析过程中，每次归约的都是最左边的简单短语（或其它短语）。从语法树的角度，以输入符号为树的末端结点，试图向根结点方向往上构造语法树。2讨论前提和自顶向下技术同样，不考虑符号的具体构成方式。识别过程是从左到右，自底向上进行的。一般都采用规范归约：每一步都是对句柄进行归约（特例除外）。

2、3基本方法采用移入-归约方法。使用一个栈来存放归约得到的符号。在分析的过程中，识别程序不断地移入符号。移入的符号暂时存放在一个栈中。一旦在已经移入的（和归约得到的）符号串中包含了一个句柄时，将这个句柄归约成为相应的非终结符号。参看课本P102例6.14基本方法（续）归约中的动作有4类移入：读入一个符号并把它归约入栈。归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。接受：当栈中的符号仅有#和识别符号的时候，输入符号也到达结尾的时候，执行接受动作。错误处理：当识别程序发现输入符号串不

3、是句子时，即出错，调用错误处理模块。5例子i*i+ii*i+iiE::=iE*i+iE*i+iE*i+iE*i+iE*i+iE*i+iiE::=iE*E+iE*E+iE*EE::=E*EE+iE+iE+iE+iiE::=iE+EE+EE+EE::=E+EE文法GE[E]:E::=E+E

4、E*E

5、(E)输入符号串：i*i+i已处理未处理句型句柄规则不用此页6例子的解释当栈中的符号的栈顶部分还不能形成句柄时，进行移入操作。一旦发现栈顶部分形成了句柄的时候，对该句柄进行归约。将句柄出栈，然后将归约得到的非

6、终结符号压栈。如果输入是句子，则栈中的符号（从底到上）和未处理的符号组成句型。在例子中，发现句柄和归约是人为干预的结果。所以移入-归约不是实际可运行的技术，而是技术的模板。不用此页7基本问题如何找出进行直接归约的简单短语？即如何知道栈顶符号串已形成了句柄？将找到的简单短语归约到哪个非终结符号？即如何选取适当的产生式进行归约?86.2两种优先分析法简单优先分析法：求出该文法所有符号（终结符和非终结符）之间的优先关系，按照这种关系确定归约过程中的句柄。规范归约。分析准确规范，但效率低，不实用。算符优先分

7、析法：规定算符之间的优先关系，即只考虑终结符之间的优先关系，而不考虑非终结符的优先关系。不是规范归约。分析速度快，适用于表达式的分析。基本思想9简单优先分析法思路：每次察看句型中相邻的两个符号。通过两个符号的关系判定出前一个符号是句柄的尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。S0Sj-1SjSj+1Sj+2Si-1SiSi+1SnU10优先关系和书上的写法不一样。等同：Si〓Sj先于：Si►Sj后于：Si◄Sj注意：〓，►和◄不同于=，>和<。由Si►Sj不能导出Sj◄Si。11

8、简单优先分析技术(思路续）我们要通过两个相邻符号SiSi+1之间的关系来找到句柄：SiSi+1在句柄内：必然有规则U→SiSi+1Si在句柄内部，但是Si+1在句柄之后：必然有规则U→Si，且存在规范句型USi+1。如果Si+1在句柄内，而Si在句柄外，那么必然存在规范句型SiU，且U→Si+1。12优先关系的定义Sj=Si：当且仅当G中有规则U→SjSiSj◄Si：当且仅当U→SjV，且+V==>Si；Sj►Si：当且仅当U→VW，其中V和W分别满足+V==>Sj*

9、W==>Si且Si为终结符号。13优先关系的例子文法：S→bAbA→(B

10、aB→Aa)语言：{bab,b(aa)b,b((aa)a)b,}可以从语法树里面导出部分优先关系。bAbaSb◄aa►bbAbS(Bb◄((〓BB►b14优先矩阵可以将优先关系填写到一个矩阵，得到优先矩阵。(将矩阵作为关系的表示形式）SABab()SA==B►►a►►(◄=◄◄b=◄◄)►►=15#b((aa)a)b#◄◄◄◄►句柄:a归约为A#b((Aa)a)b#◄◄◄◄==►句柄:Aa)归约为B#b((Ba)b#◄◄◄

11、=►句柄:(B归约为A16识别过程(例子续)#b(Bb#◄◄=►句柄:(B归约为A#b(Aa)b#◄◄◄==►句柄:Aa)归约为B#b(Aa)b#◄◄◄==►句柄:Aa)归约为B#bAb#◄==►句柄:bAb归约为S#b(Bb#◄◄=►句柄:(B归约为A17优先关系的构造根据优先关系的构造性的定义（定义6.1），我们立刻可以得到构造算法。(1)=的构造：直接对每个规则右部处理，对所有右部X1X2Xn，都有Xi=Xi+1。SjSi=当且仅当G中有规则U→SjSi1