哈工大编译原理4-2

《哈工大编译原理4-2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章语法分析14.3自底向上4.3.1自底向上分析中的问题研究一、方法描述自左向右逐个扫描输入串，一边把输入符号移入分析栈，一边检查位于栈顶的一串符号是否与某个产生式的右部相同，如果相同，就把栈顶的这串符号归约为左部的非终结符；不同，则继续移入输入符号，进行判断。上述过程一直重复到输入串结束，栈内恰好为S。计算机学院2辛明影移入归约分析法为输入串构造分析树时从叶节占点（底端）开始，向根节点（顶端）前进。该过程可看成是把输入串w“归约”成文法开始符号的过程如果每一步都能恰当地选择子串，我们就可以得到最右推导的逆过程----最左归约

2、文法4.1：S→aABeA→Ab

3、bB→d规范归约：最左归约规范推导：最右推导计算机学院3辛明影句子abbde的归约过程(最左归约）abbdeAABS对应的最右推导:S=>aABe=>aAde=>aAbde=>abbde①②③④计算机学院4辛明影存在的问题：在第步归约时，②有两种可能：A→Ab和A→b分析栈的情况如图：bAa计算机学院5辛明影abbdeAAB①②③正确地选择归约的符号串很重要现在看看用A→b归约的情况计算机学院6辛明影二、句柄定义4.1短语*+如果S=>αAw=>αβw，则称β为相对于A的、句型αβw的短语。SαA

4、βw裁剪句柄αAw和αβw为最右推导所得的右句型；w只包含终结符计算机学院7辛明影SAABbdea短语：Ab,d,aAbde计算机学院8辛明影定义4.2直接短语若A→β为一产生式，则称β为相对于A的、句型αβw的直接短语句型aAbde所包含的直接短语：Ab、d、定义4.3最左直接短语是句柄句型aAbde所包含的句柄:Ab计算机学院9辛明影在第②步归约中，相对于句型aAbde来说，Ab是句柄，其上一级句型为aAde；而b根本就不是短语，因为不存在上一级句型aAAde计算机学院10辛明影例：证明T/（E-T）*F+i是句型，并指出其所

5、包含的短语、直接短语和句柄E=>E+T=>E+i=>E+F=>T+i=>T*F+i=>T/F*F+i=>T/(E)*F+i=>T/(E-T)*F+iE+TFiTT*FT/F（E）E--T（E-T），T/（E-T），T/（E-T）*F，i,T/（E-T）*F+i短语：E-T，E直接短语:E-T,i句柄：E-T计算机学院11辛明影考虑文法4.1：S→aABeA→AbA→bB→dabbde的最右推导和最左归约如左右句型句柄归约产生式abbdeaAbdeaAdeaABeSbAbdaABeA→bA→AbB→dA→aABeS=>aABe=>a

6、Ade=>abbde=>aAbde计算机学院12辛明影EE+T*FTFid3id2TF句子F+id*id对应的语法树短语：FId2Id3id2*id3id1+id2*id3直接短语：FId2Id3句柄：F计算机学院13辛明影三、用栈实现移进归约分析移入归约分析器使用了一个栈来保存文法符号，初始时，栈和输入串的情形为：栈输入串＄w＄终止时，形成如下格局：栈输入串＄S＄用输入缓冲区来存放待分析的串w,＄为栈底符号和输入结束标记。计算机学院14辛明影考虑文法4.2：E→E+T

7、TT→T*F

8、FF→(E)

9、idid1*id2+id3的分析

10、过程如下：计算机学院15辛明影步骤符号栈输入串动作0＄id1*id2+id3＄prepare1＄id1*id2+id3＄移入2＄F*id2+id3＄归约F→id3＄T*id2+id3＄归约T→F4＄T*id2+id3＄移进5＄T*id2+id3＄移进6＄T*F+id3＄归约F→id7＄T+id3＄归约T→T*F8＄E+id3＄归约E→T9＄E+id3＄移入10＄E+id3＄移入11＄E+F＄归约F→id12＄E+T＄归约T→F13＄E＄归约E→E+T14＄E＄access计算机学院16辛明影移进：把下一个输入符号移进栈移进归约的基

11、本动作：归约：栈顶已形成句柄右端，需向栈内搜索确定句柄的左端，并选择正确的非终结符进行替换接受：分析成功出错：调用错误处理程序计算机学院17辛明影四、句柄的识别解决两个问题：栈顶形成的一定是最左直接短语2、判断句柄的左、右端：优先法状态法1、最左性：计算机学院18辛明影4.3.1算符优先分析一、算符优先文法定义4.4算符文法定义4.5相邻一个文法，如果它的任一产生式的右部都不含两个相邻的非终结符，即不含有形如A→……QR……的产生式，则该文法是算符文法若S=>…ab…或S=>…aQb…,称a,b相邻计算机学院19辛明影②ab:当且

12、仅当存在产生式A→…aT…，且T=>b…，或T=>Rb…，称a后于b归约定义4.6关系①ab:当且仅当存在产生式A→…ab…或A→…aTb…，称a、b同等归约③ab:当且仅当存在产生式A→…Tb…,且T=>…a，或T=>…aR，称a先于b归约④ab