编译原理 第6-1章(清华大学).ppt

1、第6章lr分析程序及其自动构造，6.1自底向上分析和概述LR分析6.2LR(0)分析6.3 LR(1)分析6.4LR(1)分析6.5LALR分析6.6使用歧义语法，具有强大的自底向上分析算法能力，并构造了最常用和最有效的复杂模型移位约简(action)，将输入分为两部分：未消化和半消化，一般控制程序，如果你能找到一个生产公式A-w并且堆栈中的内容是qw(q可能是空的也就是说，你可以反过来使用这个生产公式。例如，如果堆栈中的内容是(int)，我们使用生产公式tint，并将堆栈的内容减少到(TShift:)如果它不能执行减少，并且在未消化的输入中有标记，则将它从输入移动到堆栈。作为上面的例子，假设

2、堆栈的内容是(，在输入中有int int in。我们不能对进行缩减(因为它不符合任何生产公式的右端)。所以我们将输入的第一个符号移动到堆栈中。所以堆栈中的内容是(int，剩余的输入是int) #。reduce的一种特殊情况：堆栈中的所有内容w都被缩减为起始符号s(即应用了sw)，并且没有剩余输入，这意味着整个输入字符串都已被成功分析。进入归约分析，也会有错误的情况，例如，当前的标记不能构成合法句子的一部分，如上面的语法。尝试分析int)时会出现错误。进入简化模型分析过程。STACKREMAININININGINGUPPARASTRACTION 1(int)# shift 2(int)# shi

3、ft 3(int)# reduced :Tint 4(T int)# reduced : ET5(E int)# shift 6(E int)# shift 7(E int)# reduced :Tint 8(E T)# reduced 3: EE T9(E)# shift 10(E)# reduced :T11T # reduced 33366没有E-T(E)#如果使用E-T，则(e-e不是规范句型的可行前缀)(e-e不能匹配任何生产模式的右端(e-e)不是规范句型的前缀(正确句型)，但它不超过句柄移入简化分析堆栈中的内容加上剩余输入以形成规范句型。规范派生词规范句型是规范化的，最右边的派生

4、词是：在派生词 的任何步骤中，其中和是句型，它们是的最右边的非右边的。从规范派生的句型被称为规范句型gs:seee t | TT (e)| int set(e)(e t)(e int)(t int)(int int int int)规范约简假定是g的句子，并被称为序列 n， n-1，0是的规范约简。如果序列满足：(1)n=(2)0是任何j的语法(3)的起始符号，0a=r是的前缀，则r被称为g的活前缀。活前缀已经包含句柄的所有符号，表明生成公式a的右部分已经出现在堆栈2的顶部。活动前缀只包含句柄符号的一部分，表示a12的右半部分子串1出现在堆栈的顶部，预计会看到符号2从输入字符串中推出。3.活动

5、前缀不包含任何句柄符号。此时，期望从A的右侧推出的符号串、R、活动前缀、句柄和LR(0)项分别用于用用点标记的产生式来指示位置，以便描述在该分析过程中已经识别了语法G的每个产生式的右侧符号的多少部分(出现在堆栈的顶部)。A。表征产生式A的右边部分出现在堆叠A1.2的顶部，表征A1.2的右边部分子串1出现在堆叠的顶部。预计将看到从输入字符串的 2推导出的符号A 。表示堆栈顶部没有句柄的任何符号。此时，预计从A 的右边部分推导出的符号串对于A 的LR(0)项只有A项，因此构造了闭包闭包闭包、GO函数、DFA函数、标识活前缀的LR(0)项集/*I是项目集*/ J:=I；repeatforJ中的每个项

6、目a.b和生产公式b，如果b .不在j中，请将b .添加到j，直到j returnJ中没有项目为止。GO(I，x)=闭包(J)；其中，I:项集，x:语法符号，J=任何形如ax | a.xi的项集，lr (0)项集的闭包闭包闭包，如果当前情况以a-XYZ为特征，则预计会移入First(Y)中的一些符号，如果有生产公式Y-u|w，则这两个项Y-u和y-w是描述预计会移入First(Y)中的一些符号的情况。这三个项目a-xyzy-uy-w对应于相同的归约分析状态。这三个项目形成一个配置集，对应于每个配置集，分析表将有一个状态。LR(0)项目集规格系列和LR(0)项目集规格系列C=I0，i1，I1，I

7、n 程序集(G(G)BegInc :=闭包( s )。s ) Repeatforc中的每个项目集I和每个语法符号xDoifGO(I，x)都不为空，并且不属于CThen。将GO(I，x)置于c位置，直到不会增加结束。6.2语法g :(0)s e(1)eaa(2)ebb(3)aca(4)ad(5)bCB(7)bDLR(0)项目集规格系列(DFA识别g的活前缀):I 0:s e 1:s e . I 2: ea . AEAAACAEBBAd。 I 3: eb . bi 4: ac . ai 5: bCBAcabc . bbdadbcbbdi 63360 I 73360 I 83: eaa . ebb

8、. aca . I 9: bCB . I 10: ad . I 11: bCB . lr(0)分析表结构。 假设c=i0，i1，在中，每个项目集Ik的下标k是分析器的一个状态，因此，g的LR(0)分析表包含状态0，1，让包含项目s 的Ik的下标k。这是初始状态。动作和转到可以根据以下方法构造：如果项目a 。a属于Ik和GO(Ik，a)=Ij，a是终止符，那么ACTIONk，a被设置为“将状态j和符号a移动到堆栈上”并缩写为“SJ”；如果项a 属于Ik，则对于任何终止符A，将ACTIONk，a设置为“使用生产公式A进行缩减”，并简单地将其写为“rj”；其中假设A是文法g 的第j个乘积；如果项目S

9、 S .属于Ik，则动作k，#被设置为“已接受”，并简单地标记为“ACC”；如果go (ik，a)=ij且A是非终止符，则GOTO(k，A)=j；分析表中不能用规则1至4填充信息的所有空白单元格都标有“错误标志”。如果每个条目不包含多个定义，那么根据上述算法构造的带有ACTION和GOTO的分析表被称为语法g的LR(0)表。带有左(0)表的文法G被称为左(0)文法。LR(0)语法不明确。LR(0)项目根据点的位置和它是终止符还是非终止符或点后为空分为以下几类：移入项目，以a aa的形状作为终止符，以a b的形状作为承包项目，以a 接受项目的形状，以ssa 的形状作为LR(0)项目，以a成为承包项目的形状？6.1GS是：SaAcBeAbAAbBd1)构建DFA2)以识别活前缀并构建其LR(0)分析表。3)分别给出了输入符号串abbcde和1)Abbce的LR(0