考研复试专业课笔记

编译技术

概述

遍：从头到尾扫描一次。

前端：与源语言有关。后端：与目标机有关。

文法和语言

• 文法G[Z]=（Vn，Vt，P，Z）

  • Vn：非终结符号集

  • Vt：终结符号集

  • P：产生式或规则的集合

  • Z：开始符号（识别符号） Z∈Vn

• 规范推导＝最右推导

• 最右推导：若规则右端符号串中有两个以上的非终结符时，先推右边的。

• 最左推导：若规则右端符号串中有两个以上的非终结符时，先推左边的。

• 语言：文法G[Z]所产生的所有句子的集合。

• 递归文法

• 短语：前面句型中的某个非终结符所能推出的符号串。

• 简单短语：一次推出的短语。

• 句柄：任一句型的最左简单短语。

• 语法树、子树

• 规约、推导、规范归约（对句型中句柄进行的归约）、规范推导

• 二义性文法：存在两棵不同的语法树。

• 文法的实用限制

  • 有害规则：如U::=U
  • 多余规则
    • 不可达符号
    • 不活动符号：规则中含有推不出任何终结符号串的非终结符

• BNF表示：< , >, ::=, | , { , } , [ , ] , ( , )

词法分析

• 状态图
• 词法分析程序

语法分析

根据文法规则，从源程序单词符号串中识别出语法成分，并进行语法检查。

自顶向下分析

• 存在问题及解决
  • 左递归文法：消除直接左递归（使用扩充的BNF表示或改为右递归）
  • 回溯问题：改写文法，超前扫描
• 递归子程序法

符号表

• 符号表的结构与内容
• 符号表的组织方式
• 非分程序结构语言的符号表组织：全局符号表、局部符号表
• 分程序结构语言的符号表组织：栈式符号表

存储组织及管理

• 静态存储分配

• 动态存储分配：栈式动态存储分配

• 活动记录

  • 局部数据区：局部变量
  • 参数区：存放隐式参数和显式参数
  • display区：存放各外层模块活动记录的基地址

源程序的中间形式

• 波兰表示：前缀表达、后缀表达（逆波兰）
• N元表示
  • 三元式：操作符 左操作数 右操作数
  • 四元式：操作符 操作数1 操作数2 结果
• 图结构表示
  • 抽象语法树
  • DAG图（Directed Acyclic Graphs 有向无环图）
• 静态单赋值形式（SSA）：每个变量只赋值一次

错误处理

• 分类
  • 语法错误：源程序在语法上不合乎文法
  • 语义错误：程序不符合语义规则、超越具体计算机系统的限制
• 错误处理
  • 错误改正
  • 错误局部化处理

语法制导翻译技术

• 翻译文法和语法制导翻译
  • 输入文法：未插入动作符号时的文法。产生输入序列。
  • 翻译文法（TG）：插入动作符号的文法。产生活动序列。
  • 语法导制翻译：按翻译文法进行的翻译。
• 属性翻译文法（ATG）
  • 翻译文法中的符号，包括终结符、非终结符和动作符号均可带有属性
  • 综合属性：自底向上，自右向左，用↑表示
  • 继承属性：自顶向下，自左向右，用↓表示
• L-属性翻译文法（L-ATG）：输入文法要求是LL(1)文法

语义分析和代码生成

• 声明的处理
• 表达式的处理
• 赋值语句的处理
• 控制语句的处理
• 过程调用和返回

词法分析自动化

• 确定的有穷自动机（DFA）— 状态图的形式化

• 不确定的有穷自动机（NFA）：从同一状态出发，有以同一字符标记的多条边，或者有以ε标记的特殊边的自动机。

• NFA的确定化

  • 集合I的ε-闭包（ε-closure）：从s出发经过任意条ε弧能够到达的任何状态。
  • Ia=ε-closure(J)，J是从状态子集I中的每个状态出发,经过标记为a的弧而达到的状态集合。
  • 状态转换矩阵

• DFA的简化（最小化）

  • 消除多余状态
  • 合并等价状态

语法分析提高

• LL分析法：自左向右扫描、自左向右地分析和匹配输入串。

• FIRST(α)：α的头符号集合。

• FOLLOW(A)：A的后继符号集合。

• LL(1)文法：一个文法G，其分析表M不含多重定义入口

• 自底向上分析

  • 移进—归约分析：建立符号栈，用来记录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是归约
  • 算符优先分析：当栈顶项(或次栈顶项)终结符的优先级大于栈外的终结符的优先级，则进行归约，否则移进。

