语言

程序语言分类

1. 强制式语言:基础为冯诺依曼体系结构
   • 变量
   • 赋值
   • 重复
2. 函数式语言
3. 逻辑式语言
4. 对象式语言:抽象数据类型

变量及属性

变量：一个(一组)已经命名的存储单元

• 作用域： 可访问该变量的程序范围
  • 静态作用域绑定：按照语法定义作用域
  • 动态作用域绑定：按照程序执行动态定义作用域
• 生存期：一个存储区绑定与一个变量的时间区间
• 值：变量对应存储单元存的值
• 类型：变量的值的类型及操作

虚拟机

虚拟机是由实际机器加软件实现的机器

抽象机

抽象机是用自动机模型创造出的硬件/软件理论模型

程序单元及单元实例

程序单元：程序执行过程中独立调用的单位

活动记录：执行该程序单元所必须信息&局部变量绑定的存储区

单元实例：程序单元运行时由代买段和活动记录组成，称为单元实例

数据类型

数据类型为对存储值的抽象，包括：

• 一组值的集合
• 一组操作

分类：

• 内部类型:语言定义的数据类型
• 自定义类型

数据类型的作用

1. 实现了数据抽象
2. 使程序员从机器的具体特征中脱离
3. 提高了编程效率

内部类型的优点

• 基本表示的不可见
• 编译时检测变量的正确性
• 编译时确定无二义操作
• 精度控制

数据聚合的六种方式

1. 笛卡尔积
   • $A_1 A_2 A_3 \dots A_n $
   • C：Struct
   • Pascal：Record
2. 有限映像(映射)

• 数组

1. 序列
   • 由任意多个数据项组成，每个数据项有相同的数据类型

• 串/顺序文件

1. 递归

   • 数据类型T的定义包含T的成分
   • 二叉树的定义

2. 判定或

   • 在两个不同选择对象间做出适当的选择
   • C：Union
   • Pascal：Record

3. 幂集

   • 类型是基类型的子集

抽象数据类型的定义及使用

• 在定义该类型的程序单元中，定义类型操作
• 在使用该类型的程序单元中，类型表示是隐蔽的

类型检查及分类

对数据对象的类型和操作是否匹配的检查

动态/静态

等价类型

两个类型可以互相赋值，一个类型的实参可以对应另一个类型的形参

• 名等价：类型名相同
• 结构等价：类型具有相同的结构

语句级控制结构

控制语句执行顺序的机制：

• 顺序
• 选择：if else/switch
• 重复：for/while

单元级控制结构

控制程序单元间流程的机制

• 显示调用
  • 调用语句使用被调用语句名来调用
  • 参数绑定的两种方式
    • 位置绑定
    • 关键字绑定
• 异常处理
  • 隐式调用
  • 发生异常，传递信号，调用特定函数处理
• 协同程序
  • 两个或两个以上的程序单元交替执行
• 并发单元
  • 程序单元并行执行

副作用/别名

引用环境：局部变量+非局部变量

别名：同一引用环境中，几个变量绑定于同一数据对象

副作用：对绑定的非局部变量修改时产生副作用

• 降低程序可读性
• 限制数学运算律
• 影响目标代码优化

语言的定义

语言是描述计算机执行算法的形式表示

语法+语义

文法的定义

文法是描述语法结构的形式规则

文法的分类

0型文法：

• $\alpha \rightarrow \beta$

1型文法(上下文相关文法)：

• $|\beta| \geq |\alpha|$

2型文法(上下文无关文法):

• $A \rightarrow \alpha$
• 在1型文法基础上要求$\alpha$为非终结符

3型文法(正则文法/右线性文法)

• $A \rightarrow \alpha | A \rightarrow \alpha B$

算符文法

上下文无关文法(2型)，产生式右端没有相接的非终结符，没有空产生式，即为算符文法

语法描述的基本用途

1. 表达语言设计者的意图及设计目标
2. 指导语言的使用者如何写一个正确的程序
3. 指导语言的实现者如何检测识别正确程序

推导，语言，句型，句子，文法等价

$S \rightarrow ^{*}\alpha$

句型：$\alpha \in V^*$

句子：$\alpha \in V_{T}^{*}$

语言：由文法推出的所有句子的集合，记L(G)

文法等价：若两个文法产生的语言相同，则称其等价

短语，句柄，直接短语，素短语

短语：$\alpha A \beta$是一个句型，A->$\omega$，则$\omega$为句型关于非终结符A的短语

• 语法树一个节点的所有子节点的叶子结点构成其短语

句柄：句型的最左直接短语

直接短语: A->$\alpha$

素短语：

语法树(推导树)

无二义性文法只有一个语法树

规范规约

最左规约

规范推导

最右推导

编译

编译的概念(编译及翻译)

翻译：将一种语言编写的程序转换为另一种语言的完全等效的程序

编译程序：高级语言 $\rightarrow$ 低级语言

• 宿主语言：编写编译程序的语言

汇编程序：汇编语言 $\rightarrow$ 机器语言

词法分析器的作用

• 扫描符号串，按词法规则生成单词表
• 识别词法错误

单词符号的分类

• 标识符
• 基本字
• 常数
• 运算符
• 界符: ; / /等

公共左因子/左递归的消除

>

FIRST/FOLLOW集，预测分析表的构造(预测分析)

• FOLLOW集不漏的求法:
  • 终结符：$S \rightarrow Aa, a \in FOLLOW(A)$
  • FIRST集：$S \rightarrow AB, FIRST(B) \subseteq FOLLOW(A)$
  • 尾非终结符：$S \rightarrow \dots A, FOLLOW(S) \subseteq FOLLOW(A)$
  • 特判$FIRST$为$\varepsilon$时的情况

FIRSTVT/LASTVT集，优先关系表构造(算符优先)

LR分析法(LR(0)， SLR(1))，项目规范族及分析表

>

语义分析

语义检查

• 一致性检查
• 越界检查

语义处理

• 说明语句：登记信息
• 执行语句：生成中间代码

语法制导翻译

在语法分析过程中，根据每个产生式对应的语义子程序，进行翻译生成中间代码的方法。

翻译结果:四元式/三地址式

>

语义子程序

>

局部优化方法

在基本块内优化

• 合并已知量
• 删除公共子表达式
• 删除无用赋值
• 删除死代码

全局优化方法

循环优化方法

• 代码外提

• 强度削弱

  • 同族归纳变量：$j = c_1 * i + c_2$
  • 与循环计数器相关的值(同族归纳变量)，将其转换为与循环计数器无关的赋值(需在循环外初始化)
  • 删除归纳变量

• 将同族归纳变量作为判断条件

寄存器分配原则

• 本身占用寄存器
• 有空余寄存器
• 无空余寄存器：选择替换一个
  1. 或在内存中有保留副本的
  2. 或之后最远引用的
  3. 或在之后不再引用的

活动记录内容

1. 返回指针
2. 动态链接
3. 静态链接
4. 现场保护
5. 参数个数
6. 参数单元
7. 局部变量
8. 临时变量

三种分配方式(静态/栈式/堆分配)

静态分配：编译时进行存储分配

仅含半静态变量的栈式分配

>

允许过程嵌套定义的栈式分配

>

静态作用域规则

最近嵌套规则

动态作用域规则

最近嵌套规则(最近调用)

数据参数传递的几种方法

• 传值
• 传地址
• 传名

循环

程序流图中有唯一入口结点的强连通子图