第一章

1、编译器的概念：编译器将源语言编写的程序作为输入，而产生用目标语言编写的等价程序。

2、机器语言→汇编语言→高级语言

3、乔姆斯基分层结构

  • 0型：无限制文法------图灵机

  • 1型：上下文相关文法------线性有界自动机

  • 2型：上下文无关文法------下推自动机

  • 3型：正则文法------正则表达式、有限确定的自动机

分类：

  1. 文法左边有终结符：0型/1型

  2. 0型文法左边符号数>=1,.右边符号=>0

  3. 1型文法左右终结符位置对应

  4. 文法左边无终结符：2型/3型

  5. 3型文法右边形式只有 a 或 Aa

 

4、相关程序和概念

  1. 解释器：立即执行源程序

  2. 编辑器：接受并编辑源程序

  3. 交互式开放环境：编译器、编辑器、其他程序捆绑在一起构成的交互式环境

  4. 调试程序：可在编译了的程序中判定执行错误的程序

  5. 分析与综合：

    • 分析：分析源程序以计算其特性的编译器操作

    • 综合：生成翻译代码时的编译器操作

  6. 前端与后端

    • 前端：只依赖于源语言的操作

    • 后端：只依赖于目标语言的操作

  7. 遍：对源程序或源程序中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。

5、扫描程序的功能及输入输出

  • 功能：依据语法规则，分析由字符组成的源程序，把它分割为一个个具有独立意义的最小语法单位，即记号

  • 输入：源程序

  • 输出：Token

6、语法分析器的任务

  1. 分析单词串是如何构成语句和说明的

  2. 分析语句和说明是如何构成程序的

  3. 分析程序的结构

7、语义分析的基本功能

  1. 确定类型

  2. 类型检查

  3. 语义处理

  4. 某些静态语义检查

8、源代码→词法分析→记号→语法分析→抽象语法树/语义树→语义分析→注释树→源代码优化→中间代码→代码生成→目标代码

9、语法制导的语义中，语法树会进行标注？

10、T形图：自举与移植

image-20220530151137472

S：源语言

T：目标语言

H：宿主语言

为了编译器能立即执行，宿主语言必须是机器语言

第二章

1、正则表达式r：

a. 语言：所有匹配这个正则表达式的字符串的集合

b. 字母表：这个正则表达式所有接受的字符的集合

c. 元符号：具有特殊意义的符号

2、有限自动机组成元素

a. 字母表

b. 状态集合

c. 转换函数

d. 初始状态

e. 接受状态

3、DFA的判定

a. 单个输入状态

b. 输入字符，得到的状态确定

c. 消除了ε转换

4、NFA的构造

a. 输入为初始状态的ε集合

b. 输出为转入状态的ε集合

5、DFA与NFA区别

a. 能否根据当前处所状态与面临的输入字符，确定唯一的后继状态

第三章

1、所有记号符号的串集是被表达式的文法定义的语言

2、二义性文法：对某个输入的记号串，可产生两个及两个以上不同分析树或语法树的文法。

消除的方法：

  1. 消除二义性规则

  2. 修改文法,即将文法改变成能强制正确分析 树的构造 的结构

原因：

  1. 文法中缺少对文法符号优先级与结合性的规定，else悬挂

证明有二义性：

  1. 针对一个输入，有两个或两个以上不同的分析树或语法树

  2. 两个及以上的最左推导或最右推导

第四章

一、自顶向下

从文法的开始符号开始，反复使用各种产生式，直到推出整个字符串或者出错

递归下降分析法：
  • 将一个非终结符A的文法规则看作将识别A的一个过程的定义
LL1

  • 第一个L：从左向右扫描输入串

  • 第二个L：最左推导

  • 1：一个符号先行

  • 动作：生成、匹配、接受

二、自底向上

  1. 从程序开始逐步进行归约直到归约到文法的开始符号或出错

  2. 通过叶子结点，逐步向上构造分析树，直到完整构造出根节点。

  3. 寻找句柄

