第一章
编译程序：能够把某一种高级语言程序（源语言程序）转换成另一种低级语言程序（目标语言程序），而后者与前者在逻辑上市等价的，这样一个翻译程序被称为编译程序。
编译过程及每个阶段的任务：编译程序的工作，从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。但就其过程而言，它与人们进行自然语言直接的翻译有许多相近之处。当我们把一种文字翻译为另一种文字，例如把一段英文翻译为中文时，通常需经下列步骤：
（1）识别出句子中的一个个单词；
（2）分析句子的语法结构；
（3）根据句子的含义进行初步翻译；
（4）对译文进行修饰；
（5）写出最后的译文。
类似地，编译程序的工作过程一般也可以划分为五个阶段：词法分析、语法分析、语义分析与中间代码产生、优化、目标代码生成。
第一阶段：词法分析 任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号）
第二阶段：语法分析 任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）
第三阶段:词义分析与中间代码产生 任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
第四阶段：优化 任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
第五阶段：目标代码生成 任务是：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。
第二章
上下文无关文法：在计算机科学中，若一个形式文法 G = (N, Σ, P, S) 的产生式规则都取如下的形式：V -> w，则称之为上下文无关文法。包括一组终结符，一组非终结符，一个开始符号，以及一组产生式
句子、句型的推导语法树过程（联系第五章，句型推导，会画语法树，找出句柄，短语和简单短语）
句型：假定G是一个文法，S是它的开始符号，若S=〉α，则称α是一个句型
句子：仅含终结符的句型是一个句子
句柄：给定句型中的最左简单短语就是句柄
短语： 任一子树的树叶全体(具有共同祖先的叶节点符号串)皆为短语。
简单短语：任一简单子树的树叶全体(具有共同父亲的叶节点符号串)皆为简单短语。
短语：i１, i2, i3, i１+ i2, i１+i2+ i3 简单短语：i１, i2, i3 句柄：i１ (第一个)
９.证明下面的文法是二义的：S->iSeS|iS|i 证明：反例法：
对于该文法的句子iiiei有两个最右推导如下，所以该文法是二义
的： S=>iS=>iiSeS=>iiSei=>iiiei S=>iSeS=>iSei=>iiSei=>iiiei
第三章
词法分析器的功能：输入源程序，输出单词符号。单词符号是一个程序语言的基本语法符号。程序语言的单词符号有：关键字、标识符、运算符、常数、界符。
非确定有限自动机的确定化：
第四章
语法分析器的功能：词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则，包括两类语法分析办法自下而上分析法和自上而下分析法
LL（1）文法的判定（消除左递归，判断是否是LL（1）文法，构造预测分析表）
1.考虑下面文法G1:
S→a|∧|(T)
T→T,S|S
(1)消去G1的左递归.然后对每个非终结符,写出不带回溯的递归子程序。
(2)经改写后的文法是否是LL(1)的?给出他的预测分析表。
2.文法
(1)计算这个文法的每个非终结符的FIRST和FOLLOW集合；
(2)证明这个文法是LL(1)的；
(3)构造它的预测分析表；
（文法）
3. 下面文法中，哪些是LL（1）的，说明理由。
(1) S→Abc
A→a | e
B→b | e
是，以为文法不含左递归，每个非终结符各个产生式的候选首符集两两不相交，对文法中每个非终结符，它包含ε的候选首符集中
First(A)∩Follow(B)=
(3) S→ABBA
A→a | e
B→b | e
不是，因为First(A)∩Follow(B)不为空
第五章
根据LR(0)项目的作用不同，将其分为四类：移近 归约 接受 报错
LR（0）项目的种类
LR的分析原理
SLR冲突的解决方法及过程（项目集规范族，判断是SLR还是LR的，构造预测分析表）
文法G[E]的产生式为：
E—>T|E+T
T—>F|T*F
F—>(E)|i
证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄
2.考虑下面的表格结构文法G2:
S→a|∧|(T)
T→T,S|S
(1)给出(a,(a,a))和(((a,a),∧,(a)),a)的最左和最右推导。
(2)指出(((a,a),∧,(a)),a)的规范规约及每一步的句柄,根据这个规范规约,给出”移进-规约”的过程,并给出它的语法树自下而上的构造过程。
5．考虑文法
S→AS|b
A→SA|a
（1）列出这个文法的所有LR(0)项目。
（2）构造这个文法的LR(0)项目集规范族及识别活前缀的DFA。
（3）这个文法是SLR的吗？若是，构造出它的SLR分析表。
5.2 证明下面文法是SLR(1)文法，但不是LR(0)文法。 S→A
A→Ab|bBa
B→aAc|a|aAb
解：文法G[S]：0：S→A 1：A→Ab 2：A→bBa 3：B→aAc 4：B→a 5：B→aAb
第六章
属性通常分为两类：综合属性和继承属性，综合属性用于“自下而上”传递信息，继承属性用于“自上而下”传递信息，终结符只有综合属性，非终结符可有综合属性也可有继承属性。
在语法树中，一个结点的综合属性的值由其子结点的属性值确定。一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定
根据包含的属性类型，属性文法分为：S-属性文法和L-属性文法仅用综合属性的属性文法称S-属性文法，L -属性文法是包括综合属性和继承属性的属性文法
第七章
中间语言有多种形式，常见的有后缀式、三地址代码（包括三元式，四元式、间接三元式）、DAG图表示。
符号表的功能:(1)收集符号属性(2)上下文语义的合法性检查的依据(3)目标代码生成阶段地址分配的依据
在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，符号表中所登记的信息在编译的不同阶段都要到。在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码。在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据。对一个多遍扫描的编译程序，不同遍所用的符号表也往往各有不同。因为每遍所关心的信息各有差异。
一张符号表的每一项（或称入口)包含两大栏（或称区段、字域），即名字栏和信息栏。信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，由于查填符号表一般是通过匹配名字来寮现的，因此，名字栏也称主栏。主栏的内容称为关键字（key word）。
在整个编译期间，对于符号表的操作大致可归纳为五类：
对给定名字，查询名字是否已在表中；
往表中填入一个新的名字；
对给定名字，访问它的某些信息；
对给定名字，填写或更新它的某些信息；
删除一个或一组无用的项。
主要属性:符号名，符号的类型，符号的存储类别，符号的作用域及可视性，符号变量的存储分配信息，以及符号的其它属性。
以下几种通常都是需要的：名字、类型、存储类别、作用域及可视性、存储分配信息
其它属性 （１） 数组内情向量 （２） 记录结构型的成员信息 （３） 函数及过程的形参
符号表总体组织和表项属性信息组织
第一种： 把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表
第二种： 把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表
第三种：折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。
存储分配策略：静态分配策略、栈式动态分配策略、堆式分配策略
基本块的定义及其划分
所谓基本块，是指程序—顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第—个语句，出口就是其中的最后一个语句。对一个基本块来说，执行时只从其入口进入，从其出口退出。
具体而言：1. 只有一个入口，表示程序中不会有其它任何地方能通过jump跳转类指令进入到此基本块中。2. 只有一个出口，表示程序只有最后一条指令能导致进入到其它基本块去执行。
所以，基本块的一个典型特点是：只要基本块中第一条指令被执行了，那么基本块内所有执行都会按照顺序仅执行一次。
基本块可以用源代码、汇编、指令等表示。
寻找入口语句
1、程序的第一条语句
2、转移语句的目标语句
3、紧跟在条件转移语句后面的语句
·划分基本块的算法：
1、求出所有入口语句
2、一个入口语句对应一个基本块，入口语句对应的基本块方法是：该基本块由该入口语句到下一入口语句（不含下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的代码序列组成
3、凡未被纳入某一基本块的语句，都是程序中控制流程无法到达的语句，可以删除
