四川大学编译原理期末试卷4套+复习资料

四川大学期末考试试题A (闭卷) (2012-2013学年第2学期)一．简答题 1.符号表的作用是什么？为了达到对其插入删除等操作的复杂度为O(1)，需将其组织成什么数据结构2.分析树和语法书的区别 3.什么是正规集 4.什么叫句子，什么叫句型 5.二义文法一定不是LL（1）   二．给定文法      S→A      A→A+A|B++      B→y 1. 画出句子y+++y++的分析树 2.给出句子y+++y++的最右推导    三．给定正则表达式（a|b）*abb 1.使用thompson构造法构造等价的NFA 2.用子集法对（1）得到的NFA进行确定化和最小化，得到等价的最小DFA 3.使用双层多分支语句实现（2）得到的DFA写出伪代码四．给定文法 statement→if-stmt|other|e if-stmt→if(exp)statement else-part else-part→else statement|e exp→0|1 写出递归下降子程序的伪代码五． 给定文法 S→[SX]|a X→e|+SY|Yb Y→e|-SXc 1. 对文法中的每一个非终结符构造First集和Follow集。

 2.构造LL（1）分析表 3.基于分析表，使用LL(1)对句子[a+a-ac]进行自顶向下的语法分析，给出每一步的动作及分析栈和输入串的变化情况六．给定文法 E→E+T|T T→T*F|F F→(E)|id  1.构造LR（0）项目的DFA： 2.构造SLR（1）的分析表 3.利用2得到的分析表对id+id*id进行自顶向下的语法分析七． 1.给出构造Follow集合的算法描述 2.给出SLR（1）算法的描述 四川大学期末考试试题 (闭卷) (2010-2011学年第2学期) 1. 简答题 (12分) (1) 编译器的前端和后端分别包括哪几个阶段？前后端分开有什么好处？ (2) 解释器和编译器有什么本质区别？ (3) 词法分析和语法分析的功能分别是什么？ (4) 分析树与抽象语法树有什么不同？2. 已知字母表 ∑= {a, b, c}å，定义在∑上的语言L具有以下特征：(5分) (1) 若出现a，则其后至少紧跟两个c； (2) 若出现b，则其后至少紧跟一个c 试给出可以产生语言L的正规表达式  3. 文法如下：(8分) exp→ exp addop term |termaddop→ +|- termterm→ mulop factor| factormulop →* factor→ (exp)|number(1)  给出句子3*)58(+的最左推导； (2) 构造(1)中句子的抽象语法树。

  4. 文法如下：(10分) exp→ exp and exp|exp or exp|not  exp|(exp)|TRUE|FALSE (1) 此文法是否为二义文法？为什么？ (2) 试将文法改写为非二义文法，要求运算符优先级由低到高分别是or、and、not，且and和or是左结合的，not是右结合的  5. DFA构造题(20分) 已知正规表达式 bbca*)|( (1) 使用Thompson构造方法构造对应的NFA； (2) 用子集构造法将得到的NFA确定化为DFA； (3) 将得到的DFA最小化6. LL(1)分析题(20分) 文法如下： A→ Pa  P → bPa|bQb  Q → Qa|a (1) 消除文法左递归，提左因子； (2) 为所得文法的每个非终结符构造First集和Follow集； (3) 所得文法是LL(1)文法吗？为什么？ (4) 构造所得文法的LL(1)分析表7. LR(k)分析题(25分) 文法如下： declaration→ type list-var ®type → int|float var -list → id,var -list|id (1) 构造文法的LR(0)项目的DFA； (2) 构造SLR(1)分析表； (3) 这个文法是SLR(1)文法吗？如果不是，请说明原因； (4) 给出对应输入串int x,y,z进行SLR(1)分析的步骤(要求给出分析过程中每一步的详细情况，包括：分析栈、输出串及执行的动作)。

四川大学期末考试试题A (闭卷) (2008-2009学年第2学期)  一、简答题 (本大题共4小题，每小题3分，共12分) 1. 按照次序写出一个完整的编译器的各个阶段以及各个阶段的输入输出2. 一个文法必须满足哪些条件才是LL(1)的？3.给出上下文无关文法(Context-Free Grammar)的定义4.写正规表达式：所有不以0开头的十进制偶数的集合二、算法题 (本答题共1小题，每小题8分，共8分) 给出基于DFA进行词法分析的表驱动的实现算法三、 分析题 (本答题共3小题，每小题分数见题首，共10分) 文法如下：S→SS+|SS*|a+® 1. (4分)给出句子aa+a*的最右推导； 2. (3分)构造(1)中句子的分析树； 3. (3分)这个文法产生的语言是什么？四、 文法二义性分析题 (本大题共2小题，每小题5分，共10分) 文法如下： exp→exp op exp |(exp)|TRUE |FALSEOp→ and|or® 1. 此文法是否为二义文法？为什么？ 2. 试将文法改写成非二义文法，要求运算符op是左结合的，且and的优先级高于or的优先级五、 DFA构造题 (本大题共3小题，每小题分数见题首，共20分)六、 已知正规表达式 (a|b)*c*b1. (6分)使用Thompson构造方法构造对应的NFA； 2. (8分)用子集构造法将得到的NFA确定化为DFA； 3. (6分)将得到的DFA最小化。

六、LL(1)分析题 (本大题共4小题，每小题5分，共20分) 文法如下：S→SLS |a®           L→bbL|b® 1. 消除文法左递归，并提左因子； 2. 为所得文法的每个非终结符构造First集和Follow集； 3. 构造所得文法的LL(1)分析表； 4. 所得文法是LL(1)文法吗？为什么？七、LR(k)分析题 (本大题共3小题，每小题分数见题首，共20分) 文法如下： S→(A)|bB®           A →a|aB®            B→A a b® 1. (10分)构造文法的LR(0)项目的DFA； 2. (6分)构造SLR(1)分析表； 3. (4分)这个文法是SLR(1)文法吗？请说明是或不是的原因四川大学期末考试试题A (闭卷) (2007-2008学年第2学期) 1. (9分)简答题 (1) 编译器的前端和后端分别包括哪几个阶段？前后端分开有什么好处？   (2) 在建立LL(1)语法分析器的时候，提左因子和消除左递归的目的分别是什么？ (3) 词法分析和语法分析的功能分别是什么？2. (5分)已知字母表∑={a,b,c}，定义在∑上的语言L具有以下特征： (1) 若出现a，则其后至少紧跟两个c； (2) 若出现b，则其后至少紧跟一个c。

 试给出可以产生语言L的正规表达式3. (6分)文法如下， S→(L)|a  L→L,S|S(1)  证明句子(a,(a,a))可以由此文法产生； (2) 构造(1)中句子的分析树4.  (5分)构造如下文法的递归下降分析程序（recursive-descent parser）S→bSa|b5.  (10分)文法如下， Exp→Exp® Op Exp|(Exp)|number ®Op→+|-|* (1) 此文法是否为二义文法？为什么？ (2) 试将文法改写为非二义文法，其中要求运算符Op是左结合的，且*的优先级高于+、-的优先级6.  (20分)已知正规表达式)(a|ba)*(b|a)(1)  使用Thompson构造方法构造对应的NFA； (2) 用子集构造法将得到的NFA确定化为DFA； (3) 将得到的DFA最小化7.  (25分)文法如下， S→(L)|a  L→L,S|S(1) 消除文法左递归； (2) 为所得文法的每个非终结符构造First集和Follow集； (3) 所得文法是LL(1)文法吗？为什么？ (4) 构造所得文法的LL(1)分析表； (5) 写出对输入串))(,(aa进行LL(1)分析的过程。

8. (20分)文法如下， declaration→ type list-var ®type → int|float var -list → id,var -list|id(1) 构造文法的LR(0)项目的DFA；(10分) (2) 构造SLR(1)分析表；(6分) (3) 这个文法是SLR(1)文法吗？如果不是，请说明原因；(4分) 1. 编译的各个阶段 扫描程序(scanner) 在这个阶段编译器实际阅读源程序（通常以字符流的形式表示）扫描程序执行词法分析（Lexical analysis）：它将字符序列收集到称作记号(t o k e n）的有意义单元中，记号同自然语言，如英语中的字词相似  语法分析程序(parser) 语法分析程序从扫描程序中获取记号形式的源代码，并完成定义程序结构的语法分析（syntax analysis），这与自然语言中句子的语法分析类似语法分析定义了程序的结构元素及其关系通常将语法分析的结果表示为分析树（ parse tree）或语法树（syntax tree）  语义分析程序（semantic analyzer） 分析程序的静态语义，包括包括声明和类型检查。

  源代码优化程序（source code optimizer），代码生成器（code generator），目标代码优化程序（target code optimizer）2. 编译器的前端（front end），后端（back end），遍（passes） 扫描程序、分析程序和语义分析程序是前端，代码生成器是后端 编译器发现，在生成代码之前多次处理整个源程序很方便这些重复就是遍（p a s s）  3. 编译器，汇编器和解释器之间的区别     解释程序是如同编译器的一种语言翻译程序它与编译器的不同之处在于：它立即执行源 程序而不是生成在翻译完成之后才执行的目标代码 汇编程序是用于特定计算机上的汇编语言的翻译程序有时，编译器会生成汇编语言以作为其目标语言，然后再由一个汇编程序将它翻译成目标代码  4. 扫描，分析（语法，词法）的任务 扫描的任务是将源程序读作字符文件并将其分为若干个记号     扫描程序的任务是从源代码中读取字符并形成由编译器的以后部分（通常是分析程序）处理的逻辑单元 由扫描程序生成的逻辑单元称作记号（ t o k e n） 分析的任务是确定程序的语法，或称作结构 分析程序的任务是从由扫描程序产生的记号中确定程序的语法结构，以及或隐式或显式地构造出表示该结构的分析树或语法树 5. 上下文无关文法，最左推导，BNF，EBNF，乔姆斯基文法层次     上下文无关文法说明程序设计语言的语法结构，利用了与正则表达式中极为类似的命名惯例和运算。

二者的主要区别在于上下文无关文法的规则是递归的（recursive） 最左推导（ leftmost derivation）是指它的每一步中最左的非终结符都要被替换的推导 最右推导（ rightmost derivation）则是指它的每一步中最右的非终结符都要被替换的推导最左推导和与其相关的分析树的内部节点的前序编号相对应；而最右推导则和后序编号相对应  最左推导的一个例子：书p73相关题目：3.3  EBNF中注意重复和可选的表示方法，语法图 6. 句子，句型，文法所定义的语言，分析树，抽象语法树  7. 自顶向下，自底向上语法分析    自顶向下（t o p - d o w n）的分析算法通过在最左推导中描述出各个步骤来分析记号串输入之所以称这样的算法为自顶向下是由于分析树隐含的编号是一个前序编号，而且其顺序是由根到叶分为两类：回溯分析程序（ backtracking parser）和预测分析程序（ predictive parser）    自底向上的分析程序有两种可能的动作(除“接受”之外)： 1) 将终结符从输入的开头移进到栈的顶部 2) 假设有B N F选择A→a，将栈顶部的串a归约为非终结符A。

  8. 为什么要解决公因子，左递归 当有公因子存在时，不能立即区分出文法规则右边的选择 当有左递归时，将导致一个无限循环  9. 写正则表达式，构造NFA，DFA，最小化（按照算法做） 构造NFA（使用Thompson结构）: 书P45-47将NFA转换成DFA（最小子集法）： ε- 闭包（ε - c l o s u r e）是可由ε转换从某状态或某些状态达到的所有状态集合，它总是包含状态本身  子集构造：参见Chapter_two(2).ppt 相关题目：2.1，2.12，2.16 10. 写最左推导，最右推导，画分析树和抽象语法树 相关题目：3.3  11. 写出给定程序的语法树，抽象语法树 相关题目：3.3  12. 说明文法有二义性 可生成带有两个不同分析树的串的文法称作二义性文法（ambiguousgrammar） 相关题目：3.2  13. 写出给定程序的递归下降分析程序（可能用伪代码，C程序），构造语法树 注意事项：在处理产生式A→ε时，可以忽略，或者使用A的Follow集合不要试图去匹配ε（不然要被拉去登记的） 相关题目：4.2，4.3，4.4  14.  给定文法：消除左递归，提取公因子，求First Set，Follow Set，说明是否是LL(1)文法，构造LL(1)分析表，给出一个输入分析的动作 相关题目：4.7，4.8，4.1015. 给定文法：求LR(0)的DFA，构造LR(0)和SLR(1)的分析表，说明是否是LR(0)或SLR(1)文法（描述冲突），给定一个输入，写出LR(0),SLR(1)的分析步骤 相关题目：5.1，5.3   16. 算法（写伪代码） 3种DFA代码，LL(1)算法，LR(0)算法，SLR(1)算法，消左递归，提公因子，构造First，Follow集合 DFA代码（英文书P63，中文P42）LL（1）算法（英文书P155，中文P115） LR（0）算法（英文书P207，中文P158） SLR(1) 算法（英文书P210，中文P160） 左递归（英文书P159，中文P119） 公因子（英文书P164，中文P122） 构造First Set（英文书P168，中文P126） 构造Follow Set（英文书P173，中文P130） 参见书本。