引论

什么是编译原理

1.计算机编译语言的层次：

机器语言：可以直接被计算机直接理解；
汇编语言：引入助记符，但是还是难以被直接理解，由汇编语言到机器语言是通过汇编的形式；
高级语言：能直接理解的，由高级语言到汇编语言或者机器语言是通过编译的形式；

编译程序补充说明

1.编译程序的功能：是把高级语言翻译成等价的目标程序，编译程序把”源语言”翻译成二进制文件的”目标语言”的过程，目标程序可以独立源程序运行（注意编译和运行是分俩个阶段的）；

2.编译器的系统位置以及语言处理流程：源程序=>经过预处理源程序=>汇编语言程序=>可重定位机器码=>目标机器代码；

预处理器：把存储在不同文件中的源程序聚合在一起，把被成为宏的缩写语句转换为原始语句；
编译器：如上；
汇编器：进行可重定位，可重定位指的是在内存中存放的起始位置L不是固定的，而起始位置+相对地址=绝对地址；
链接器/加载器：其中加载器修改可重定位地址，将修改后的指令和数据放到内存中适当位置，而链接器将多个可重定位的机器代码文件连接到一起以及解决外部内存地址问题；

编译系统的结构

1.编译过程的划分：分俩批次

第一批次：分析/前端部分，与源语言相关；
- 词法分析：分析各个短语的词性；
- 语法分析：划分句子，也就是句子的中的短语；
- 语义分析：就是分析源语言的语义，分析各个短语在句子中占什么成分，语义分析的结果一般直接用中间代码表示，所以这俩个可以一起实现，同时语法分析时分许句子时同时结合语义分析，所以该三个阶段可以一起实现，这个技术被称为语法制导翻译；
- 第二批次：综合/后端部分，与目标语言相关，中间代码生成其实也属于前端部分；

中间代码生成；
代码优化：代码优化一般中间代码和目标机器代码都需要优化；
目标代码生成；

解释程序

1.解释程序：解释程序是一种语言处理程序，在词法、语法和语义分析上基本同编译过程一致，但是运行用户程序时，它是直接执行源程序或者说源程序的内部形式（中间代码），解释程序不会生成目标代码；

编译程序和解释程序的区别

1.区别：

相同点：
- 都有相同的词法、语法、语义分析过程；
不同点：
- 编译程序运行速度会更快，编译程序是生成目标代码后再运行的，而解释程序是一边翻译一边执行；
- 编译程序安全性更高，因为编译程序生成的目标代码是二进制形式的；
- 编译程序不参与用户程序运行控制，而解释程序参与；
- 解释程序不需要同机器码打交道，实现起来比较简单，且便于在不同平台上移植；

前端部分简单介绍

1.词法分析主要任务：从左到由逐行扫描程序的字符，识别出各个单词，确定单词的类型，将识别出的单词转换成统一的机内表示——语法单元(token)形式，token<种别码，属性值>，第一分量表示种别码，第二个表示值；

单词类型	种别	种别码
关键字/保留字	if,else,then	一词一码
标识符	变量名、数组名、记录名	多词一码
常量	整形、浮点型、字符型、布尔型	一型一码
运算符	算数、关系、逻辑·	一词移码或者一型一码
界限符	; () = {} …	一词一码

2.语法分析简单介绍：语法分析器从词法分析器输出的token序列种识别出各类短语，并构造语法分析树；

3.语义分析的主要任务：

第一个任务：收集标识符的如下主要属性信息，存储在符号表中：
- 种属（Kind）
- 类型（Type）
- 存储位置和长度
- 值和作用域
- 参数和返回值信息
第二个任务：语义检查；
- 变量或者过程未经申明就使用；
- 变量或者过程名重复声明；
- 运算分量类型不匹配；
- 操作符和操作数之间的类型不匹配；

中间代码生成及编译器后端

文法和语言

文法的概述

1.文法的定义：文法是语言的抽象规则（例如我们的语言都是遵守主谓宾这个文法）；

2.文法的描述：

