编译原理笔记(课堂ppt).md

## Compilers
### 题型分布
综合体：1.NFA - DFA 2.语法树 3.LL1分析 4.LRK分析
计算题：1.文法和语言 2.中间代码 3.正规式NFA等价转换 4.参数传递 5.语义子程序 属性文法 6.划分基本块 画出流图



### 参考书目
### 课程简介
* 主要讲十章
* 课时分配
## Week 1
`2022/8/29`
## 一、引论
#### 1.1翻译程序 定义
* 翻译程序：将源程序转换成目标程序的程序，是汇编程序，编译程序以及各种变换程序的总称。
* 编译程序：将高级语言翻译成**低级语言程序**（汇编语言或机器语言）
* 目标程序：可以是介于源程序和机器语言之间的**“中间语言”**
​
* **目标程序**：对源程序逐条解释执行，**不生成目标代码**
* 翻译程序：汇编程序、编译程序、解释程序
* 编译程序 - C语言
* 解释程序 - python
* 编译-解释程序 Java
##### 课堂习题
* **汇编程序**相对编译程序**工作更简单**
* **解释程序**跟适合**规模较小**的程序
****
#### 1.2编译过程和编译程序的结构
* 编译过程： 将高级语言翻译成**等价目标程序**的过程。
* 词法分析 - 语法分析 - 语义分析 - 中间代码生成 - 代码优化 - 目标代码生成
##### 编译过程
##### 1.词法分析
* 分析和识别出来单词
* 输出单词列表

##### 2.语法分析


##### 3.语义分析
* 进行语义审查
* 这个10的高精度转化就是语义分析完成的

##### 4.中间代码的生成
* 便于优化
* 便于移植
* 例题

##### 5.代码优化
* 为了得到高质量（省时间、省空间）的程序。
##### 6.目标代码生成
* 绝对指令代码：直接装入内存中确定的位置
* 可重定位的指令代码：需要时装入内存
* 汇编指令代码
* 结构图
* 六个阶段 八个功能

##### 表格管理 出错处理
表格管理：表示编译程序具有表格管理功能1
出错处理： 语义错误不一定能全部找到
##### Def
###### 遍
遍：从头到尾扫描一次成为一遍
###### 前端后端
前端：与源程序有关的部分，即编译过程的前五个部分
后端：与目标机有关的部分，即目标程序代码生成和优化
##### 编译程序结构

## Week 2
`2022/9/5`
## 二、文法和语言

#### 2.1语言概述
* 语言：是在某个特定的字母表上的符号串组成的集合。
* 是由句子组成的集合，是由一组记号组成的集合。
* 语法：构成语言句子的各个记号之间的组合规律
* 语义：表示各个记号的特定含义
* 语用：表示在各个记号所出现的行为中，它的来源、使用和影响
* 形式语言：只考虑语法

#### 2.2符号和符号串
* 字母表：符号的非空有限集合
* 符号：字母表中的元素，不能分解的最小单位
* 符号串：字母表中符号组成的任何又穷序列
* 符号串集合：字母表上的符号串组合成的集合
* 空串：不包含任符号的符号串
​
* 前缀： abc，前缀有 **空串**、a、ab、abc
* 后缀、子串
* 真前缀，真后缀：不和自身相等的非空前缀或后缀

##### 符号串的运算
###### 闭包
#### 2.3文法和语言的形式定义
语言的描述可以是**生成**或**识别**方式
**生成**：BNF范式是一种元语言，用来描述其它语言。
**大写字母A B ... 为非终结符**
{} 可重复
[] 可选项
**识别**的方式描述语言

##### 文法定义

##### 推导定义
有一个文法，存在一对属于V*的任意符号，使得v和w在串头和串尾加上那一对符号后分别等于那个文法
则说w是v的直接推到
* 直接推到 *+: 至少一步推到* ***: 0步或至少一步推到**
**例子**
```markdown
Vn = {A, B}; // 定义大写字母是非终结符 Vt = {a, b}; S = A;
B->a 推导出 Bb => ab
```


