[理学]第七章 LR分析编译原理.ppt

1 1 L表示从左到右扫描输入串 left-to-right scanning R表示最左规约（即最右推导的逆过程） rightmost derivation in reverse K表示向右查看输入串符号的个数 当K=1时，能满足当前绝大多数高级语言编译程序的需要。 在步骤3中，用A→b归约 在步骤5中，用A→Ab归约 问题：何时移进？何时归约？用哪个产生式归约（如何找当前句柄归约）？ 问题： 对于一个文法，状态集是如何确定的？ LR分析表是如何得到的？ 可归前缀和活前缀在LR分析中的作用 在LR分析过程中，实际上是把活前缀列出放在符号栈中，一旦在栈中出现可归前缀，即句柄已经形成，就用相应的产生式进行归约。 在分析的过程中，只要符号栈中的符号串是一个活前缀，就可保证已被分析过的部分是该文法规范句型的正确部分。 用有限自动机来识别活前缀和可归前缀 有限自动机如何构造？ 一个特例：已经有了可归约前缀如何构造识别活前缀和可归前缀的有限自动机 由文法的产生式构造识别活前缀和可归前缀的有限自动机的方法 构造识别活前缀和可归约前缀的有限自动机的一个例子： 特例：由句子规范推导的逆过程直观地看出它的活前缀和可归前缀 按活前缀和可归前缀构造识别它们的有限自动机 以上示例中构造DFA的方法是通过一个句子的归约过程确定可归前缀，但是： 对于一个复杂的文法，其可归前缀不是如此简单就能计算出来 示例中用一个句子归约过程的所有活前缀和可归前缀构造出的DFA，恰好也是识别整个文法的活前缀和可归前缀的DFA，这仅是一个特殊情况。 对一个上下文无关文法需要求出它的所有活前缀和可归前缀后才能构造其识别该文法活前缀的DFA 推论：若文法G中有产生式B??A?则有： LC(A)?LC(B)·{?} 【证明】因为对任一形为?B?的句型必有规范推导： S’??B? ???A?? 即对任一个?∈LC(B)定有??∈LC(A)，所以 LC(A)?LC(B)·{?} 对任何一个上下文无关文法只要能够构造出它的识别可归前缀的有限自动机，就可以构造其相应的分析表。 用这种方法构造识别可归前缀的有限自动机 从理论的角度讲是比较严格的，但实现起来却很复杂。 【解释】若当前处于A–X?YZ刻划的情况，期望移进 First(Y)中的某些符号，假如有产生式Y–u|w。那么Y–?u和Y–?w这两个项目便是刻划期望移进 First(Y)中的某些符号的情况。 ∵Go[I2,A]={S’→aA.} ∴I4=Closure({S’→aA.}) I4:E→aA． ∵Go[I3 ,B]={E→bB.} ∴I7=Closure({E→bB.}) I7:E→bB． ∵Go[I3 ,c]={E→c.B} ∴ I8=Closure({E→c.B}) I8:E→c.B，B→.cB，B→.d ∵Go[I3 ,d]={B→d.} ∴ I9=Closure({B→d.}) I9:B→d. ∵Go[I5 ,A]={A→cA.} ∴ I10=Closure({A→cA.}) I10:A→cA. ∵Go[I8 ,B]={B→cB. } ∴ I11=Closure({B→cB.}) I11:B→cB. 我们所要构造的识别方法G[S]全部活前缀的DFA为: M=(C,V,GO,I0,C)。其中： 状态集及终态集为项目集规范族C; 字母表为V=VN∪VT∪{S’} 初态为I0; 转换函数为GO; 总结：构造识别文法活前缀DFA的三种方法 一、根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造NFA再确定化为DFA 二、求出文法的所有项目，按一定规则构造识别活前缀的NFA再确定化为DFA 三、使用闭包函数（CLOSURE）和转换函数(GO)构造文法G’的LR(0)的项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的DFA LR分析表 (1)对于每个项目集Ii中形如A→??X?项目,若GO(Ii,X)= Ij,则,若X∈VT,则置ACTION[i,X]=sj,否则(X∈VN),置GOTO[i,X]=j; (2)若归约项目A→??属于Ii,且A→?是P中第j个产生式,则对于?a?VT?{#},置ACTION[i,a]=rj (3)若接受项目S’→S·属于Ii,则置ACTION[i,#]=“acc”; (4)在表中其它未填入信息的栏目中均填“ERR”。 定义：若文法G按上面算法构造出来的分析表不包含多重定义项，则该文法G是LR(0)文法。 1.总控程序：所有LR分析器总控程序相同。 2.分析表： 不同文法有不同的分析表 同一文法采用的LR分析器不同，分析表也不同 分析表分为ACTION表（动作表