语法规则构成说明：通过建立一组规则，来描述句子的语法结构，例如：
- <句子>::=<主语><谓语>
- <主语>::=<代词>|<名词>
- <谓语>::=<动词><直接宾语>……..
规则推导：有了一组规则，可以按照一定的方式来推导产生句子（方法从一个要识别的符号开始推导，即用相应规则的右部去替代规则的左部）
- <句子> => <主语><谓语>
- <主语><谓语> => <代词><谓语>

符号和符号串

1.字母表：字母表是元素的非空有穷集合，字母表中的元素被称为符号，字母表的运算有乘积、n次幂、正闭包、克林闭包；

2.符号串：由字母表中符号组成的任意又穷序列称为符号串（例如011101是字母表{0,1}上的字符串）；

空串：是长度为0的串，用ε表示；
连接运算：将俩个串进行相连；
幂运算：串的0次幂等于ε，否则S^n = S^n-1*S；

文法的定义

1.文法G=（Vn,Vt,P,Z）

Vn：非终结符，是用来表示句子成分的符号，有时也称为“语法变量”；
Vt：终结符，是文法所定义的语言的基本符号，有时也称为token；
P：产生式或规则的集合，描述了将终结符和非终结符组成串的方法，产生式的一般形式：α→β，α称为产生出式的头或者左部，β称为产生式的体或者右部；
Z：开始符合（Z∈Vn），表示文法中的最大语法成分；

例如：文法G=（Vn,Vt,P,S）,Vn={S}，Vt={0,1}，P={S=>0S1,S=>01}，S为开始符号；

2.符号约定：

终结符：a、b、c；
非终结符：A、B、C；
文法符号：X、Y、Z；
终结符号串：u、v……z；
文法符号串：α、β；

语言的定义

1.推导：用产生式的右部替换产生式的左部，是一个自顶向下的过程；

2.规约：用产生式的左部替换产生式的右部，是一个自底向上的过程，规约是推导的逆过程；

3.句子和句型：句子是推导出后只包含终结符得就是句子，否则是句型；

文法的分类

1..最左推导和最右推导：没搞懂；

3.文法的等价：若L(G1)=L(G2)，则称文法G1和G2是等价的，既然说文法是等价的，所以文法可以是多重的，不同的文法实现同样的功能；

1.文法的类型：低级文法包含高级文法，高级文法一定是低级文法

0型文法（短语文法）：对于产生式α→β的结构中，α至少含有一个非终结符；
1型文法（上下文有关）：对于产生式式α→β，都有|β|>=|α|，仅仅S→ε除外；
2型文法（上下文无关）：对于产生式α→β，α只能是非终结符，产生式型的形式可变形为A→β；
3型文法（正规文法）：
- 左线性文法：A→wβ | A→w
- 右线性文法： A→βw | A→w

CFG的分析树

1.二义性文法：

定义：如果一个文法可以为某个句子生成多颗分析树，则称这个文法时二义性的；
判定：大多数时候我们都希望文法不是歧义性的，可以给出一组充分条件，满足这组充分条件的文法是无二义性的；

正则表达式

1.运算类型：

*：克林闭包；
连接；
|：或运算；

递归文法

例如（定义变量）：变量名 x,y,z;,可以推理得：S=>aAb，而A=>B|BcA;

例如（加减乘除）：E=>E+T|T;T=>T*F|F;F=>(E)|a；

词法分析

有穷自动机的分类（FA）

1.有穷自动机（FA）：是一个五元组 M：

有穷状态集；
输入字母表；
转换函数；
开始状态；
接受状态|终止状态；

2.区别：不确定的有穷自动机（NFA）和确定的有穷自动机（DFA）区别在于转换函数可以有多个能到达的状态集合；

从正则表达式到有穷自动机