代码优化

• 局部优化技术
  • 基本块：连续语句，第一条进，最后一条出
  • 流图：有向图，节点是基本块
  • 优化方法
    • 代数变换
    • 常数合并和传播
    • 删除冗余代码
    • 消除公共子表达式（DAG图）
• 全局优化技术
  • 数据流分析：out[S] = gen[S] ∪ (in[S] – kill[S])
    • out[S]代表在S末尾得到的数据流信息
    • gen[S]代表S本身产生的数据流信息
    • in[S]代表进入S时的数据流信息
    • kill[S]代表S注销的数据流信息
  • 到达定义分析
  • 活跃变量分析
  • 寄存器：冲突图，图着色算法
  • 循环优化

离散数学（一）

逻辑域：逻辑真值集合、逻辑运算集合、关系集合。

合式公式

真值赋值函数：从合式公式到逻辑集合{0,1}的函数，记为σ。

• 有效式（永真式、重言式）：每个真值赋值σ使得σ(Q)=1。
• 永假式（不可满足式）：每个都不为1
• 可满足式：至少有一个

---

简单析取式：Q1∨…∨Qn

简单合取式：Q1∧…∧Qn

析取范式：简单合取式的析取

合取范式：简单析取式的合取

极大项：Q1 ∨…∨Qn，其中Qi是pi或-pi（包含每一个变元）

极小项：Q1∧…∧Qn，其中Qi是pi或-pi（包含每一个变元）

主析取范式：R1∨…∨Rm，其中R1,……,Rm是极小项

主合取范式：R1∧…∧Rm，其中R1,……,Rm是极大项

主析取范式和主合取范式统称为主范式。

---

完全集：S是联结词集合，使得每个n(n>0)元的联结词都可由S定义。如{非、与、或}。

如果从完全集S中去掉任何一个联结词就成为不完全的了，就称S为极小完全集。

---

原子命题（简单命题）：具有确定真或假含义的陈述句。

谓词：表示客体的性质，或表示客体之间的关系的词。Q(x, y)

函数与谓词的区别在于：对于一元函数f，f (x)是论域中的元素；对于一元谓词 P， P(x) 是 0 或 1。

命题：谓词、量词

论域：包括对象集合、运算集合、关系集合。

---

逻辑符号：包括变元、联接词、量词（∀, ∃）、逗号以及括号等。

非逻辑符号：包括常元、函词（\(f_1^n\)，右上角的n表示n元函词）、谓词（\(P_1^n\)）等。

项：常元、变元、函词组成。

合式公式：项、谓词、联接词、量词等组成。

前束范式：δk为∀,∃量词，δ1x1…δnxnQ的公式称为前束范式

---

公理系统的组成： - 语言集 - 公理集：公理是用于表达推理由之出发的初始肯定命题 - 推理规则集：推理规则是由公理及已证定理得出新定理的规则 - 定理集：表达了肯定的所有命题。

命题逻辑公理系统

谓词逻辑公理系统

---

可靠性定理：若\(\Gamma \vdash \alpha\)，则\(\Gamma \vDash \alpha\)。（如果语法上是有效的，则语义（真值）上是有效的）

完备性定理：若\(\Gamma \vDash \alpha\)，则\(\Gamma \vdash \alpha\)。（如果语义上是有效的，那么可以找到一个证明）

三段论：Q, Q→R ⊢ R

离散数学（二）

集合论

集合相等、子集、真子集、空集

幂集：集合A的全部子集构成的集合，记作P(A)。

基数：有穷集合A中所含有元素的个数，记作#A，或|A|、n(A)。

势（基数）：衡量集合的大小。

若存在一个从A到B上的一一映射则AB的势相同。

可数集：元素可以一一列出（是无限集，如自然数）

集合的运算

• 交、并、差、补

• 对称差集：A⊕B =(A-B)∪(B-A)=(A∪B)-(A∩B)

对偶原理：（不含 - 和⊕）将∪和∩互换，Ø和全集互换，仍成立。

集类：如果一个集合的所有元素都是集合，则称该集合为集类。

广义并：集类的所有元素的所有元素。∪B ={x| ∃ X (X∈B ∧ x∈X)}

广义交：集类的所有元素共有的元素。∩B ={x| ∀X (X∈B → x∈X)} , B≠Ø

字母表、字符串、语言、闭包、正闭包

有序偶：< x，y >。可表示为：<x,y>={{x}, {x, y}}

