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

1、编译原理作业集-第五章-修订 编译原理作业集 第五章 自下而上语法分析 第五章 语法分析自下而上分析 本章要点 1. 自下而上语法分析法的基本概念： 2. 算符优先分析法； 3. lr分析法分析过程； 4. 语法分析器自动产生工具yacc； 5. lr分析过程中的出错处理。 本章目标 掌握和理解自下而上分析的基本问题、算符优先分析、lr分析法及语法分析器的自动产生工具yacc等内容。 本章重点 1自下而上语法分析的基本概念：归约、句柄、最左素短语； 2算符优先分析方法：firstvt, lastvt集的计算，算符优先表的构造，工作原理； 3lr分析器： （1）lr(0)项目集族，lr(1)项目

2、集簇； （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)简单短语 西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 am - 1 - 编译原理作业集 第五章 自下而上语法分

3、析 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. 无

4、法判定二义性； 7. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类， 和lr分析法属于自底向上分析。 a. 深度分析法 b. 宽度优先分析法 c. 算符优先分析法 d. 递归下降子程序分析法 8. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自顶向下分析试图为输入符号串构造一个 ； a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 9. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类，自底向上分析试图为输入符号串构造一个 。 a. 语法树 b. 有向无环图 c. 最左推导 d. 最右推导 10. 采用自顶向下分析方法时，要求文法中不含有 。 a

5、. 右递归 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 | f f-f?p | p p-(t) | a 该文法句型t*p?(t*f)的最左直接短语是下列符号串_。 a. (t*f)， b. t*f， c. p， d. p?(t*f) 14. 在通常的语法分析方法中，（ ）特别适用于表

6、达式的分析。 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. a 15. a；16. d；

7、17. c； 西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 am - 2 - 编译原理作业集 第五章 自下而上语法分析 二、填空题： 1. 规范归约的关键问题是_ 。 2. lr(k)分析法中，l的含义是_，r的含义是_，k的含义是 。 3. 移进一归约分析对符号串的使用有四类操作：移进、_、_和出错处理。 4. 设文法g（e为其开始符号）产生式如下： ee+t|t tt*f|f f（e）|i 则句型e+t*f+i的句柄是_。 5. 自下而上分析方法的基本思想是：从输入符号串开始，利用文法规则逐步进行归约，直至归约到文法的 。 6. 在算符优先分析中，用 来

8、刻画“可归约串”；在规范归约分析中，用 来刻画“可归约串”。 7. 在lr(0)分析中，相容的项目集，必须满足的条件是_，_。 8. lr语法分析栈中存放的状态是识别_的dfa状态。 9. 在lr分析过程中的任何时候，栈里的文法符号从下往上应该构成 ，把输入串的剩余部分配上之后应成为 。 10. 对于lr(0)分析法来说，项目a?1?2对活前缀?1是有效的，其条件是存在规范推导 。 11. 形式上我们说一个lr(1)项目a?，a对于活前缀?是有效的，如果存在规范推导 。 12. lr(k)分析方法中项目类型可分为四类 、 、 和 。 13. 所谓算符优先分析法就是仿照算术四则运算的运算过程设计

9、的一种语法分析方法。它首先要规定 ，然后利用这种关系确定 ，并进行 。 14. 如图所示的语法树中，a，b不在同一句柄中， 先归约，所以 的优先级高于 。 p r b a q 15. 对于句型的语法树，若它的一棵子树的根标记为a，且将此子树的末端结点标记从左至右排列起来所形成的符号串为，则是 ；此时文法中必有推导 。 16. lr(0)每个项目中圆点的左部表示在分析过程中，要用该产生式归约时， ，右部表示 。 17. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别 的nfa的一个状态。 西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 am -

10、 3 - 编译原理作业集 第五章 自下而上语法分析 二答案： 1. 寻找或确定一个句型的句柄；2. 从左到右扫描输入串，构造一个最右推导的逆过程；3. 归约，接受；4. t*f；5. 开始符号；6. 最左素短语，句柄；7. 移进项目和归约项目并存，多个归约项目并存；8. 文法活前缀和可归前缀；9. 活前缀，规范句型；10. s?a?1?2?；11. s?a?，其中?=?，a是?的第一个符号，或者a rrrr*是#而?为?。12. 归约项目，接受项目，移进项目，待约项目；13. 运算符之间的优先关系；句型的“句柄”， 归约；14. a，a，b；15. 句型相对于a的一个短语；a=+ ；16. 句

11、柄已识别的部分(进入符号栈)，等待识别的部分；17. 活前缀 三、判断题 1. 一个二义性文法可以是slr文法或lalr文法。（ ） 2. ll(1)文法不能用lr（1）分析器来分析。（ ） 3. lr分析器在自左至右扫描输入串时就能发现其中的任何错误，并能准确地指出出错地点。( ） 4. 在归约过程的任一时刻，一个上下文无关文法的任何句型的直接短语一般都不是唯一的。( ) 5. 算符优先分析法不是一种规范规约法。 ( ) 6. 存在有左递归规则的文法是ll(1)的。 ( ) 7. 任何算符优先文法的句型中不会有两个相邻的非终结符号。 ( ) 8. 算符优先文法中任何两个相邻的终结符号之间至少

12、满足三种关系(，)之一。 ( ) 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. 简单优先文法允许任意两个产生式具有相同右部

13、。 （ ） 17. 一个句型的句柄一定是文法某产生式的右部。 （ ） 18. 若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。 （ ） 19. 根据项目的定义，可给出文法中所有产生式的项目，而每个项目都为识别活前缀的dfa的一个状态。 （ ） 四答案：1. ；2. ；3. ?；4. ?；5. ?；6. ；7. ?；8. ；9. ?；10. ?；11. ?；12. ；13. ?；14. ；15. ；16. ；17. ； ；19. ； 西安理工大学计算机科学与工程学院 张发存编写 6/24/2019 6:18:37 am - 4 - 编译原理作业集 第五章 自下而上语法分析 五、名词

14、解释： 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，ab，则称g是一个算符优先文法。 4. 所谓素短语是指这样的一个短语，它至少含有一个终结符，并且，除自身之外不再