软考——软件设计师：第六章：程序设计语言与语言处理程序（编译原理）考点总结（完整篇）
1.主要内容
2.编译过程
2.1 编译过程概述
编译程序的功能是把某高级语言书写的源程序翻译成与之等价的目标程序（汇编语言或机器语言）。
2.2 词法分析
词法分析阶段是编译过程的第一个阶段，这个阶段的任务是对源程序从前到后（从左到右）逐个字符地扫描，从中识别出一个个“单词” 符号。
“单词”符号是程序设计语言的基本语法单位，如关键字（或称保留字）、标识符、常数、运算符和分隔符（如标点符号、左右符号）等。词法分析程序输出的“单词”常以二元组的方式输出，即单词种别和单词自身的值。
2.3 语法分析
语法分析的任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”、“语句”和“程序”等。词法分析和语法分析在本质上都是对源程序的结构进行分析。
2.4 语义分析
语义分析阶段分析各语法结构的含义，检查源程序是否包含静态语义错误，并收集类型信息供后面的代码生成阶段使用。
只有语法和语义分析都正确的源程序才能翻译成正确的目标代码。
2.5 中间代码生成
中间代码生成阶段的工作是根据语义分析的输出生成中间代码。“中间代码”是一种简单且含义明确的记号系统，可以有若干种形式，它们的共同特征是与具体的机器无关。
最常用的一种中间代码是与汇编语言的指令非常相似的三地址码。
2.6 代码优化
由于编译器将源程序翻译成中间代码的工作是机械的、按固定模式进行的，因此，生成的中间代码往往在时间上和空间上有较大的浪费。当需要生成高效的目标代码时，必须进行优化。
优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。
2.7 目标代码生成
目标代码生成阶段是编译器工作的最后一个阶段。这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。这个阶段的工作与具体的机器密切相关。
3.文法定义
3.1 文法类型
3.2 语法推导树
3.3 有限自动机
3.3.1 有限自动机例题
这类题相对于正规式的题要简单的多，没有什么技巧，直接按照四个选项给出的表达式去一步一步的推就可以了！！！
由于A是初态，C是终态，我们代入验证四个选项中哪一个可以由初态走到终态，即为正确答案。
A选项：0000，从A开始，由0到达B；再由0，仍然到达B（因为在B这里，0只能是以自身循环），所以0000无法识别。
B选项：1111，从A开始，由1到达A；再由1，仍然到达A（因为在A这里，1只能是以自身循环），所以1111无法识别。
C选项：0101，从A开始，由0到达B；再由1，到达C；再由0，到达B；最后由1，到达终态C，所以0101可以识别。
D选项：1010，从A开始，由1到达A；再由0，到达B；再由1，到达C；最后由0，到达B，所以1010无法识别。
3.4 正规式
3.4.1 正规式例题
上面这道例题，其中的丨表示“或”，*表示重复 [0，+∞）次。那么对于文法G[S]的分析如下：????????????
第一空：????????????
A选项：首先S→aA丨bB，可以推出aA；根据A→bS丨b，可以推出abS；根据S→aA丨bB，可以推出abaA；根据A→bS丨b，可以推出ababS；可以发现这样的正规式是一个以ab循环多次的字符串，即可以推出ababab。
B选项：首先S→aA丨bB，可以推出bB；根据B→aS丨a，可以推出baS；根据S→aA丨bB，可以推出babB；根据B→aS丨a，可以推出babaS；可以发现这样的正规式是一个以ba循环多次的字符串，即可以推出bababa。
C选项：首先S→aA丨bB，可以推出aA；根据A→bS丨b，可以推出abS；根据S→aA丨bB，可以推出abbB；根据B→aS丨a，可以推出abbaS；根据S→aA丨bB，可以推出abbaaA；根据A→bS丨b，可以推出abbaab。
D选项：首先S→aA丨bB，可以推出bB；根据B→aS丨a，可以推出baS；根据S→aA丨bB，可以推出babB；此时根据B→aS丨a，无法推出babb，因为B要么是aS、要么是a，不可能出现b这种情况，所以D选项是错误的！！！
第二空：意思是说这四个选项中哪一个可以将第一空中文法G[S]可以识别的三个选项都表示出来：????????????
A选项：（a丨b）*，它可以将由a或b组成的任意串表达出来，也就是这样：a、ab、baa、babba这些都可以。那么它所表达的范围已经超出了文法G[S]可以识别的范围，它无法与文法G[S]保持等价，所以排除A选项。
B选项：（ab）*，它可以将由ab组成的串循环表示 [0，+∞) 次，也就是这样：ab、abab、abababab这些都可以。但是它无法表达第一空的B、C两个选项，因为它全部是以ab这样的形式表达的。所以排除B选项。
C选项：（ab丨ba）*，它可以生成任意数量的ab串或ba串，也就是这样：ababab、bababa或者abbaab这些都可以，它所表达的范围与文法G[S]完全等价！！！
D选项：（ab）*（ba）*，它的意思是：先来若干个ab串、再来若干个ba串，也就是这样：ababab、bababa、ababbaba这些都可以，但是它无法表示第一空的C选项。所以排除D选项。
4.表达式
将表达式（a-b）*（c+5）构造成树的步骤为：括号不能出现在树中；按照表达式的计算顺序来依次构造！！！
第一步肯定是要计算（a-b），之后再计算（c+5），最后将这两者的结果相乘，所构造的树即为上图这种形式：????????????
那么将树构造出来之后，对于前缀、中缀、后缀，无非就是二叉树的的前序、中序、后序遍历的过程：a b - c 5 + *。
如果说这里将表达式中的括号去掉：a - b * c + 5，那么所构造的树就不一样了，应该是下图所示的形式：????????????
5.函数调用——传值与传址
5.1 传值调用
采用传值调用方式时，形参取的是实参的值，修改了形参并不会改变实参的具体值。对于上面这段代码，调用swap函数的语句swap（a，b），进入函数体void swap（int x，int y）的传值调用，虽然函数体内x和y的值进行了交换，第一行打印x和y的值分别为4、3，回到主函数之后，这里因为是传值调用并未改变实参a、b的值，所以a仍然为3，b仍然为4。
5.2 引用调用（传址调用）
采用引用调用方式时，形参取的是实参的地址，即修改了形参实际上也就修改了实参（换句话说，形参与实参在这里是一样的）。对于上面这段代码，调用swap函数的语句swap（a，b），进入函数体void swap（int &x，int &y）的引用调用，函数体内x和y的值进行了交换，第一行打印x和y的值分别为4、3，回到主函数之后，这里因为是引用调用，修改了形参x、y的值，实际上也就修改了实参a、b的值，所以a为4，b为3。
6.各种程序语言特点
6.1 主要特点
①C：指针操作能力强，高效。
②C++：面向对象，高效。
③C#：面向对象，中间代码，.Net。
④Java：面向对象，中间代码，跨平台。
⑤Python：解释型，面向对象，胶水语言。
⑥Fortran：科学计算，执行效率高。
⑦Pascal：为教学而开发的，表达能力强，Delphi。
⑧Lisp：函数式程序语言，符号处理，人工智能。
⑨Prolog：逻辑推理，简洁性，表达能力，数据库和专家系统。
6.2 语言分类
①编译型：逐段编译，生成可执行程序exe等，执行效率高。
②解释型：逐句，解释器，跨平台，执行效率低。
7.数据类型与程序控制结构