n元序偶：<x1, x2, …, xn>= < <x1, x2, …, xn-1>, xn>

笛卡尔乘积：A×B = {<x, y>| x∈A ∧ y∈B }。不满足交换律、结合律。

关系

关系：R⊆A1×A2×...×An，称R为A1, A2, …, An间的n元关系。

关系的相等：都是n元，每个集合相等，关系用序偶的集合形式表示相等。

关系图：一个<x,y>用一条有向边表示。

关系矩阵：xi与yj有关系R，则矩阵i行j列为1。

关系的性质

• 自反：顶点都有自环
• 反自反：顶点都无自环
• 对称：两个点要么无边，要么有方向相反的两条边
• 反对称：两个顶点之间至多一条边！
• 传递：x到y有路径，则必有x到y的边

关系的运算（记住关系本质上是序偶的集合）

• 交、并、差、补、异或

• 求逆：偶序的第一元和第二元对换；每条边反向；矩阵转置。保持关系的五条性质。

• 合成：复合，R ◦ S ＝{<x, z>|∃y∈Y 使得x R y ∧ y S z) }。矩阵表示类似矩阵乘法。

• 次幂：\(R^0=恒等关系I_A\)，\(R^{n+1}=R^n◦R\)

• 闭包

  

  

---

偏序关系：集合 A上的关系R是自反的、反对称的、传递的。用\(\le\)表示任意偏序关系，并用\(<A ,\le>\)表示偏序结构。

全序关系：偏序\(<A ,\le>\)对于任意 x, y ∈ A，要么x ≤ y，要么y ≤ x，即 x与y可比。则\(\le\)为A上的全序，并称\(<A ,\le>\)为全序结构。

严格偏序关系（拟序关系）：R是反自反的、传递的（满足这两条就必然反对称）。\(<A ,<>\)为严格偏序（拟序）结构。

覆盖：x＜y 且不存在z使得 x＜z 和 z＜y，则y是x的覆盖。

哈斯图（偏序结构图）

• 如果 x＜y ，则点 x 画在点 y 之下
• 如果 y 覆盖 x ，则 x 和 y 之间存在一条无向边

最大元、最小元、极大元、极小元、上界、下界、最小上界、最大下界

{1，2，3，6，12，24，36 } 整除关系的哈斯图，S是红色部分：

良序结构：偏序结构<A , ≤ >，A 的每一个非空子集都有一个最小元。良序必全序。

---

相容关系：自反、对称。

等价关系：自反、对称、传递。

等价关系的矩阵可以通过行列变换化为如下形式：

等价类：A中与x有关系R的元素的集合称为x关于R的等价类，简称x的等价类，记作\([x]_R\)。

商集：等价类的集合，\(\{[x]_R|x\in A\}\)为A关于R的商集，记为A/R。A/R的元素个数称为秩。

划分：划分Π的每个元素非空，并集为A，任意两个交为空。如A={a,b,c}，B={{a}, {b,c}}就是一个划分。

一个等价关系确定一个划分，一个划分确定一个等价关系。

函数

函数：特殊的二元关系，不能一对多。

部分函数：按正常理解的函数，部分有定义dom(f)⊆X。

• 全函数（简称函数）：dom(f)=X
• 严格部分函数：dom(f)⊂X

限制（缩小dom）、延拓（扩大dom）、像、原像

函数的复合：\(f:X\to Y,g:Y\to Z\)，记作\(g ◦ f\)（习惯上）。

满射（ran=Y）、单射、双射（满射+单射，一一对应）

左逆：\(g ◦ f = I_X\)，当且仅当f是单射

右逆：\(f ◦ g= I_X\)，当且仅当f是满射

逆：\(g\)既是左逆，又是右逆。f是双射

特征函数：\(\Psi_A(x)\)，x属于A返回1，不属于返回0。

图论

无向图：G=〈Ｖ,Ｅ,Ψ〉。e, ∈ E 且 v1, v2 ∈ V，Ψ(e) =｛v1，v2｝。

有向图：G=〈Ｖ,Ｅ,Ψ〉。e ∈E 且 v1, v2 ∈V，Ψ(e) =〈v1，v2〉。

• d 度正则图：所有结点的度均为自然数 d 的无向图
• 完全无向图：度都为n-1
• 完全有向图：入度和出度都为n-1

子图、真子图

生成子图：V同，E和Ψ是原图的子集。

导出子图：V'是V的子集，以 V′ 为节点集合的最大子图，记作G[ V′ ]。

