编译原理期末复习

编译原理

文章中的习题都是在B站视频编译原理中截图得到的。个人觉得讲的非常好，建议期末速成的同学看一看。

第一章

1. 编译程序的基本结构

• 编译过程
  从输入源程序开始到输出目标程序为止的整个过程。可分为五个阶段：词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成

2. 编译器（编译程序）的体系结构（实现方法）

从分遍的角度可把编译器分为一遍的和多遍的。一遍指对源程序或源程序的中间结果从头到尾扫描一次，生成目标代码。多遍指对源程序或源程序的中间结果从头到尾扫描多次，生成目标代码。一遍：高效，编译速度快。但是设计复杂。多遍：算法清晰实现起来简单，但是时间长。

• 一遍扫描的好处
  避免重复性工作，编译速度快。
• 一遍扫描的缺点
  发生语法或语义错误时，前面所作的工作可能要半途而废。
  不便于分工，不便于优化，算法不清晰。
• 多遍扫描的好处
  节省内存空间，提高目标代码质量，使编译的逻辑结构清晰，算法清晰。
• 多遍扫描的缺点
  编译时间较长。
  注：在内存许可情况下，还是遍数尽可能少些为好。

第二章

1. 给出一个语言需求，给出它的文法定义

2. 给出一个目标字串，进行推导

   

3. 请说明递归文法存在的必要性

   可以通过有限的规则去定义无穷的集合

4. 有哪些类别的递归文法,缺点，如何避免

   左递归和右递归。对于自上而下语法分析的时候，左递归会无穷的循环下去，没有出口，右递归没有缺点。解决：使用定理二，把左递归转换成右递归。

5. 求出给定句型的短语，直接短语，句柄（2.5.1）

   

• 短语为T+T*F+i , T*F+i , T , T*F , i
• 直接短语： T , T*F , i
• 句柄：T

6. 化简文法

相关知识点

• 推导，规约，语法树

• 最左推导例子

• 二义性例子

第三章

1. 词法分析的工具有几种

   自动机，正规式，正规文法。这三者是可以相互转换的。自动机内部有三种形式（第二个问题）

2. 自动状态机的三种表示方法

• 自动机模型，状态转换图，状态转换矩阵
• 自动机模型是理解算法的基础
• 状态转换图是人直接理解的依据
• 状态转换矩阵是给机器来识别字符的

3. 正规式，正规文法，NFA,DFA在词法分析中起到什么作用

   • 正规式和正规文法是用来对词法分析需求进行泛形式化或形式化的描述，也可以快捷的转换成NFA。

   • NFA提供了将正规式或正规文法转换成自动机的便捷途径，有算法可以自动实现这种转换。

   • DFA是词法分析器的实现模型，是真正能够实别单词的基础，NFA到DFA的准换也是有算法可以自动完成的，从软件工程角度，正规式或正规文法到NFA，DFA形成了一个一整条的自动转换过程。

4. 它们之间的关系

   • 正规式,正规文法以及自动机之间是可以相互转换的，是等价的。
   • 自动机模型是词法分析器的实现基础。状态状态图和状态转换矩阵都是自动机的描述方法。前者主要由人使用，后者由机器使用，用于识别单词

5. NFA和DFA定义的差别

相关知识点

• 右线性文法

• 状态转换矩阵，三型文法（右线性文法）

• NFA的确定化和最小化

• 第二个例子

• 正规式

第四章

1. 自上而下语法分析存在的问题，如何解决
   • 文法中有左递归，会导致分析过程没有递归出口而一直递归下去。
   • 有多个候选式的时候，会因为不知道选择哪一个而出现回溯，造成分析过程时间和空间上的低效。
   • 首先，消除文法中的左递归。其次，提取公共左因子。第三，构造非终结符的first集和follow集。第四，按照first集和follow集构造LL1分析表。让语法总部程序按在下推自动机模型中按照LL1分析表来选择性推导分析。

相关知识点

• 消除左递归

• first集和follow集

开始符号的follow集为#

• 是否为LL1文法

• 构造LL1文法

• LR0分析表

移进项目后边为终结符，待约项目后边为非终结符。

• SLR（1）文法

• LR(1)文法

• LALR文法

第六章

1. LR分析器的实质是什么？LR分析表的实质是什么？

   LR分析器是下推自动机，LR分析表是DFA。

2. LR分析器和LL1分析器的区别

   • 结构上的差别：LL1是单栈，LR是双栈。下推自动机中的总控程序和分析表也有差别。
   • 工作原理上的差别：
     • 计算方法：LR是移进规约，LL1是推导和匹配
     • 计算方法依赖的数据源的差别：LR以来的是LR分析表，LL1依赖的是LL1分析表。
     • 对输入带分析方式的差别：LL1把输入带上面的内容移到下推栈，如果某个字符可以推导就选择下推栈，LR根据栈顶状态查表，决定做什么动作
     • 分析精准度上的差别：如果发现一个输入程序出错，LL1分析器对错误的定位不是很精准，LR分析器能够精准定位到出错的位置。

3. LR0，SLR，LR1识别精准度之间的差别

   • 在填写LR分析表时，对规约项的填写是逐步精准。
   • LR0是对所有终结符都填写规约项
   • SLR是对规约到的非终结符的随符集中所有字符填写规约项
   • LR1是对候选式的随符集中所有字符（搜索符）填写规约项
   • LR0和SLR分析表的规模一样，所以分析时的算法复杂度一样，空间复杂度一样
   • LR1分析表的规模比SLR的规模大很多，所以分析时的算法复杂度和空间复杂度都会有所增加，从而对目标机器的性能要求也有所提升。

其他

翻译型（编译型） 二进制文件 exe,dll

解释型 编译后不能直接运行，也可以说是 边编译边运行的语言

C#是编译型，直接编译成二进制文件

Java，python是解释型

C是编译型