资源描述：
《编译原理及其习题解答（武汉大学出版社）课件chap6》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、中南民族大学计算机科学学院编译原理CompilerPrinciples第六章自底向上优先分析法编译原理CompilerPrinciples第六章自底向上优先分析法自底向上的分析方法，也称移进-归约分析法。它的实现思想是：对输入符号串自左向右进行扫描，并将输入符逐个移入一个后进先出栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，(该句柄对应某产生式的右部)，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为一步归约。重复这一过程直到归约到栈中只剩文法的开始符号时则为分析成功，也就确认输入串是文法的句子。确定的自底向上的分析方法分为两大类：优先分析法和LR分析方法。
2、本章将在介绍自底向上分析思想基础上，着重介绍算符优先分析法。编译原理CompilerPrinciples6.1短语、直接短语、句柄1、短语：令文法G，开始符号为S，xAy是G的句型（即SxAy），如果SxAy且Aα，则称α是句型xαy相对于非终结符A的短语。2、直接短语（简单短语）如短语中有A=>α，则称α是句型相对于规则A→α的直接短语。3、句柄（Handle）一个句型的最左直接短语称为该句型的句柄。（可规约串）编译原理CompilerPrinciples例6.1例：文法G[数]:<数>→<数字串><数字串>→<数字串><数字>
3、<数字><数字>→0
4、1
5、2
6、3
7、4
8、5
9、6
10、
11、7
12、8
13、9<数>=><数字串>=><数字串><数字>=><数字串>1所以，<数字串>1是一个句型。下面结论是否正确？1.1是句型<数字串>1相对于<数字>的短语。2.<数字串>1是句型<数字串>1相对于<数字串>的短语。3.<数字串>是句型<数字串>1相对于<数>的短语。编译原理CompilerPrinciples语法树与短语的关系1.每个句型（句子）都对应有一棵语法树；2.每棵语法树的叶子结点从左到右、从上到下构成一个句型（句子）；3.每棵子树的叶子结点从左到右、从上到下构成一个短语；每棵子树的直接叶子结点从左到右、从上到下构成一个直接短语；最左简单子树的直接叶子结点从左到右
14、、从上到下构成一个句柄。编译原理CompilerPrinciples例6.1<数><数字串><数字串><数字>1编译原理CompilerPrinciples解题方法例2例：文法G[E]:E→T
15、E+TT→F
16、T*FF→(E)
17、i证明i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。证明：EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*i编译原理CompilerPrinciples接上例语法树：EE+TTT*FFFi3i1i2第1层i1+i2*i3—相对于E第2层i1—相对于E;i2*i3—相对于T第3层i1,i2—相对于T;i3—相
18、对于F第4层i1,i2—相对于F(F→i直接短语)第5层∴i+i*i是G的一个句型，其中i1,i2,i3,i2*i3,i1+i2*i3都是句型i1+i2*i3的短语，且i1,i2,i3为直接短语，i1为句柄编译原理CompilerPrinciples分析说明(2)作为“短语”的两个条件是不可缺少的，仅仅有Aβ，未必意味着β就是句型αβδ的一个短语，因为还需要有Sαβδ这个条件。例如：上例中有Ei1+i2，但i1+i2并不是该句型的一个短语，因为不存在从E（开始符号）到E*i3的推导。(1)短语、直接短语、句柄是针对某一句型（Sα）而言的;编译原理CompilerPrincipl
19、es解题方法⒈先证明前提（如证明i+i*i是G的一个句型）⒉给出语法树（注意文法是否是二义性的）如题文法G[E]:E→E+E
20、E*E
21、(E)
22、i所以：证明i+i*i是G的一个句型，并指出这个句型的所有短语、直接短语、句柄。⒊根据每颗语法树得出短语、直接短语、句柄例课本P143例6.3编译原理CompilerPrinciples练习1题目文法G[T]:T→F
23、T*FF→F↑P
24、PP→(T)
25、i证明T*P↑(T*F)是文法G的一个句型，并指出这个句型的所有短语、直接短语、句柄。编译原理CompilerPrinciples练习１解答证明：TT*FT*F↑PT*F↑(T)T*F↑(T*
26、F)T*P↑(T*F)语法树：TT*FF↑PPT()T*F第1层T*P↑(T*F)—相对于T第2层P↑(T*F)—相对于F;第3层P—相对于F;(T*F)—相对于P第4层T*F—相对于T第5层∴T*P↑(T*F)是G的一个句型，其中T*F,P,(T*F),P↑(T*F),T*P↑(T*F)都是该句型的短语，且T*F,P为直接短语，P为句柄编译原理CompilerPrinciples练习2题目设有文法G[S]:S→V1V1→V2
27、V1iV2V2→V3
28、V2+V3V3→)V1*
29、((1)给出(+
