编译原理作业集-第五章-修订.doc

编译原理作业集 第五章 自下而上语法分析第五章 语法分析自下而上分析本章要点1. 自下而上语法分析法的基本概念： 2. 算符优先分析法；3. LR分析法分析过程；4. 语法分析器自动产生工具YACC；5. LR分析过程中的出错处理。本章目标掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。本章重点1自下而上语法分析的基本概念：归约、句柄、最左素短语；2算符优先分析方法：FirstVT, LastVT集的计算，算符优先表的构造，工作原理；3LR分析器：（1）LR(0)项目集族，LR(1)项目集簇；（2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造；（3）LR分析的基本原理，分析过程；4LR方法如何用于二义文法；本章难点1. 句柄的概念；2. 算符优先分析法；3. LR分析器基本；作业题一、单项选择题：1. LR语法分析栈中存放的状态是识别_的DFA状态。a. 前缀；b. 可归前缀；c. 项目；d. 句柄；2. 算符优先分析法每次都是对_进行归约：(a)句柄 （b）最左素短语(c)素短语(d)简单短语3. 有文法G（S，a，SSaS，S，S），该文法是_。a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法；4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类， 和LL(1)分析法属于自顶向下分析；a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法5. 自底向上语法分析采用 分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。a. 递归 b. 回溯 c. 枚举 d. 移进归约6. 一个LR(k)文法，无论k取多大， 。a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定二义性；7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类， 和LR分析法属于自底向上分析。a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法8. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自顶向下分析试图为输入符号串构造一个 ；a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导9. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自底向上分析试图为输入符号串构造一个 。a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导10. 采用自顶向下分析方法时，要求文法中不含有 。a. 右递归 b. 左递归 c. 直接右递归 d. 直接左递归11. LR分析是寻找右句型的 ；而算符优先分析是寻找右句型的 。a. 短语； b. 素短语； c. 最左素短语； d. 句柄12. LR分析法中分析能力最强的是 ；分析能力最弱的是 。a. SLR(1)； b. LR(0)； c. LR(1)； d. LALR(1)13. 设有文法G：T-T*F | FF-FP | PP-(T) | a该文法句型T*P(T*F)的最左直接短语是下列符号串_。a. (T*F)，b. T*F，c. P，d. P(T*F)14. 在通常的语法分析方法中，（）特别适用于表达式的分析。a算符优先分析法bLR分析法c递归下降分析法dLL(1)分析法15. .运算符的优先数之间有几种关系 。a.3种b. 2种c. 4种d. 1种16. 算符优先法属于（）a.自上而下分析法b.LR分析法c.LR分析法d.自下而上分析法 17. 在LR分析法中，分析栈中存放的状态是识别规范句型 的DFA状态。a.句柄 b. 前缀 c. 活前缀 d. LR(0)项目一答案：1. b；2. b；3. b；4. d；5. d；6. a；7. c；8. c；9. d；10. b；11. d，c；12. c，b；13. a；14. a15. a；16. d；17. c；二、填空题：1. 规范归约的关键问题是_ 。2. LR(k)分析法中，L的含义是_，R的含义是_，k的含义是 。3. 移进一归约分析对符号串的使用有四类操作：移进、_、_和出错处理。4. 设文法G（E为其开始符号）产生式如下：EE+T|TTT*F|FF（E）|i则句型E+T*F+i的句柄是_。5. 自下而上分析方法的基本思想是：从输入符号串开始，利用文法规则逐步进行归约，直至归约到文法的 。6. 在算符优先分析中，用 来刻画“可归约串”；在规范归约分析中，用 来刻画“可归约串”。7. 在LR(0)分析中，相容的项目集，必须满足的条件是_，_。8. LR语法分析栈中存放的状态是识别_的DFA状态。9. 在LR分析过程中的任何时候，栈里的文法符号从下往上应该构成 ，把输入串的剩余部分配上之后应成为 。10. 对于LR(0)分析法来说，项目Ab1b2对活前缀ab1是有效的，其条件是存在规范推导 。11. 形式上我们说一个LR(1)项目Aab，a对于活前缀g是有效的，如果存在规范推导 。12. LR(k)分析方法中项目类型可分为四类 、 、 和 。13. 所谓算符优先分析法就是仿照算术四则运算的运算过程设计的一种语法分析方法。它首先要规定 ，然后利用这种关系确定 ，并进行 。14. 如图所示的语法树中，a，b不在同一句柄中， 先归约，所以 的优先级高于 。15. 对于句型的语法树，若它的一棵子树的根标记为A，且将此子树的末端结点标记从左至右排列起来所形成的符号串为，则是 ；此时文法中必有推导 。16. LR(0)每个项目中圆点的左部表示在分析过程中，要用该产生式归约时， ，右部表示 。17. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别 的NFA的一个状态。二答案：1. 寻找或确定一个句型的句柄；2. 从左到右扫描输入串，构造一个最右推导的逆过程；3. 归约，接受；4. T*F；5. 开始符号；6. 最左素短语，句柄；7. 移进项目和归约项目并存，多个归约项目并存；8. 文法活前缀和可归前缀；9. 活前缀，规范句型；10. ；11. ，其中g=da，a是w的第一个符号，或者a是#而w为e。12. 归约项目，接受项目，移进项目，待约项目；13. 运算符之间的优先关系；句型的“句柄”， 归约；14. a，a，b；15. 句型相对于A的一个短语；A=+ ；16. 句柄已识别的部分(进入符号栈)，等待识别的部分；17. 活前缀三、判断题1. 一个二义性文法可以是SLR文法或LALR文法。（ ）2. LL(1)文法不能用LR（1）分析器来分析。（ ）3. LR分析器在自左至右扫描输入串时就能发现其中的任何错误，并能准确地指出出错地点。( ）4. 在归约过程的任一时刻，一个上下文无关文法的任何句型的直接短语一般都不是唯一的。( )5. 算符优先分析法不是一种规范规约法。 ( )6. 存在有左递归规则的文法是LL(1)的。 ( )7. 任何算符优先文法的句型中不会有两个相邻的非终结符号。 ( )8. 算符优先文法中任何两个相邻的终结符号之间至少满足三种关系(，)之一。 ( )9. 任何LL(1)文法都是无二义性的。 ( )10. 每一个SLR(1)文法也都是LR(1)文法。 ( )11. 存在一种算法，能判定任何上下文无关文法是否是LL(1)的。 ( )12. 任何一个LL(1)文法都是一个LR(1)文法，反之亦然。 ( )13. LR(1)分析中括号中的1是指，在选用产生式A进行分析，看当前读入符号是否在FIRST()中。 ( ) 14. 若某一个句型中出现了某一产生式的右部，则此右部不一定是该句型的句柄。（ ）15. 算符优先关系表不一定存在对应的优先函数。 （ ）16. 简单优先文法允许任意两个产生式具有相同右部。 （ ）17. 一个句型的句柄一定是文法某产生式的右部。 （ ）18. 若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 （ ）19. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别活前缀的DFA的一个状态。 （ ）四答案：1. ；2. ；3. ；4. ；5. ；6. ；7. ；8. ；9. ；10. ；11. ；12. ；13. ；14. ；15. ；16. ；17. ； ；19. ；五、名词解释：1. 短语，直接短语，句柄；2. 规范归约，规范推导；3. 算符文法，算符优先文法；4. 素短语，最左素短语；5. 前缀，活前缀；6. LR(0)项目，LR(0)项目集规范族；五. 答案：1. 设G是一个文法，S是文法的开始符号，假定abd是文法G的一个句型，如果有：S=*aAd且A=*b，则称b是句型abd相对于非终结符A的短语。特别地，如果A=b，则称b是句型abd相对于规则A-b的直接短语。一个句型的最左直接短语称为该句型的句柄。2. 在形式语言中，最右推导常称规范推导。规范归约是最右推导的逆过程，也称最左归约。3. 一个文法，如果它的任何一个产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：QR，则我们称该文法为算符文法。在一个算符文法中的任何终结符对（a，b），至多只满足下述三个关系之一：a=b，ab，则称G是一个算符优先文法。4. 所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除自身之外不再含任何更小的素短语。所谓最左素短语是指处于句型最左边的哪个素短语。5. 一个字的前缀是指该字的任意首部。活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。6. 文法G的每一个产生式的右部添加一个小圆点，称为G的一个LR(0)项目。构成识别一个文法活前缀的DFA的项目集（状态）的全体，称为该文法的项目集规范族。六、简答题：1. 说明任何SLR(1)文法都是LR(1)文法。2. 为什么移进归约法不是一种语法分析方法？3. LR(k)分析法是如何做到严格地自左向右进行分析的？4. 使用状态有限的识别可归前缀的有穷自动机，为什么可以识别语言的无穷多个句子？5. LR项目的含义是什么？六答案：1. 假设有一个SLR(1)文法G不是LR(1)文法，那么在G的LR(1)项目集规范族中，或有下面的(i)，或有下面的(ii)，或两种情形都有与之对应，G的LR(0)项目集规范族或有下面的(i)，或有下面的(ii)，或两者皆有：因为G是SLR(1)文法，因此有：a不属于FOLLOW(A)， FOLLOW(A)FOLLOW(B)根据G的LR(1)项目集，有aFOLLOW(A)， FOLLOW(A)FOLLOW(B)这和假设矛盾。因此，任何SLR(1)文法都是LR(1)文法。2. 自底向上分析技术采用移进归约法实现句型分析，但移进归约法决不是一种分析技术，它本身不能解决自底向上分析计数所必须解决的两个基本问题，移进归约法仅仅是适用于各种自底向上技术的一种实现方法。3. 自底向上分析的关键是寻找句柄。简单优先分析法、算符优先分析法都是自左向右地向前查看若干个输入符号，找出句柄（或其变型最左素短语）的尾，然后回头（从右到左）找出句柄（或其变型最左素短语）的头，这已不是严格地从左到右查看源程序来进行归约了。LR(k)分析法则严格地从左到右地读入输入符号串中的符号，且最多向貌似句柄的符号串后看确定个数的符号，就能一点不回溯地识别该貌似句柄的符号串是否真正的句柄。它的基本思想是：在规范归约的过程中，一方面记住已移进和归约出的符号串，即记住“历史”，另一方面根据所用的产生式（规则）推测未来可能碰到的输入符号，即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈的顶部时，能够根据所记载的“历史”、“展望”的信息以及“现实”中的输入符号三方面的材料，来确定符号栈顶部的符号串是否构成相对于某一规则左部的句柄，从而确定将要做的工作。为了记住分析的“历史”和汇集全新的“展望”信息，LR分析技术这样来处理：将归约过程的“历史”和“展望”材料综合地抽象成某些状态，存放在一个状态栈中，栈中每个状态都概括了从分析开始直到某一归约阶段的全部“历史”和“展望”材料。因此，任何时候栈顶的状态都代表了整个“历史”和已推测出的“展望”信息，都可以从栈顶状态得知所要了解的一切，而无需自底向上翻阅整个栈。LR分析程序的每一步工作都是由栈顶状态和现行输入符号惟一确定的。根据文法，可以将各种状态下面临不同输入符号所要做的工作用一张表表示出来，然后用这张表直到整个分析过程的进行。4. 这是因为，许多句型在归约过程中虽然分析的步数和过程不一样，但它们所处的状态有一些是一样的，而这些同样的状态在有穷自动机中只需要出现一个即可。5. LR项目是在规则右部适当位置加一个圆点得到的，用圆点的位置来标记分析过程中的某个时刻。圆点的含义为：对规则右部的符号串，已从输入串看到可由圆点左部推出的符号子串，希望能进一步看到可由圆点右部推出的符号串；如果圆点右部为e，则自然联想到可将规则右部归约成规则左部。此时，圆点左部的符号子串一定是一个可归前缀。因此，项目刻画了在分析过程中一条规则的右部已有哪些成分被识别。七、应用题：1. 文法如下：Sa | L | (T)TT, S | S(1) 计算该文法的Firstvt和Lastvt；(2) 构造算符优先关系表,并说明该文法是否是OPG文法；(3) 计算优先函数；(4) 给出串(a,a)#和(a,(a,a) #的算符优先分析过程。1.答案： （1）Firstvt(S)=a, L, ( ，Firstvt(T)=a, , , L, ( ，Lastvt(S)=a, L, ) ，Lastvt(T)=a, , , L, ) （2）aL(),aL(=,.该文法是OPG文法. a L ( ) , f0 1 1 1 1 1 g0 1 1 1 1 1 f1 2 2 1 3 3 g1 2 2 2 1 2 f2 3 3 1 3 3 g2 4 4 4 1 2先给出该文法的语法树:步骤 栈 优先关系 当前符号 剩余符号 动作0#(a,a) #1#(a,a) #移进2#(,a)#归约4#(S,a)#移进5#(S,)#归约7#(S,S)#归约8#(T=)#脱括号9#S=#接受2. 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。 SSab | bR RS | a2. 答案：（1） 该文法的拓广文法G为 (0) S S(1) S Sab(2) S bR(3) R S(4) R a其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：I0 = SS, SSab, SbRI1 = SS, SSabI2 = SbR, RS, Ra, SSab, SbRI3 = SSabI4 = SbRI5 = RS, SSabI6 = RaI7 = SSab求FOLLOW集：FOLLOW(S)=FOLLOW(R)=FOLLOW(S)=a,在I5中，出现移进归约冲突，且FOLLOW(R)a=a因此，此文法不是SLR(1)文法。3. 证明下面文法是SLR(1)文法，并构造其SLR分析表。EE+T|T TTF|F FF*|a|b输入串b+ab*是该文法的句子吗？给出对该串的分析过程。答案：3. 该文法的拓广文法G为 (0) E E(1) E E+T(2) E T(3) T TF(4) T F(5) F F*(6) F a(7) F b其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0 = EE, EE+T, ET, TTF, TF, FF*,Fa, FbI1 = EE, EE+TI2 = ET, TTF, FF*, Fa, FbI3 = TF, FF*I4 = FaI5 = FbI6 = EE+T, TTF, TF, FF*, Fa, FbI7 = TTF, FF*I8 = FF*I9 = EE+T, TTF, FF*, Fa, Fb求FOLLOW集：FOLLOW(E)=, FOLLOW(T)=, , a, bFOLLOW(F)=, , a, b, *构造的SLR分析表如下： 显然，此分析表无多重定义入口，所以此文法是SLR文法。4. 下面文法属于哪类LR文法？试构造其分析表。S(SR|a R,SR|)输入串（a,a）是文法的句子吗？给出分析过程。4.答案：该文法的拓广文法G为 (0) S S(1) S (SR(2) S a(3) R ,SR(4) R )构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0 = SS, S(SR, SaI1 = SSI2 = S(SR, S(SR, SaI3 = SaI4 = S(SR, R,SR, R)I5 = S(SRI6 = R)I7 = R,SR, S(SR, SaI8 = R,SR, R,SR, R)I9 = R,SR每个LR(0)项目集中没有冲突。因此，此文法是LR(0)文法。其分析表如下：5. 设文法G为 S AA BA | B aB | b（1）证明它是LR(1)文法；（2）构造它的LR(1)分析表；（3）给出输入符号串abab的分析过程。5. 答案：(1) 构造其拓广文法G的产生式为 (0) S S(1) S A(2) A BA(3) A (4) B aB(5) B b构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下：I0 = SS, $, SA, $, ABA, $, A, $, BaB, a/b/$, Bb, a/b/$I1 = SS, $I2 = SA, $I3 = ABA, $, ABA, $, A, $, BaB, a/b/$, Bb, a/b/$I4 = Bb, a/b/$I5 = BaB, a/b/$, BaB, a/b/$, Bb, a/b/$I6 = ABA, $I7 = BaB, a/b/$该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。(2)构造LR(1)分析表如下：以上分析表无多的定义入口，所以该文法为LR(1)文法。(3)对于输入串abab，其分析过程如下：6. 为下面的文法构造LALR(1)分析表SEEE+T | TT(E) | a并给出对输入串(a+a)的分析过程。6. 答案：其拓广文法G：(0) S S(1) S E(2) E E+T(3) E T(4) T (E)(5) T a构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下：I0 = SS, $, SE, $, EE+T, $/+, ET, $/+, T(E), $/+, Ta, $/+I1 = SS, $I2 = SE, $, EE+T, $/+I3 = ET, $/+I4 = T(E), $/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I5 = Ta, $/+I6 = EE+T, $/+, T(E), $/+, Ta, $/+I7 = T(E), $/+, EE+T, )/+I8 = ET, )/+I9 = T(E), )/+, EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I10 = Ta, )/+I11 = EE+T, $/+I12 = T(E), $/+I13 = EE+T, )/+, T(E), )/+, Ta, )/+I14 = T(E), )/+, EE+T, )/+I15 = EE+T, )/+I16 = T(E), )/+合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下：I0 = SS, $, SE, $, EE+T, $/+, ET, $/+, T(E), $/+, Ta, $/+I1 = SS, $I2 = SE, $, EE+T, $/+I3,8 = ET, $/+/)I4,9 = T(E), $/+/), EE+T, )/+, ET, )/+, T(E), )/+, Ta, )/+I5,10 = Ta, $/+/)I6,13 = EE+T, $/+/), T(E), $/+/), Ta, $/+/)I7,14 = T(E), $/+/), EE+T, )/+I11,15 = EE+T, $/+/)I12,16 = T(E) , $/+/)LALR分析表如下：7. 已知文法S L.L S L L LB L BB 0B 1 用LR分析法说明符号串101.110是否文法的句子。（1）拓广文法为G，增加产生式SS若产生式排序为：0 S S 1 S L.L 2 S L 3 L LB 4 L B5 B 06 B 1 由产生式知： FIRST (S ) = 0,1FIRST (S ) = 0,1 FIRST (L ) = 0,1FIRST (B ) = 0,1FOLLOW(S ) = # FOLLOW(S ) = # FOLLOW(L ) = 0,1,#FOLLOW(B ) = 0,1,#G的LR(0)项目集族及识别活前缀的DFA如下图所示： 在I2中：B .0和 B .1为移进项目，S L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I2、I8中：FOLLOW(S) 0，1= # 0，1= 所以在I2 、I8中的移进-归约冲突可以由FOLLOW集解决，所以G是SLR(1)文法。 （2）构造的SLR(1)分析表如下：状态ACTIONGOTO01#SLB0s4s51231acc2s6s4s5r273r4r4r4r44r5r5r5r55r6r6r6r66s4s5837r3r3r3r38s4s5r17对输入串101.110#的分析过程步骤状态栈符号栈剩余符号串动作12345678910111213141516171819202100 50 30 20 2 40 2 70 20 2 50 2 70 20 2 60 2 6 50 2 6 30 2 6 80 2 6 8 50 2 6 8 70 2 6 80 2 6 8 40 2 6 8 70 26801#1#B#L#L0#LB#L#L1#LB#L#L.#L.1#L.B#L.L#L.L1#L.LB#L.L#L.L0#L.LB#L.L#S101.110#01.110#01.110#01.110#1.110#1.110#1.110#.110#.110#.110#110#10#10#10#0#0#0#移进归约B 1归约L B移进归约B 0归约L LB移进归约B 1归约L LB移进移进归约B 1归约L B移进归约B 1归约L LB移进归约B 0归约L LB归约L L.Lacc分析成功，说明输入串101.110是文法的句子。8. 对于文法 SAB AaB Bb (1) 构造LR(1)分析表； (2) 给出用LR(1)分析表对输入符号串abab的分析过程。9. 给定文法GZ：ZC SCif E thenSAEEEAEAAi其中：Z、C、S、A、EVN ；if、then、iVTa) 构造此文法的LR(0)项目集规范族，并给出识别活前缀的DFA。b) 构造其SLR（1）分析表。9. 答案：1.首先拓广文法：在G中加入产生式0ZZ，然后得到新的文法G，再求G的识别全部活前缀的DFA： I0：Z.Z Z.C S C.if E thenI1： ZZ.I2： ZC .S S.AE A.iI3：Cif .E then E.EA E.A A.iI4：ZC S.I5：SA.EI6：Ai. I7：Cif E .then EE.AI9：SA.E E.EA E.A A.iI10：Cif E then.I11：EE.A A.iI12：SAE. EE.AI13：EEA. Follow(Z)#Follow(C)iFollow(S)#Follow(E)#,thenFollow(A),# ,then 则可构造SLR（1）分析表为：ACTIONGOTO0iftheni#ZCSEA0S3121OK2S6453S6784r15S96r6r6r6r67S10S118r5r5r59S612810r211S61312S11r313r4r4r410. 设有文法GS：SaAAAbAb求识别该文法所有活前缀的DFA；构造合适的LR分析表，并给出对输入串abb的分析过程。解答：(1).首先拓广文法： 在G中加入产生式0.SS，然后得到新的文法G: 0.SS 1.SaA2.AAb3.Ab(2).再求G的识别全部活前缀的DFA：11.给定文法 GS