第五章

1、LR（0）文法判别

DFA中每个状态都是移入状态或归约状态，其中哪些状态为归约状态，哪些状态为移入状态；且每个归约状态中只有一个完整项，所以该文法是LR(0)文法。

2、语法：

一组规则，用它可形成和产生一组合式的程序

3、文法：

描述语言的语法结构的形式规则

第六章

1、属性文法

语法规则：

  • 语法——一组规则，用它能够形成一组合式的程序

语义规则：

  • 语义——定义程序的意义的一组规则

2、语义属性包括：

  1. 变量的数据类型

  2. 表达式的值

  3. 存储器中变量的位置

  4. 程序的目标代码

  5. 数的有效位数

3、概念

  1. 联编：确定语义的过程

  2. 联编时间：确定语义的时间点

  3. 静态语义：联编时间能在编译阶段进行确定

  4. 动态语义：联编时间只能在运行的时候进行确定

4、常见的静态语义

5、块结构

包含说明的任意构造 （过程、函数、复合语句）

6、哈希表的基本原理

把字符映射到整数值上

7、符号表的作用、内容

  • Tips：分析阶段是对符号表的构建过程

  • 类型检查（语义分析阶段）

  • 存储地址（相对地址）（目标代码生成阶段）

  • 三种基本操作：插入、查找和删除

8、符号表的基本结构

  • 线性表 //无序表

  • 搜索树 //有序表

  • 杂凑表 //哈希表

第七章

1、概念

1.运行时环境：

目标计算机的寄存器以及存储器的结构

2.过程活动记录：

一个过程或函数被激活或调用的时候，分配给它存储局部数据的空间

  1. 自变量（参数空间）

  2. 用作簿记地址的空间，它包括了返回地址

  3. 用作局部数据的空间

  4. 用作局部临时变量的空间

3.调用序列：过程或函数被调用时，必须发生的操作序列的判定

  1. 为活动记录分配存储器

  2. 计算和保存自变量

  3. 寄存器的保存和设置

4.返回序列：过程或函数返回时需要的额外操作

  1. 放置可由调用程序访问的返回值

  2. 调整寄存器

  3. 活动记录存储器的释放

二、几种运行时环境及特点

a. 完全静态运行时环境 FORTRAN77
1
2
3
i.  数据空间在编译阶段确定

ii. 不允许递归调用、不支持指针
b. 基于栈的运行时环境 C C++ Pascal

i. 指针

   1.  fp frame point 指向当前活动
   2.  控制链 指向先前活动记录
   3.  sp stack point 指向栈顶

ii. 允许递归调用、支持指针，某个过程可能有多个有效的过程活动记录

iii. 整个存储器空间被划分为 代码区、静态存储区域（存放全局变量）、栈区域、堆区域、空闲区域

c. 完全动态的运行时环境

i. 只有在被调用时才被分配空间

ii. 使用堆管理

8-10章

1、代码生成

第一个必须考虑机器的物理特性

2、代码优化的分类

a）窥孔优化：

在目标代码上进行的优化

b）优化应用的程序范围

基本块：一个最大的线性代码序列

局部优化：基本块内

全程优化：过程内，基本块外

过程间优化：程序内，过程外

源代码优化的实例

没找到

名词解释

  1. 短语——一个句型的语法树中任一子树的叶节点所组成的符号串

  2. 直接短语——最小子树的叶节点

  3. 素短语——如果短语中至少含有一个终结符，而且除它自身之外不再含任何更小的素短语

  4. 句柄——一个句型的最左直接短语

  5. 文法——描述语言的语法结构的形式规则

  6. 语法——一组规则，用它能够形成一组合式的程序

  7. 基本块——程序中一顺序执行的语句序列

  8. 语法制导翻译——在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法

  9. 语义——定义程序的意义的一组规则