哈工大编译原理4-2.pptVIP

第四章 语法分析 例：文法G（S）： S →（A）|a A→A+S|S 求各非终结符的FIRSTVT和LASTVT 解：FIRSTVT（S）={a,(} FIRSTVT（A）={+,a,(} LASTVT(S)={a,)} LASTVT(A)={+,a,)} 算法4.3 构造算符优先关系的算法 FOR 每条产生式P→X1 X2…… Xn DO FOR i=1 TO n-1 DO BEGIN IF Xi、Xi+1 ∈VT，THEN Xi Xi+1 IF i≦n-2 且Xi、Xi+2∈VT , Xi+1 ∈VN THEN Xi、 Xi+2 IF Xi∈VT而Xi+1 ∈VN THEN FOR a ∈ FIRSTVT(Xi+1 ) DO 置Xi ??a IF Xi∈VN而IF Xi+1 ∈VT THEN FOR a ∈ LASTVT(Xi) DO 置 a ?? Xi+1 END 例：文法G（S）： S →（A）|a A→A+S|S 求算符优先矩阵 解：FIRSTVT（S）={a,(} FIRSTVT（A）={+,a,(} LASTVT(S)={a,)} LASTVT(A)={+,a,)} S →（A） a + ( ) a 　 + 　 ( 　 ) （.Firstvt(A)={+,a,(} ＜ ＜ ＜ ＜ ＜ Lastvt(A)={+,a,)}.) S →（A） = ＞ ＞ ＞ S →（A） (=) A→A+S ＞ ＞ ＞ A→A+S LASTVT(A)={a,+,)}.+ +.FIRSTVT(S)={a,(} 表4.1 文法4.2对应的算符优先矩阵 三、算符优先算法 栈顶形成可归约串的判断方法： 1 ·利用栈顶终结符和当前输入符号之间的优先关系· ，能找到可归约串?的 右端； 2 ·在栈内，利用·关系，可找到可归 约串?的左端； 3 ·将·和·之间的符号串弹出栈，并 将归约后的非终结符压入栈，完成一次归约 算法4.4 算符优先分析算法 *辛明影 * 4.3 自底向上 4.3.1自底向上分析中的问题研究 一、方法描述 自左向右逐个扫描输入串， 一边把输入符 号移入分析栈 ， 一边检查位于栈顶的一串符号是否与某个产生式的右部相同， 如果相同，就把栈顶的这串符号归约为左部的非终结符； 不同，则继续移入输入符号，进行判断。 上述过程一直重复到输入串结束， 栈内恰好为S。 移入归约分析法为输入串构造分析树时从叶节占点（底端）开始，向根节点（顶端）前进。 该过程可看成是把输入串w“归约”成文法开始符号的过程 如果每一步都能恰当地选择子串，我们就可以得到最右推导的逆过程----最左归约 文法4.1： S→aABe A→Ab|b B→d 规范归约：最左归约 规范推导：最右推导 句子abbde的归约过程(最左归约） a b b d e A A B S 对应的最右推导: S=aABe=aAde=aAbde=abbde ① ② ③ ④ 存在的问题： 在第 步归约时， ② 有两种可能： A→Ab 和A→b 分析栈的情况如图： b A