西安理工大学《编译原理》编译原理作业集－第五章.doc

第五章 语法分析—自下而上分析 本章要点 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)简单短语 3. 有文法G＝（｛S｝，｛a｝，｛S→SaS，S→ε｝，S），该文法是________。 a. LL(1)文法；b.二义性文法；c.算符优先文法；d.SLR(1)文法； 4. 在编译程序中，语法分析分为自顶向下分析和自底向上分析两类和LL(1)分析法属于自顶向下分析；a. 深度分析法 宽度优先分析法 算符优先分析法 递归子程序分析法5. 自底向上语法分析采用分析法，常用的是自底向上语法分析有算符优先分析法和LR分析法。递归 回溯 枚举 移进－6. 一个LR(k)文法。 a. 都是无二义性的；b. 都是二义性的；c. 一部分是二义性的；d. 无法判定；在编译程序中，语法分析分为自顶向下分析和自底向上分析两类和LR分析法属于自底向上分析。a. 深度分析法 宽度优先分析法 算符优先分析法 递归子程序分析法在编译程序中，语法分析分为自顶向下分析和自底向上分析两类自顶向下分析试图为输入符号串构造一个；语法树 有向无环图 最左推导 最右推导在编译程序中，语法分析分为自顶向下分析和自底向上分析两类自底向上分析试图为输入符号串构造一个。语法树 有向无环图 最左推导 最右推导采用自顶向下分析方法时，要求文法中不含有。 右递归 左递归 直接右递归 直接左递归 LR分析是寻找右句型的 ；算符优先分析是寻找右句型的。短语素短语最左素短语句柄LR分析法中分析能力最强的是；分析能力最弱的是。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)在通常的语法分析方法中，（　　）特别适用于表达式的分析。．算符优先分析法　．LR分析法　．递归下降分析法　．LL(1)分析法.运算符的优先数之间有几种关系.3种　　　. 2种　　　. 4种　　. 1种算符优先法属于（　）.自上而下分析法　.LR分析法　.ＳLR分析法　.自下而上分析法 a.句柄 b. 前缀 c. 活前缀 d. LR(0)项目 一．答案： 1. b；2. b；3. b；4. d；5. d；6. a；、填空题： 1. 规范归约的关键问题是________。 2. LR分析法中，L的含义是____________________，R的含义是_______________________3. 移进一归约分析对符号串的使用有四类操作：移进、__________、_________和出错处理。 4. 设文法G（E为其开始符号）产生式如下： E→E+T|T T→T*F|F F→（E）|i 则句型E+T*F+i的句柄是_________________。 5. 自下而上分析方法的基本思想是：从输入符号串开始，利用文法规则逐步进行归约，直至归约到文法的 。 6. 在算符优先分析中，用来刻画“可归约串”；在规范归约分析中，用 来刻画“可归约串”。在LR(0)分析中，相容的项目集，必须满足的条件是_______，_______。LR语法分析栈中存放的状态是识别_______的DFA状态A→(1((2对活前缀((1是有效的，其条件是存在规范推导 。 11. 形式上我们说一个LR(1)项目[A→(((，a]对于活前缀(是有效的，如果存在规范推