[![正则表达式到又穷自动机]
(https://s1.ax1x.com/2022/06/09/XyQ3Of.md.png)]
(https://imgtu.com/i/XyQ3Of)

由NFA到DFA的转换

1.将NFA的状态组成一个新的状态，如以下r=aa*bb*cc的表示
[![由NFA到DFA]
(https://s1.ax1x.com/2022/06/09/XyQsmT.md.png)]
(https://imgtu.com/i/XyQsmT)

2.子集构造法实例：
[![带有ε的NFA到DFA]
(https://s1.ax1x.com/2022/06/09/XyQbAe.md.png)]
(https://imgtu.com/i/XyQbAe)

自顶向下语法分析方法（重点）

自顶向下分析概述

自顶向上优先分析

LR分析

语法制导的语义计算

静态语义分析和中间代码生成

运行时存储组织

代码优化和目标代码生成

1.代码优化：

常数合并：编译时将常数运算进行合并；
常数传播：
代数化简：消掉没有必要的代数，例如x+0 = x；
削弱运算强度：将高复杂度度运算替换为低复杂度运算；

补录

tracert -d 查看网络路节点

1.编译器的定义
2.考PL/0语言
3.考LL(1)
4.几天的课：运行时存储器组织、优化和目标代码生成，拍照的东西
5.上次课：抽象语法树和利波兰式
6.今天的课：运行时存储器组织、优化和目标代码生成，拍照的东西
7.分析设计题，老师最后讲

复习

文法和语言

1.文法：

文法是语言的形式化的描述工具；
文法是一个四元组；
文法是等价的，可以进行改造，文法分类成0、1、2、3型文法；
推导完成的叫句子，中间的过程叫句型，逆推导的过程叫归约；
同一个文法在推导过程中语法树是否具有二义性，是否进行改造；

A卷考试重点

写无聊语言的杀，啥也不写的杀，下个学期的补考也杀，带*号的题目不全；

选择题-（40）

1.期中考试题（GCC）
2.以及目标代码生成、代码优化

解答题（30）

1.何为编译器，编译器的组成部分，编译器的各组成部分作用；

a、编译器是将高级语言翻译成等价的目标语言的程序；

b、编译器由词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成组成：

c、如下：

词法分析：主要将字符从左至右读入源程序，对构成源程序的字符进行扫描和分解；
语法分析：在词法分析的基础上将单词序列分解为各类语法短语，这中语法短语也称为语法单位，可表示为语法树；
语义分析：审查源程序有无语义错误，为代码生成阶段收集类型信息；
中间代码生成：在进行语法分析和语义分析后，有的编译程序变成一种内部表现形式，这种表现形似就是中间代码；
代码优化：对中间代码进行变化或者改造，目的是使生成的目标代码更高效；
目标代码生成：将中间代码变换为特定机器上的绝对指令或者重定位的指令代码或者某种汇编指令代码；

2.何为PL/0语言，试用PL/0语言描述xx算法；

a、如下：

PL/0语言是Pascal的一个子集；
PL/0语言编译系统由PL/0编译程序和P-code解释程序组成；

3.如何判断一个文法是LL(1)的，若有文法xx，试将其改造成LL(1)文法；

a、如下：

文法不含左递归；
产生式的候选首符集俩俩不相交；

4.请结合C语言说明函数参数传递的方式和不同；

a、如下：

按值传递：将实参的值拷贝给形参、有内存分配和释放、不改变外部的值；
地址传递：将形参是指针变量，指针的值拷贝形参指针的值，有内存分配和释放、改变外部值；
引用传递：形参是实参的引用，无内存分配，改变外部值；

5.给出表达式的抽象语法树和利波兰式；

6.请简述代码生成时的指令调度；代码生成，寄存器

分析设计题（30）

给出文法：S→A，A→BA，A→c，B→aB，B→b
1.构造活前缀DFA
2.构造LR(0)分析表，Action表和Goto表；
3.给出输入串，写出分析过程（状态栈）

例题：

B卷考试重点

解答题（70）

1.何为编译器，解释编译器的组成，解释各个编译器的作用；
2.linux系统在C语言的编译过程；
3.何为FA、NFA、DFA，以及将DFA转换成DFA；
4.何为文法，举例说明文法的分类；
5.LR(0)的分析表
6.请把利波兰式复原成为算数表达式，并且将抽象语法树画出来；
7.请生成下列语句的目标代码(x=x+1)；