##### 句型 句子 语言

当一个语言是无穷的时候一定是**递归**实现的
如果一个语言可以有两种文法表示，则这两个文法称为**等价文法**

#### 2.4文法和语言的分类
* 0型文法，没有要求
* 1型文法，要求右边串长**大于等于**左边
* 2型文法，左部只有一个非终结符 `所有的大写字符 A B C ... 都是非终结符`
* 3型文法，右部没有非终结符，有的话就只有一个终结符B，在右边为右线性

#### 2.5上下文无关文法及其语法树

**语法树**


短语 - 简单短语 - 句柄

##### 必考题 例题
**注意括号也要写**
##### 文法二义性


#### 2.6句型分析

**多余规则**

**有害规则**
## 三、词法分析
**Week7**
`2022/10/10`



### 3.2单词的描述工具
##### 正规式
**例子**
##### 正规文法转化成正规文法
*是闭包
正规式转化成正规文法
### 3.3自动机

##### 有穷自动机


从起始 到终结点 路径就是字符串
若一个点既是初态点又是终态点，则空串是该自动机可接受

例题

##### 不确定的有穷自动机
注意：初态有一个**从外边的射入弧**，终态有一个**同心圆**
##### NFA转换成等价的DFA




###### 例题

##### DFA的简化
**注意：** 一个集合 经过相同符号后到达相同的转态 也可以合并为一个
##### 必考题 例题
##### 正规式和有穷自动机的转换
如果正规式是闭包 空弧不能任意省略掉




## 四、语法分析
### LL(1)文法
##### FIRST集合
###### 例题
可以推到出空 - 就FIRST去空 -- 都能推导出来空就并上一个空
不能推导出空 - 就写一个不写后边的
##### FOLLOW集合
###### 例题
FOLLOW(S), 看右部有哪些有S
有S的右部，看S的右边，如果能推导出空就用First去空并上左边的Follow
不能推到出空就是S右边的First
##### SELECT集合
###### 例题
#### 消除左递归 提取左公因子
#### 表驱动分析法
##### 题型
先进行改写 - 判别是否是LL1文法
##### 例题
**蓝色部分还要并上FOLLOW(S),**
### 作业

## 五、自低向上优先分析
### 自底向上语法分析




### 算符优先分析
只考虑终结符，忽视非终结符

#### 算符文法
OG 算符文法

<=> 符号里面都有一个dot
a优于b，a优先级等于b，并不能说明a b 的关系

算符文法中，任意两个终结符之间**至多**有一种算符优先关系称为**算符优先文法**
a 优先 b， b 优先 a，a b, b a顺序不一样



**第一步**：求firstvt和lastvt
**第二步**：算符优先关系表的构造

**第三步**：算符优先分析算法
栈顶元素a 和 要进入的元素b 没有关系 -> 报错
​ a 进栈
a>b 规约，往栈底找等于的话就一直找，知道找到一个Xi-1 < Xi, 左部出站，右部进栈


##### 例题


### 最左素短语
短语、至少一个终结符、除自身不包含其他素短语



## 六、LR分析





##### LR(0)文法

#### 例题

是LR(0)文法



规约看产生式的右部有几个就弹出几个，然后左部入栈，然后看goto(左边的转态栈号和符号栈)是谁就入状态栈



#### SLR(1)
看移进和左部follow都是空

##### 例题


#### LR(1)分析






#### LALR(1)




### 总结


## 七、语法制导翻译和中间代码生成


### 7.1属性文法




### 7.2语法制导翻译



### 7.3中间代码生成
主要掌握中间代码的表示形式

#### 逆波兰式 必考




先改写为if语句


#### 三元式

任意跳转的用/ ，4用的是/ 不是1

for循环要改写成if语句加上goto语句，

##### 树形表示


##### 间接码表

### 四元式


## 八、符号表


## 九、存储



### 9.3参数传递
这个存储4分，存储策略2分
## 代码优化