编译原理-第七章.

第七章LR分析法7.1LR分析概述7.2LR（0）分析7.3SLR（1）分析7.4LR（1）分析7.5LALR（1）分析7.6二义性文法在LR分析中的应用3复习：自底向上分析思想从输入串出发，反复利用产生式进行归约，如果最后能得到文法的开始符号，则输入串是句子，否则输入串有语法错误核心寻找句型中的当前归约对象——“句柄”进行归约,用不同的方法寻找句柄，就可获得不同的分析方法41.优先法----ch6算符优先分析•根据归约的先后次序为句型中相邻的文法符号规定优先关系–句柄内相邻符号同时归约，是同优先级的–句柄两个端点符号的优先级要高于句柄外与之相邻的符号的优先级，句柄内相邻符号具有相同的优先级•a1…ai-1ai═ai+1═…═aj-1═ajaj+1…an52.状态法---ch7LR分析法•根据句柄的形成过程建立状态–用状态来描述不同时刻句柄是否形成–因为句柄是产生式的右部，可用产生式来表示句柄的不同识别状态•例如：S→bBB可分解为如下识别状态–S→.bBB移进b–S→b.BB等待归约出B–S→bB.B等待归约出B–S→bBB.归约LR分析法是1965年由Knuth提出的一种自底向上分析方法，它的适用范围很广，很受计算机理论界的重视。自底向上分析法的关键问题是在分析过程中如何确定句柄。LR分析法能根据当前分析栈中的符号串（通常以状态表示）和向右顺序查看输入串的k个（k≥0）符号可唯一确定分析器的动作是移进还是归约和用哪个产生式归约，能唯一地确定句柄。LR（K）表示“从左至右，每步向前（右）查看K个输入符号”。K=0表示不需要向右查看输入符号LR分析法严格执行最左归约，是一种规范归约，这一点与算符优先分析法不同。LR分析法的优点：①对文法限制少，适用范围广。②分析速度快③能准确及时地报错缺点：①构造分析器的工作量较大②K值愈大，实现愈困难本章主要介绍LR分析的基本思想，及当K≤1时，LR分析器的基本构造原理和方法。着重介绍LR（0）、SLR（1）、LALR（1）、LR（1）四种分析器的构造方法。7.1LR分析概述一LR分析器的组成一个LR分析器由3个部分组成：(1)总控程序：也称驱动程序，所有LR分析器的总控程序都是相同的。(2)分析表或分析函数:不同的文法分析表不同；同一个文法采用的LR分析器不同时，分析表也不同。分析表可分为动作表（ACTION）和状态转换表（GOTO）两部分，它们都可用二维数组表示。(3)分析栈：包括文法符号栈和状态栈二LR分析器工作过程LR分析器的动作由栈顶状态和当前输入符号决定。SP输出输入串×××…#总控程序ACTION表GOTO表SnXn┇┇S1X1S0X0•SP：栈指针•S[i]：状态栈•X[i]：文法符号栈•ACTION表和GOTO表分别为动作表和状态转换表。GOTO[Si，X]=Sj表示栈顶状态为Si遇到当前文法符号为X时应转向状态Sj。ACTION[Si，a]规定了栈顶状态为Si时遇到输入符号a应执行的动作。动作有4种：(1)移进：把a移入文法符号栈，把Sj=GOTO[Si，a]移入到状态栈。其中i，j表示状态号。(2)归约：当栈顶形成句柄为β时，把β归约为相应的非终结符A（A→β为文法中的产生式）。设β的长度为r（即|β|=r），则从状态栈和文法符号栈中自顶向下去掉r个符号（即栈指针SP-r），把A移入文法符号栈，Sj=GOTO[Si，A]移进状态栈，Si为修改指针后的栈顶状态。(3)接受acc：文法符号栈中只有开始符S′，输入串只有#，则为分析成功。(4)报错：当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入串不是该文法能接受的句子。LR分析器的关键部分是分析表的构造，下面将针对每种不同的LR分析器详细介绍其构造思想及方法。7.2LR（0）分析LR（0）分析表构造的思想和方法是构造其它LR分析表的基础。先引进一些概念和术语：•拓广文法：对原文法G[S]增加一产生式S′→S，S′只在左部出现。对文法进行拓广的目的：为了对某些右部含有开始符的文法，在归约过程中能分清是否已归约到文法的最初开始符，还是在文法右部出现的开始符。拓广文法的开始符S′只在左部出现，这样确保不会混淆。•可归前缀：如果有S′=〉，为终结符串（或空），含有句柄，且句柄在的后端，称为可归前缀。*R•活前缀：把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为活前缀。定义7.1若S′=〉αAω=〉αβω是文法G中的一个规范推导（β为句柄），如果符号串γ是αβ的前缀，则称γ是G的一个活前缀，γ的右端不超过句柄的末端。*RR例如：G[S]：（1）S→aAcBe（2）A→b（3）A→Ab（4）B→daAbcde是规范句型。因为:S=〉aAcBe=〉aAcde=〉aAbcde从左至右，规范句型aAbcde的活前缀有ε、a、aA、aAb，而aAbc不是活前缀，因为它包含句柄后面的符号c。由以上分析我们很容易理解，在LR分析过程中，实际上是把αβ的前缀列出放在符号栈中，一旦在栈中出现αβ（可归前缀），即句柄已经形成，则用产生式A→β进行归约。（参考P125-表7.2）7.2.2识别活前缀的有限自动机（略）7.2.3活前缀及其可归前缀的一般计算方法（略）7.2.4LR（0）项目集规范族的构造（1）LR（0）项目在文法G中每个产生式的右部适当位置添加一个圆点构成项目。例如：S→aAc对应有4个项目:（右部长度3加1）[0]S→aAc[1]S→aAc[2]S→aAc[3]S→aAc一个产生式可对应的项目数为它的右部符号串长度加1注意：A→ε仅有项目A→每个项目的含义与圆点的位置有关，概括地说，圆点的左部表示分析过程的某时刻用该产生式归约时句柄已识别的部分，圆点的右部表示待识别部分。项目S→aAc：希望用S的右部归约，当前输入串中符号应为a项目S→aAc：已与第一个符号a匹配，需分析A的右部项目S→aAc：A的右部已分析完归约成A，希望输入串中符号为c项目S→aAc：S的右部分析完毕，句柄已形成，可以进行归约。根据圆点所在位置和圆点后是终结符还是非终结符，把项目分为以下几种：1.移进项目：圆点后为终结符的项目，对应状态为移进状态。形如A→αaβ，a∈VT2.待约项目：圆点后为非终结符的项目，如A→αBβ，B∈VN。表示所对应的状态等待着分析完非终结符B所能推出的串归约成B，才能继续分析A的右部。3.归约项目：圆点在最右部的项目，如A→α，表明一个产生式的右部已分析完，句柄已形成，可以归约。4.接受项目：形如S′→α，S′→α为拓广文法，S′为左部的产生式只有一个，它是特殊的归约项目，对应状态为接受状态。（3）LR（0）项目集规范族的构造对于构成识别一个文法活前缀的DFA项目集的全体称为这个文法的LR（0）项目集规范族。按（2）中方法，列出拓广文法的所有项目，构造NFA再确定化，这样做确定化的工作量较大，可以用闭包函数求DFA项目集。（2）构造识别活前缀的NFA（了解）•定义和构造项目集I的闭包函数CLOSURE（I）a）I的项目均在CLOSURE（I）中b）若A→αBβ属于CLOSURE（I），则每一形如B→γ的项目也属于CLOSURE（I）c)重复b）直到CLOSURE（I）不再扩大为止•定义转换函数GO（I，X）如下：GO（I，X）=CLOSURE（J）其中：I为包含某一项目的状态，X∈VNVTJ={任何形如A→αXβ的项目|A→αXβ属于I}圆点不在产生式右部最左边的项目称为核（拓广文法S′→S除外）GO（I，X）转换函数得到的J为转向后状态所含项目集的核。•使用CLOSURE和GO（I，X）构造文法G′的LR（0）项目集规范族：a）置项目S′→S为初态集的核，求CLOSURE（{S′→S}）得到初态的项目集b）对初态集或其它的项目集应用转换函数GO（I，X）=CLOSURE（J）求出新状态J的项目集。c)重复b）直到不出现新的项目集为止。例如：G[S]：S′→SS→aAcA→AbbA→bcAbbbaSI7I6I5I4I3I1I2I0S′→SS→aAcS′→SS→aAcA→AbbA→bA→bS→aAcA→AbbA→AbbS→aAcA→AbbLR（0）项目集规范族的项目分为四种：移进项目、归约项目、待约项目和接受项目。一个项目集中可能包含以上四种不同的项目，但是一个项目集中不能有下列情况存在：a)移进项目和归约项目同时存在形如称移进—归约冲突。A→αaβB→γb)归约和归约项目同时存在形如称归约—归约冲突。A→βB→γLR（0）文法：一个文法的LR（0）项目集规范族不存在移进—归约或归约—归约冲突时，这个文法为LR（0）文法。(4)LR（0）分析表的构造是LR（0）分析器的重要组成部分，是总控程序分析动作的依据。LR（0）分析表可用一个二维数组表示，行标为状态号，列标为文法符号和#。分析表由两部分组成：动作表ACTION：表示当前状态下面临输入符应做的动作。转换表GOTO：表示当前状态下面临文法符号应转向的下一个状态。构造一个文法的LR（0）分析表，首先构造其识别活前缀的自动机DFA，利用DFA的项目集和状态转换函数构造它的LR（0）分析表。LR（0）分析表的构造算法如下：假设已构造出LR（0）项目集规范族如下：C={I0，I1，…，In}，其中Ik为项目集的名字，k为状态名，令包含S′→S项目的集合Ik的下标为分析器的初始状态，那么分析表的ACTION表和GOTO表构造步骤为：a)若项目A→αaβ属于Ik且转换函数GO（Ik，a）=Ij，当a∈VT时，则置ACTION[k，a]为Sj，其动作含义为将a移进符号栈，j进入状态栈。b)若项目A→α属于Ik，则对任意a∈VT和#，置ACTION[k，a]和ACTION[k，#]为rj。j为A→α产生式序号。rj动作的含义是把当前文法符号栈顶的符号串α归约为A，栈顶指针向下移动|α|的长度，非终结符A变为当前面临的符号。c)若GO（Ik，A）=Ij，则置GOTO[k，A]为j，其中A∈VN，表示当前状态为k时，遇文法符号A时应转向j，因此A移入文法符号栈，j移入状态栈。d)若项目S′→S属于Ik，则置ACTION[k，#]为acc，表示接受e)凡不能用上述方法填入的分析表的元素，均应填上“报错标志”。为清晰起见，表中用空白表示出错。例：S→vI:T[1]拓广文法S′→S[0]I→I,i[2]I→i[3]T→r[4]构造LR（0）分析表先构造识别活前缀的DFA（即LR（0）项目集规范族）I９I８Ti,I:riｖSI7I6I5I3I４I2I0S′→SS→vI:TS′→SS→vI:TI→I,iI→iI→iS→vI:TI→I,iS→vI:TT→rI→I,iT→rI→I,iS→vI:TI1然后构造LR（0）分析表，如下所示：状态ACTIONGOTOvi，：r#SIT0S211acc2S433S6S54r3r3r3r3r3r35S986S77r2r2r2r2r2r28r1r1r1r1r1r19r4r4r4r4r4r4练习：构造下列文法的LR（0）分析表S→aAcA→bB|baB→dB|e(5)LR（0）分析器的工作过程1)若ACTION[S，a]=Sj，a∈VT，则a移入符号栈，j移入状态栈。2)若ACTION[S，a]=rj，a∈VT或#，则用第j个产生式归约，并将两个栈的指针减去k，其中k为第j个产生式右部的符号串的长度，这时当前面临符号为第j个产生式左部的非终结符。3)若ACTION[S，a]=acc，a=‘#’，则为接受，表示分析成功。4)若GOTO[S，A]=j，A∈VN，表明前一动作是用关于A的产生式归约，当前面临非终结符A应移入符号栈，j移入状态栈。5)若ACTION[S，a]=空白，则转向出错处理对于前例文法，句子vi，i：r的LR（0）分析过程。步骤状态栈符号栈输入串ACTIONGOTO10#vi，i：r#S