编译原理
2.1 引论?
1.从高级语言源程序到目标机器代码的全过程是怎样的？
??源程序首先要经过预处理器，预处理器将存储在不同文件中的源程序聚合在一起，并把宏转换为原始语句。经过预处理后的源程序交与编译器，编译器将其编译为汇编语言程序，汇编语言程序之后被汇编器汇编为可重定位的机器代码，该机器代码经由链接器以及加载器处理后变为最终的目标机器代码
2.编译程序的工作包括哪些方面？它们具体的含义是什么？?
? 编译程序的工作包括：词法分析、语法分析、语义分析和中间代码生成、优化以及目标代码生成
??词法分析的任务是扫描源程序的字符，识别出各个单词，确定单词的类型，将识别出的单词转换成统一的机内表示（词法单元token形式）
??语法分析从词法分析器输出的token序列中识别出各类短语，并构造语法分析树，语法分析树描述了句子的语法结构
??语义分析的任务是收集标识符的属性信息并进行语义检查
??中间代码生成的任务是对语法分析识别出的各类语法范畴，分析其含义，进行初步翻译，产生介于源代码和目标代码之间的一种代码
??优化的任务是对中间代码进行加工变换，为的是在最后阶段能产生更为高效的目标代码
??目标代码生成的任务是把经过优化的中间代码转化成特定机器上的低级语言代码
3.什么是终结符、什么是非终结符???
终结符是文法所定义的语言的基本符号，有时也称为token，非终结符是用来表示语法成分的符号，有时也称为语法变量
2.2 词法分析??
1.什么是正则表达式？??
正则表达式是对字符串操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。
2.什么是有穷自动机、确定有穷自动机、不确定有穷自动机??
有穷自动机是对一类处理系统建立的数学模型，这类系统具有一系列离散的输入输出信息和有穷数目的内部状态。系统只需要根据当前所处的状态和当前面临的输入信息就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变
??确定有穷自动机是一种特殊的有穷自动机，它的任意一个状态对于任意一个输入符号有且只有一个转换。
??不确定有穷自动机是说当一个状态面对一个输入符号的时候，它所转换到的可能不只一个状态，可以是一个状态集合
3.什么是有穷自动机定义的语言？
给定输入串x，若存在一个对应于串x的从初始状态到某个终止状态的转换序列，则称串x被该有穷自动机接收由一个有穷自动机接收的所有串构成的集合称为是该有穷自动机定义的语言
4.词法分析阶段可以检测到哪些错误类型？是如何检测的？对错误的处理过程是什么？??
词法分析阶段可以检测到的错误类型有：单词拼写错误、非法字符。
词法错误检测的方法是：若当前状态与当前输入符号在转换表对应项中的信息为空，则报错，调用错误处理程序错误处理程序将查找已扫描字符串中最后一个对应于某终态的字符，若找到，将该字符与其前面的字符识别成一个单词，然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词。若未找到，则确定出错，采用错误恢复策略。
??简单的一种错误恢复策略称为恐慌模式，它从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止
2.3 语法分析
1.什么是上下文无关文法？??
上下文无关文法就是说这个文法中所有的产生式左边只有一个非终结符
2.什么是语法分析树？??
一颗语法分析树是一个推导的图形表示。在推导中出现的每一个非终结符号都在树中有一个对应结点。一个结点的子节点就是在推导中用来替换该节点对应的非终结符号的文法符号串。
3.什么是二义性文法？??
若一个文法的某些终结符号串有两颗或多颗语法分析树，或者等价地说有两个或多个最左推导/最右推导，那么这个文法就称为二义性文法。在实践中的大多数情况下，我们可以对一个二义性文法进行重新设计，使它变成一个描述相同语言的无二义性文法。然而，有时使用二义性文法并应用一些技巧可以得到更加高效的语法分析器
4.什么是自顶向下和自底向上语法分析？??
语法分析器通常可以按照它们的工作方式分为自顶向下的（从文法的开始符号出发，从顶部开始构造语法分析树）和自底向上的（从构成语法分析树叶子节点的终结符号串开始，从底部开始构造语法分析树）。自顶向下的语法分析器包括递归下降语法分析器和LL语法分析器，而最常见的自底向上语法分析器是LR语法分析器
5.什么是推导？什么是归约？什么是最左推导？什么是最右推导？自底向上的分析和自顶向下的分析分别采用什么推导或归约方式？??
推导是从开始符号开始，通过使用产生式的右部取代左部，最终能产生语言的一个句子的过程。在最左推导中，总是选择每个句型的最左非终结符进行替换，在最右推导中，总是选择每个句型的最右非终结符进行替换
??归约是推导的逆过程，即从给定的源语言的句子开始，通过规则的左部取代右部，最终达到开始符号的过程
??自底向上的分析采用最左归约的方式，自顶向下的语法分析采用最左推导方式
2.4 语法制导的翻译
1.语法制导翻译指的是编译的哪几个阶段？??
语法制导翻译包括语法分析、语义分析、中间代码生成三个阶段
??语法制导翻译使用上下文无关文法（CFG）来引导对语言的翻译，是一种面向文法的翻译技术
2.5 中间代码生成??
1.常见的中间代码形式有哪些？四元式、三元式、逆波兰式
2.6 运行时刻环境??
1.数据的存储分配策略是怎样的？??
对于那些在编译时刻就可以确定大小的数据对象，可以在编译时刻就为它们分配存储空间，这样的分配策略称为静态存储分配。反之，若不能在编译时完全确定数据对象的大小，就要采用动态存储分配的策略，即在编译时仅产生各种必要的信息，而在运行时刻，再动态地分配数据对象的存储空间。动态存储分配又可分为栈式存储分配与堆式存储分配
??静态和动态存储分配分别对应编译时刻和运行时刻
2.程序运行时内存的划分是怎样的？??
内存分为静态代码区、静态数据区以及动态数据区。动态数据区又分为栈区、堆区以及空闲内存区
3.适合静态存储分配的语言必须满足的限制条件是什么？常用的静态存储分配方法有哪些？??
适合静态存储分配的语言必须满足：数组上下界必须是常数、不允许过程的递归调用以及不允许动态建立数据实体
??常用的静态存储分配方法有：顺序分配法、层次分配法。顺序分配法按照过程出现的先后顺序逐段分配存储空间，各过程的活动记录占用互不相交的存储空间。层次分配法通过对过程间的调用关系进行分析，凡属无相互调用关系的并列过程，尽量使其局部数据共享存储空间
4.什么是栈式存储分配？??
有些语言使用过程、函数或方法作为用户自定义动作的单元，几乎所有针对这些语言的编译器都把它们的运行时刻存储以栈的形式进行管理，称为栈式存储分配
??这种安排不仅允许活跃时段不交叠的多个过程调用之间共享空间，而且使得过程的非局部变量的相对地址总是固定的，和过程调用序列无关
2.7 代码生成
1.什么是流图？
??流图是程序的一种图形化表示方式。其中图的结点是基本块，而图的边显示了控制流如何在基本块之间流动
2.什么是窥孔优化？
??窥孔是程序上的一个小的滑动窗口，窥孔优化是指在优化的时候，检查目标指令的一个滑动窗口（即窥孔），并且只要有可能就在窥孔内用更快或更短的指令来替换窗口中的指令序列
————————————————
版权声明：本文为CSDN博主「小灵宝」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44709990/article/details/114759334