编译原理课件Chapter6.ppt

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

1、第6章自底向上优先分析法1从推导的角度，从输入符号出发，试图把它规约成识别符号。每一步都寻找特定的某个类型的短语（一般是简单短语）进行归约。在分析过程中，每次归约的都是最左边的简单短语（或其它短语）。从语法树的角度，以输入符号为树的叶子结点，试图向根结点方向往上构造语法树。6.1概述2基本问题如何找出进行直接归约的简单短语？将找到的简单短语归约到哪个非终结符号？3自底向上分析过程的实现基本都采用移入-归约方法。使用一个栈来存放归约得到的符号。在分析的过程中，识别程序不断地移入符号。移入的符号暂时存放在一个栈中。一旦在已经移入的（和归约得到的）符号串中包含了

2、一个句柄时，将这个句柄归约成为相应的非终结符号。4自底向上分析过程的实现（续）特点：能力强，构造复杂产生式表控制程序输出符号串#…#栈分析表5自底向上分析过程的实现（续）工作过程：把输入符号串按描述顺序一一地移进符号栈（一次移一个），检查栈中符号，当在栈顶的若干符号形成当前句型的句柄时，就根据规则进行规约，将句柄从符号栈中弹出，并将相应的非终结符号压入栈内（即规则的左部符号），然后再检查栈内符号串是否形成新的句柄，若有就再进行规约，否则移进符号。分析一直进行到读到输入串的终止符为止。最后，若栈中仅含有终止符和开始符号，则表示分析成功，否则失败。6自底向上分

3、析过程的实现（续）归约中的动作有4类移入：读入一个符号并把它归约入栈。归约：当栈中的部分形成一个句柄（栈顶的符号序列）时，对句柄进行归约。接受：当栈中的符号仅有#和识别符号的时候，输入符号也到达结尾的时候，执行接受动作。当识别程序觉察出错误的时候，表明输入符号串不是句子。进行错误处理。7例子＃i*i+i#i*i+i移进＃i*i+i#i*i+iiE::=i＃E*i+i#E*i+i移进＃E*i+i#E*i+i移进＃E*i+i#E*i+iiE::=i＃E*E+i#E*E+iE*EE::=E*E＃E+i#E+i移进＃E+i#E+i移进＃E+i#E+iiE::=i＃

4、E+E#E+EE+EE::=E+E＃E#接受文法GE[E]:E::=E+E

5、E*E

6、(E)

7、i输入符号串：i*i+i符号栈输入符号串句型句柄动作8例子的解释一旦发现栈顶部分形成了句柄的时候，对该句柄进行归约。将句柄出栈，然后将归约得到的非终结符号压栈。当栈中的符号的栈顶部分还不能形成句柄时，进行移入操作。如果输入是句子，则栈中的符号（从底到上）和未处理的符号组成句型。在例子中，发现句柄和归约是人为干预的结果。所以移入-归约不是实际可运行的技术，而是技术的模板。96.2简单优先分析法基本思想：每次察看句型中相邻的两个符号。通过两个符号的关系判定出前一个符号是

8、句柄的尾。然后，反向找出句柄的头。这样我们就找到了一个句柄。S0…Sj-1SjSj+1Sj+2…Si-1SiSi+1…SnU10简单优先分析技术(基本思想续）我们要通过两个相邻符号SiSi+1之间的关系来找到句柄：SiSi+1在句柄内：必然有规则U→…SiSi+1…Si在句柄内部，但是Si+1在句柄之后，必然有规则U→…Si，且存在规范句型…USi+1…。如果Si+1在句柄内，而Si在句柄外，那么必然存在规范句型…SiU…，且有U→Si+1…。11优先关系和书上的写法不一样，凑合用。等同：Si〓Sj先于：Si►Sj后于：Si◄Sj注意：〓，►和◄不同于=，

9、>和<。由Si►Sj不能导出Sj◄Si。12优先关系的定义Sj=Si：当且仅当G中有规则U→…SjSi…Sj◄Si：当且仅当U→…SjV…，且+V==>Si…；Sj►Si：当且仅当U→…VW…，其中V和W分别满足+V==>…Sj*W==>Si…且Si为终结符号。13优先关系的构造根据优先关系的构造性的定义（定义6.1），我们立刻可以得到构造算法。(1)=的构造：直接对每个规则右部处理，对所有右部X1X2…Xn，都有Xi=Xi+1。SjSi=当且仅当G中有规则U→…SjSi…14（2）◄的构造：由定义，Sj◄Si可以得到存在规则U→…SjV…，也就是Sj=V

10、,+HEAD(V)＝{Sk

11、V==>Sk…}＝{Si1,Si2,…,Sin}。SjSi1Si2…Sin◄◄◄15（3）►关系的构造：由定义，Sj►Si表示:存在规则U→…VW…其中V=W+TAIL(V)＝{Sl

12、V==>…Sl}＝{Sj1,Sj2,…,Sjm}。+HEAD(W)＝{Sk

13、W==>Sk…}＝{Si1,Si2,…,Sin}。Sj1Si1Si2…Sin►►►Sj2►►►Sjm►►►16优先矩阵可以将优先关系填写到一个矩阵，得到优先矩阵。(将矩阵作为关系的表示形式）SABab()SA==B►►a►►(◄=◄◄b=◄◄)►►=17=简单优先关系矩阵

14、（表）文法：S→bAbA→(B

15、aB→Aa)HEAD(A)={(a