《《编译原理课程教案》第4章：lr分析方法》由会员分享，可在线阅读，更多相关《《编译原理课程教案》第4章：lr分析方法（144页珍藏版）》请在金锄头文库上搜索。
1、LR分析方法,第四章（3）,本章要求,主要内容： LR分析方法及其相关概念，语法分析器的自动生成，各种语法分析中的错误处理 重点掌握：LR分析方法与分析过程，活前缀、LR(0)项目、Closure 和 go函数的定义，项目集规范族及识别活前缀的有穷自动机的构造，LR(0)分析表的构造，SLR文法及其分析表的构造。,LR分析概述,LR分析法：L从左向右扫描输入串，R构造最右推导的逆过程 大多数用上下文无关文法描述的高级语言的语法成分可以用LR分析器来识别。 LR分析：采用移进-归约分析，严格的规范归约。 LR分析根据当前分析栈中的符号串和向右顺序查看输入串的K(K0)个符号就可以唯一确定分析的动
2、作是移进还是归约。 向前查看0个符号，就是LR(0)分析方法，向前查看1个符号，就是LR(1)方法。,LR分析的优缺点,优点： 比其他“移进-归约”方法使用广泛，识别率高 能用LL(1)分析法分析的所有文法都能使用LR方法来进行分析。 LR分析法在扫描输入串时就能发现其中的任何错误，并能准确地指出出错位置。 缺点： 手工构造分析表工作量太大。必须使用自动生成器。,自底向上分析法的关键问题是如何确定句柄。LR分析法与算符优先方法一样，LR方法也是通过求句柄逐步归约来进行语法分析。 在算符优先分析中，通过算符的优先关系得到句柄“最左素短语”，LR方法中句柄是通过识别活前缀而求得。,LR分析方法的基
3、本思想是：在规范归约过程中，一方面记住已移进和归约出的整个符号串(历史)，另一方面又根据所用产生式推测未来可能碰到的输入符号(对未来的展望)。 当某一符号串类似于句柄出现在栈顶时，需要根据已记载的“历史”、“展望”和“现实”的输入符号三方面的内容来决定栈顶的符号串是否构成了真正的句柄，是否需要归约。 一个LR分析器的组成见下图。,1、LR分析方法的逻辑结构,一个LR分析器由3个部分组成： LR分析程序，又称总控程序。所有的LR分析器都是相同的。 分析表(分析函数)，不同的文法分析表不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表(ACTION)和状态转换(GOTO)表
4、两个部分，它们都可用二维数组表示。 分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。,状态栈：(S0,#)为预先放到栈中的初始状态和符号。,文法符号：X1X2Xm是目前已移进并归约出的句型部分。其实它是多余的，已经概括到状态里。,分析器实际上是一个带有先进后出栈的确定的有穷自动机。将“历史”和“展望”综合成“状态”，分析栈用来存放状态，状态概括了从分析开始直到某一归约阶段的全部历史和展望资料，不必象算符优先分析法中要翻阅栈中的内容才能决定是否要进行归约。只需根据栈顶状态和输入符号就可以唯一决定下一个动作。,总控程序根据分析表的内容来决定其下一步的处理动作，分析表是根据具体的文法按某种
5、规则构造出来的。 LR方法：根据具体文法的分析表对输入串进行分析处理。 LR分析过程：在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和当前输入符号，按分析表中的内容完成相应的分析工作。,2. 分析表的组成：,表中actionSi,aj，指出如果当前栈顶为状态Si，输入符号为aj时应执行的动作。其动作有四种可能，分别为：移进(S)、归约(r)、接受(acc)、出错(error)。,(1) 分析动作表Action是一个二维数组,表中gotoSi,xj指出状态为Si，遇到Xj时应转到的下一状态。 显然：分析表定义了一个以文法符号为字母表的DFA,(2) 状态转换表goto 也是一个二
6、维数组,ri表示按第i个产生式进行归约,Si表示把当前输入符号移进栈，第i个状态进状态栈。,i表示转第i个状态，即第i个状态进状态栈。,空白表示分析动作出错,例：LR的Action和GoTo表,(1) E E+T (2) E T (3) T T*F (4) T F (5) F (F) (6) F i,产生式的序号,设文法为GL：,用三元式: (状态栈，符号栈，输入符号串) 表示分析过程中状态栈，符号栈，输入符号串的变化 初始时，将状态S0和#进分析栈。三元式为： (S0, # , a1a2an#) 任一时刻的三元式为： (S0S1Sm, #X1X2Xm, aiai+1an#) 分析器的下一步动
7、作是由栈顶状态Sm和当前面临的输入符号ai唯一确定的。,3、LR分析过程：,移进：当前输入符号ai移进符号栈，将action表中指出的状态S进状态栈。 (S0S1SmS, # X1X2Xmai, ai+1an#),根据Sm和ai查action表, actionSm, ai有4种情况：,出错：报告出错信息。三元式的变化过程终止。,接受：分析成功，终止分析。三元式不再变化。,归约：若产生式A的右端长度为r，则两个栈顶的r个元素同时出栈，A进符号栈; 再根据Sm-r和A查goto表，S=gotoSm-r, A进状态栈。三元式变为： (S0S1 Sm-r S, # X1X2Xm-rA, aiai+1a
8、n #),LR分析器示例：,文法G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fi,其LR分析表为:,sj:：把下一状态j和现行输入符号a移进桟。,rj:：按第j个产生式进行规约。,acc：接受。,空白格：出错标志。,若a为终结符，则GOTOs，a的值已列在ACTIONs，a的sj之中（状态j），因此，GOTO表仅对所有非终结符A列出GOTOs，A的值。,假定输入串为i*i+i， LR分析器的工作过程: 步骤 状态桟 符号桟 输入串 (1) 0 # i*i+i# (2) 05 #i *i+i# (3) 03 #F *i+i# (4) 02
9、#T *i+i# (5) 027 #T* i+i#,i,*,归约 指用某产生式A进行归约. 假若的长度为r， 归约动作是， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s=GOTOsm-r, A和文法符号A推进栈。,假定输入串为i*i+i， LR分析器的工作过程: 步骤 状态 符号 输入串 (5) 027 #T* i+i# (6) 0275 #T*i +i# (7) 02710 #T*F +i# (8) 02 #T +i# (9) 01 #E +i# (10) 016 #E+ i#,+,i,步骤 状态 符号 输入串 (10) 016 #E+ i# (11) 0
10、165 #E+i # (12) 0163 #E+F # (13) 0169 #E+T # (14) 01 #E # (15) 接受,+,i,i,为了介绍LR分析过程，直接给出该文法的分析表，以后再介绍如何生成,例：LR的具体分析过程：,(1) E E+T (2) E T (3) T T*F (4) T F (5) F (F) (6) F i,设文法为GL：,根据上述分析表，对输入串 i * i + i 的分析过程如下：,LR文法：对一个文法，如果能够构造一个分析表，且它的每个入口均是唯一的 如何构造LR分析表？,4.3.1 LR(0)项目集族和LR(0)分析表的构造,假定是文法G的一个句子，我
11、们称序列 n， n-1， ，0 是的一个规范归约，如果此序列满足： 1 n= 2 0为文法的开始符号，即0=S 3 对任何i，0 i n， i-1是从i经把句柄替换成为相应产生式左部符号而得到的。,LR(0)分析就是在分析的每一步，只需根据当前桟顶状态而不必向前查看输入符号就能确定应采取的分析动作。,规范归约过程中 栈内的符号串和扫描剩下的输入符号串构成了一个规范句型。 栈内的如果出现句柄（最左直接短语），句柄一定在栈的顶部。,栈内永远不会出现句柄之后的符号！,字的前缀：是指字的任意首部，如字abc的前缀有，a，ab，abc 活前缀：是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，
12、对于规范句型，为句柄，如果=u1u2ur，则符号串u1u2ui(1ir)是的活前缀。(必为终结符串)。 在LR分析工作过程中的任何时候，桟里的文法符号（自桟底而上）X1X2Xm应该构成活前缀，把输入串的剩余部分配上之后即应成为规范句型（如果整个输入串确实构成一个句子）。,引入一个新的概念：规范句型的活前缀,为什么？,因为首先规约的是句柄。,为什么要引入活前缀的概念？,因为句柄是活前缀的后缀，识别活前缀就可以找到句柄；找到了句柄，就可以对句柄归约。,对于一个文法G, 可以构造一个有限自动机DFA,它能识别G的所有活前缀。在这个基础上，我们再研究如何把这种自动机转变成LR分析表。,构造LR(0)分
13、析表的基本思想是：从给定的上下文无关文法直接构造识别文法所有规范句型的活前缀的DFA，然后再将DFA转换为一张LR(0)分析表。,文法G的每个产生式的右部添加一个圆点称为G的一个LR(0)项目（简称项目）。 如:AXYZ有四个项目： A.XYZ AX.YZ AXY.Z AXYZ. 一个项目指明了在分析过程的某个时刻看到产生式的多大一部分。 为什么要引入项目的概念？,LR(0)项目,为什么要引入项目的概念？,活前缀与句柄之间的关系有三种情况： 活前缀中已含有句柄的全部符号，表明此时某一规则A的右部符号串已出现在桟顶，其相应的分析动作是用此规则进行规约。 (2)活前缀中只含句柄的一部分符号，此时意
14、味着形如A12规则的右部子串1已出现在桟顶，正期待着从剩余的输入串中移进2 ； (3)活前缀中全然不含有句柄的任何符号，此时意味着期望从剩余输入串中能看到由某规则A的右部所推出的符号串。 为了刻画在分析过程中，文法的某一规则的右部符号串已有多大一部分被识别，我们可在文法的每个规则的右部适当位置上加一个圆点来表示。针对上述活前缀与句柄之间关系的三种情况，标有圆点的规则分别是： (1)A. (2)A1 . 2 (3)A . ,由于不同的LR(0)项目反映了在分析过程中桟顶的不同状态，因此，可以根据圆点的位置和圆点后是终结符还是非终结符，将一个文法的全部LR(0)项目进行分类（4类）： (1)A .
15、 称为“归约项目” 规约项目表示文法的某一个规则的右部已分析完，句柄已形成，应按次规则进行规约。 (2)归约项目 S . 称为“接受项目” 接受项目是对文法开始符号的规约项目。 (3)A .a (aVT) 称为“移进项目” 移进项目表示期待从输入串中移进一个符号，以待形成句柄。 (4)A .B (BVN) 称为“待约项目”. 待约项目表示期待从剩余的输入串中规约而得到B，然后才能继续分析A的右部。,文法G(S) SE EaA|bB AcA|d BcB|d 该文法的项目有： 1. SE 2. SE 3. EaA 4. EaA 5. EaA 6. AcA 7. AcA 8. AcA 9. Ad 10. Ad 11. EbB 12. EbB 13. EbB 14. BcB 15. BcB 16. BcB 17. Bd 18. Bd,有效项目,我们说项目A 1.2对活前缀1是有效的，其条件是存在规范推导,指规范推导。,有效项目中的圆点“.”,意味着对应产生式中的“.”所在处就是这个活前缀的终止点。,项目A1.2对活前缀1有效，具有两层含意： 从文法开始符号，经1可到达该项目(项目所在状态)； 在当前活前缀的情况下，该项目可指导下一步分析动作(A=12)。,有效项目的意义： 1.到目前为止分析