路径：v0 e1 v1 e2 … vn-1 en vn

• 长度：n
• 闭路径：v0= vn
• 简单路径：边互不相同
• 基本路径：点互不相同（去掉闭路径得基本路径）

可达：R (v) 表示从 v 可达的全体结点的集合。

距离：记作d (v1, v2)。图的直径定义为最远的两个点的距离。

加权图：〈G，W〉，W(e) 为边 e 的加权长度。

连通

• 无向图
• 有向图
  • 基础图：将有向边改为无向边
  • 强连通：任意两个点互相可达
  • 单向连通：任意两个点，一个可达另一个
  • 弱连通：基础图连通

极大子图

• 分支：无向图G的极大连通子图

• 有向图：强分支、单向分支、弱分支

半路径：基础图中的路径，同向为正向边，反向为反向边。

回路：连通2度正则图

• 半回路：基础图是回路
• 有向回路：入度出度均为1

非循环图：没有回路的图

子图G'的每个结点的入度（出度）都大于零，则有有向回路。

---

欧拉路径：包含所有边的简单开路径。

欧拉闭路（回路）：包含所有边的简单闭路径。

欧拉图：每个结点都是偶结点的无向图。

欧拉有向图：每个结点的出度和入度都相等的有向图。

欧拉定理：G是欧拉图（欧拉有向图）\(\Leftrightarrow\)G有欧拉闭路。

G有欧拉路径\(\Leftrightarrow\)G有两个奇结点。

---

哈密顿路径：包含所有结点的基本路径。

哈密顿回路

哈密顿图：有哈密顿回路的图。

必要条件（哈密顿回路一定满足）：W(G-V1)≤|V1|，W表示连通分支数，V1表示要减去的点集。

---

邻接矩阵：xij表示以 vi和 vj 为起点和终点边的数目。

路径矩阵（可达性矩阵）：pij=1表示vi到vj可达。

---

树：连通、非循环、n-1条边（任意2证1）

森林：每个分支都是树的无向图。

生成树：树T是无向图G的生成子图。

最小生成树：所有生成树中加权长度最小者。

有向树：根指向叶。

最优二叉树：叶加权路径长度最小的（每层的值乘以层数相加）

数据库

基本概念

数据模型

• 概念模型：实体—联系方法（E-R）法
  • 实体
  • 属性
  • 码：唯一标识实体的属性集
  • 域：属性的取值范围
  • 联系
• 数据模型
  • 数据结构
  • 数据操作
  • 数据的约束条件

数据库系统三级模式结构

• 模型：不涉及物理存储细节，与具体的应用、编程语言无关；具体定义数据的逻辑结构。
• 外模式：应用相关
• 内模式：物理相关
• 两级映象：逻辑独立性、物理独立性

关系数据库

域：D1 , D2 ,…, Dn

笛卡尔积（D1×D2×…×Dn）的每个元素（(d1 , d2 , … , dn)）叫元组。

关系：笛卡尔积的子集

语义约束

• 实体完整性：要有属性或属性组合作为主码，主码值不可为空或部分为空
• 参照完整性：关系R的外部码Fk与关系S的主码Pk相对应（或Pk为空）

关系代数

• 并、差、交、广义笛卡尔积
• 选取或限制：选择满足给定条件的元组
• 投影：取若干属性列并删去重复行
• 连接：从两个关系的广义笛卡儿积R×S中选取给定属性(X和Y)间满足比较条件的元组
• 自然连接：从两个关系的广义笛卡儿积R×S中选取在相同属性列上取值相等的元组，并去掉重复的属性列
• 除法

元组演算

域关系演算

数据库数据语言：DDL（数据定义语言）、DML（数据操纵语言）、DCL（数据控制语言）

关系数据库标准语言SQL

略

数据库保护

• 用户标识与鉴别

• 存取控制

  • 自主存取控制：角色与用户组
  • 强制存取控制：对比主体的Label和客体的Label

• 其它方法：视图、审计、数据加密

数据完整性：实体完整性（主键），参照完整性（外键），用户自定义完整性

设计理论

数据依赖：一个关系内部属性值之间相互依赖又相互制约的关系。

• 函数依赖：对于X的每个具体值，Y有唯一的值与之对应。记作：X→Y。
  • 完全函数依赖：如果X→Y，且对于任意X的真子集X ' ，都有X ' 不能→Y，则称Y对X完全函数依赖。
  • 部分函数依赖：非完全函数依赖
  • 传递函数依赖：如果X→Y，Y → Z，且Y 不能→ X，则称Z对X传递函数依赖。
  • Armstrong公理系统：自反律、增广律、传递律
  • 属性集X关于函数依赖集F的闭包：能由F根据Armstrong公理导出的属性
  • 最小依赖集
