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

编译原理作业集第五章自下而上语法分析西安理工大学计算机科学与工程学院张发存编写4/2/20205:36:30PM-1-第五章语法分析—自下而上分析本章要点1.自下而上语法分析法的基本概念：2.算符优先分析法；3.LR分析法分析过程；4.语法分析器自动产生工具YACC；5.LR分析过程中的出错处理。本章目标掌握和理解自下而上分析的基本问题、算符优先分析、LR分析法及语法分析器的自动产生工具YACC等内容。本章重点1．自下而上语法分析的基本概念：归约、句柄、最左素短语；2．算符优先分析方法：FirstVT,LastVT集的计算，算符优先表的构造，工作原理；3．LR分析器：（1）LR(0)项目集族，LR(1)项目集簇；（2）LR(0)、SLR、LR(1)和LALR(1)分析表的构造；（3）LR分析的基本原理，分析过程；4．LR方法如何用于二义文法；本章难点1.句柄的概念；2.算符优先分析法；3.LR分析器基本；作业题一、单项选择题：1.LR语法分析栈中存放的状态是识别________的DFA状态。a.前缀；b.可归前缀；c.项目；d.句柄；2.算符优先分析法每次都是对________进行归约：(a)句柄（b）最左素短语(c)素短语(d)简单短语编译原理作业集第五章自下而上语法分析西安理工大学计算机科学与工程学院张发存编写4/2/20205:36:30PM-2-3.有文法G＝（｛S｝，｛a｝，｛S→SaS，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-FP|PP-(T)|a该文法句型T*P(T*F)的最左直接短语是下列符号串________。a.(T*F)，b.T*F，c.P，d.P(T*F)14.在通常的语法分析方法中，（）特别适用于表达式的分析。a．算符优先分析法b．LR分析法c．递归下降分析法d．LL(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；编译原理作业集第五章自下而上语法分析西安理工大学计算机科学与工程学院张发存编写4/2/20205:36:30PM-3-二、填空题：1.规范归约的关键问题是________。2.LR(k)分析法中，L的含义是____________________，R的含义是_______________________，k的含义是。3.移进一归约分析对符号串的使用有四类操作：移进、__________、_________和出错处理。4.设文法G（E为其开始符号）产生式如下：E→E+T|TT→T*F|FF→（E）|i则句型E+T*F+i的句柄是_________________。5.自下而上分析方法的基本思想是：从输入符号串开始，利用文法规则逐步进行归约，直至归约到文法的。6.在算符优先分析中，用来刻画“可归约串”；在规范归约分析中，用来刻画“可归约串”。7.在LR(0)分析中，相容的项目集，必须满足的条件是_______，_______。8.LR语法分析栈中存放的状态是识别_______的DFA状态。9.在LR分析过程中的任何时候，栈里的文法符号从下往上应该构成，把输入串的剩余部分配上之后应成为。10.对于LR(0)分析法来说，项目A→12对活前缀1是有效的，其条件是存在规范推导。11.形式上我们说一个LR(1)项目[A→，a]对于活前缀是有效的，如果存在规范推导。12.LR(k)分析方法中项目类型可分为四类、、和。13.所谓算符优先分析法就是仿照算术四则运算的运算过程设计的一种语法分析方法。它首先要规定，然后利用这种关系确定，并进行。14.如图所示的语法树中，a，b不在同一句柄中，先归约，所以的优先级高于。PbR……a…Q15.对于句型η的语法树，若它的一棵子树的根标记为A，且将此子树的末端结点标记从左至右排列起来所形成的符号串为β，则β是；此时文法中必有推导。16.LR(0)每个项目中圆点的左部表示在分析过程中，要用该产生式归约时，，右部表示。17.根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别的NFA的一个状态。编译原理作业集第五章自下而上语法分析西安理工大学计算机科学与工程学院张发存编写4/2/20205:36:30PM-4-二．答案：1.寻找或确定一个句型的句柄；2.从左到右扫描输入串，构造一个最右推导的逆过程；3.归约，接受；4.T*F；5.开始符号；6.最左素短语，句柄；7.移进项目和归约项目并存，多个归约项目并存；8.文法活前缀和可归前缀；9.活前缀，规范句型；10.21*'RRAS；11.RRAS*'，其中=，a是的第一个符号，或者a是#而为。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.×；编译原理作业集第五章自下而上语法分析西安理工大学计算机科学与工程学院张发存编写4/2/20205:36:30PM-5-五、名词解释：1.短语，直接短语，句柄；2.规范归约，规范推导；3.算符文法，算符优先文法；4.素短语，最左素短语；5.前缀，活前缀；6.LR(0)项目，LR(0)项目集规范族；五.答案：1.设G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有：S=*A且A=*，则称是句型相对于非终结符A的短语。特别地，如果A=，则称是句型相对于规则A-的直接短语。一个句型的最左直接短语称为该句型的句柄。2.在形式语言中，最右推导常称规范推导。规范归约是最右推导的逆过程，也称最左归约。3.一个文法，如果它的任何一个产生式的右部都不含两个相继（并列）的非终结符，即不含如下形式的产生式右部：……QR……，则我们称该文法为算符文法。在一个算符文法中的任何终结符对（a，b），至多只满足下述三个关系之一：a=b，ab，ab，则称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)，或两种情形都有编译原理作业集第五章自下而上语法分析西安理工大学计算机科学与工程学院张发存编写4/2/20205:36:30PM-6-与之对应，G的LR(0)项目集规范族或有下面的(i)，或有下面的(ii)，或两者皆有：因为G是SLR(1)文法，因此有：a不属于FOLLOW(A)，FOLLOW(A)∩FOLLOW(B)＝Φ根据G的LR(1)项目集，有a∈FOLLOW(A)，FOLLOW(A)∩FOLLOW(B)≠Φ这和假设矛盾。因此，任何SLR(1)文法都是LR(1)文法。2.自底向上分析技术采用移进－归约法实现句型分析，但移进－归约法决不是一种分析技术，它本身不能解决自底向上分析计数所必须解决的两个基本问题，移进－归约法仅仅是适用于各种自底向上技术的一种实现方法。3.自底向上分析的关键是寻找句柄。简单优先分析法、算符优先分析法都是自左向右地向前查看若干个输入符号，找出句柄（或其变型－最左素短语）的尾，然后回头（从右到左）找出句柄（或其变型－最左素短语）的头，这已不是严格地从左到右查看源程序来进行归约了。LR(k)分析法则严格地从左到右地读入输入符号串中的符号，且最多向貌似句柄的符号串后看确定个数的符号，就能一点不回溯地识别该貌似句柄的符