• 多值依赖：给定一对（x，z）值有一组Y的值，这组值仅仅决定于x值而与z值无关，记作：X →→ Y。

范式

• 1NF：只包含原子值，不能“表中有表”。
• 2NF：每个非主属性完全依赖于码。
  • 从1NF中消除非主属性对码的部分函数依赖可得。
  • 允许主属性部分函数依赖于码。
• 3NF：每个非主属性都不传递依赖于R的任何码。
  • 2NF消除传递函数依赖。
  • 没有限制主属性对码的部分与传递函数依赖。
• BCNF：如果对于R的每个函数依赖X→Y，且Y不是X的子集时，X必含有码
• 4NF：只存在函数依赖或平凡的多值依赖。

候选码求解：L类（左部的属性）、R类（右部的属性）、N类（均未出现的属性）、LR类

存储管理与索引

B树：限制了每个节点放置关键字与指针的最小和最大个数；所有的叶节点都在同一层上。

B+树：把树中所有关键字都按递增次序从左到右安排在叶节点上，并且链接起来。

事务处理技术

ACID特性

• 原子性：作要么都做，要么都不做
• 一致性：从一个一致性状态变到另一个一致性的状态
• 隔离性：并发执行的各个事务之间不能互相干扰
• 持久性：一旦提交之后，它对数据库的影响必须是永久的

事务故障的恢复：UNDO

系统故障：UNDO+REDO

数据不一致性

• 丢失更新：两个事务T1和T2读入同一数据并修改， T2提交的结果破坏了T1提交的结果，导致T1的修改被丢失。
• 脏读：T2读了T1未提交的数据，T1之后回滚了。
• 不可重复读：事务T1读取数据后，事务T2执行更新（修改、插入、删除）操作，使T1无法再现前一次读取的结果。

并发控制（封锁）

• 排它锁（X锁）：事务T对数据对象R加上X锁，则只允许T读取和修改R，其它事务对R的任何封锁请求都不能成功，直至T释放R上的X锁。
• 共享锁（S锁）：事务T对数据对象R加上S锁，则事务T可以读取但不能修改R，其它事务只能对R加S锁，而不能对R加X锁，直到T释放R上的S锁。

意向锁：是该结点的下层结点正在被加锁。

可串行化：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行执行它们时的结果相同。

算法

渐近分析

• 渐近紧确界：\(\Theta(g(n)),c_1g(n)\le\Theta(g(n))\le c_2g(n)\)
• 渐近上界：\(O(g(n))\)
• 渐近下界：\(\Omega(g(n))\)

主定理法

排序

分治

• 归并排序、逆序对
• 最大子数组：找左边的最大、右边的最大、横跨左右的最大
• 快速排序、次序选择（找第k小的元素）

动态规划

• 01背包：背包容量为c时是否要拿第i件物品（P[i,c]），如果不拿继承i-1容量为c的（P[i-1,c]），如果拿要减去当前物品的重量（P[i-1,c-v[i]]+p[i]）。

• 最大子数组：D[i]表示以第i个元素结尾的最大子数组，\(D[i]=max\{X[i]+D[i-1],X[i]\}\)。

• 最长公共子序列：C[i,j]表示X[1...i]和Y[1...j]的最长公共子序列长度.

  

• 最长公共子串：

  

• 编辑距离：

  

• 钢条切割问题：rec[j]记录长度为j钢条的最优切割方案。

贪心

• 哈夫曼编码
• 会场出租：最早结束活动优先（带权的话动规）

图论

• 深搜、广搜

• 拓扑排序：不断删除入度为0的点；顶点完成时刻的逆序

• 强连通分量：把边反向，得到反向图\(G^R\)；在\(G^R\)上执行DFS，得到顶点完成时刻顺序L；在G上按L逆序执行DFS，得到强连通分量。

• 最小生成树

  • Prim：任选一个起点，不断添加最短的边到已连通的集合中，用新加入的点去更新。
  • Kruskal：边先排序，从最小的开始选。

• 最短路径

  • Dijkstra：每次找离源点最近的未选定的点，看能松弛哪些边。
  • Bellman-Ford：对所有的边进行n-1轮松弛操作，如果还能松弛则有负环。
  • Floyd

• 最大二分匹配：寻找增广路径。