编译原理-总复习-48学时

1、程序设计语言编译原理程序设计语言编译原理复复 习习 一一 概述概述1.1. 编译程序：编译程序： 编译的五个阶段，及其相应的输入编译的五个阶段，及其相应的输入/ /输出输出 编译程序的结构编译程序的结构 编译的前端、后端编译的前端、后端 符号表，出错处理的角色符号表，出错处理的角色2.2. 解释程序解释程序3.3. 构造编译程序的主要方法构造编译程序的主要方法4.4. 遍，编译程序划分遍，编译程序划分“遍遍”的依据的依据 二、高级语言及其语法描述二、高级语言及其语法描述 1.1.定义：符号，符号串，字符串连接，字符串定义：符号，符号串，字符串连接，字符串 长度等长度等1.1.文法：规则（产生式

2、），产生式的左部，文法：规则（产生式），产生式的左部， 产生式的候选式，终结符号，文法产生式的候选式，终结符号，文法 非终结符号，开始符号，非终结符号，开始符号，V VN N , V , VT T , , 二、高级语言及其语法描述（续）二、高级语言及其语法描述（续）3.3.演算：直接推导，直接规约，推导，规约，演算：直接推导，直接规约，推导，规约， 句型，句子，语言，最左推导，句型，句子，语言，最左推导， 最右推导，文法等价最右推导，文法等价4.4.语法树语法树5.5.二义性：句子二义，文法二义，语言二义二义性：句子二义，文法二义，语言二义6.6.短语，直接短语：定义，从语法树中寻找短语，直接

3、短语：定义，从语法树中寻找 三、词法分析三、词法分析 1.1. 定义：单词符号，单词符号种类，定义：单词符号，单词符号种类，贪心算法，超前搜索贪心算法，超前搜索2.2. 状态图，状态图，3.3. 词法分析程序，词法分析程序，4.4. 正规式，正规文法，正规式，正规文法，NFA MNFA M，DFA MDFA M5.5. NFA M =NFA M =DFA MDFA M6.6. DFA MDFA M最小化最小化四、语法分析四、语法分析 1. 自底向上方法自底向上方法 规范规约分析法：规范规约分析法：短语，直接短语，句柄短语，直接短语，句柄规范推导，规范规约规范推导，规范规约规范规约语法分析：归约

4、串的选择方法，规范规约语法分析：归约串的选择方法，规范规约分析分析时选择的数据结构，分析规范规约分析分析时选择的数据结构，分析方法等。方法等。分析树分析树LR文法文法四、语法分析（续）四、语法分析（续）2.2. 自底向上方法自底向上方法 算符优先分析法算符优先分析法 算符文法算符文法 算符优先关系算符优先关系 算符优先文法算符优先文法 素短语，最左素短语素短语，最左素短语 算符优先分析：归约串的选择方法算符优先分析：归约串的选择方法 FirstVT,LastVTFirstVT,LastVT 集合：定义，计算算法。集合：定义，计算算法。四、语法分析（续）四、语法分析（续）2.2. 自底向上方法自

5、底向上方法 算符优先分析法（续）算符优先分析法（续）优先关系表，含义，构造方法优先关系表，含义，构造方法语法分析时选择的数据结构，分析方法等。语法分析时选择的数据结构，分析方法等。分析树分析树优先函数：定义，构造方法，与优先函数：定义，构造方法，与“优先关系优先关系”之间的关系之间的关系四、语法分析（续）四、语法分析（续）3.3. 自顶向下方法自顶向下方法 递归下降分析法递归下降分析法 递归规则，递归文法递归规则，递归文法 直接左递归文法，直接左递归文法， 间接左递归文法间接左递归文法 文法的改造方法文法的改造方法 递归下降分析程序递归下降分析程序四、语法分析（续）四、语法分析（续）4.4.

6、自顶向下方法自顶向下方法 预测分析法预测分析法 FirstFirst集合，集合，FOLLOWFOLLOW集合：定义，构造方法集合：定义，构造方法 LL(1)LL(1)文法文法 利用利用FirstFirst集合，集合，FOLLOWFOLLOW集合，判定文法为集合，判定文法为LL(1)LL(1)的方法的方法 预测分析表：定义，构造预测分析表：定义，构造 利用预测分析表，判定文法为利用预测分析表，判定文法为LL(1)LL(1)的方法的方法 细化的递归下降分析程序细化的递归下降分析程序五、语义分析五、语义分析1.1. 定义：（某些含定义公式）定义：（某些含定义公式） 语法制导翻译方法，属性，属性文法，

7、语法制导翻译方法，属性，属性文法， 常用的中间代码及格式常用的中间代码及格式2.2. 属性举例：属性举例： E.code , | , E.val , E.placeE.code , | , E.val , E.place , , E.Truelist, E.Falselist , M.quad E.Truelist, E.Falselist , M.quad ， Nextquad , N.quad, S, S.nextlistNextquad , N.quad, S, S.nextlist , , elsit, elist.array elsit, elist.array, , elist.D

8、IM, elist.place elist.DIM, elist.place, , L , L.offset , L.place L , L.offset , L.place 五、语义分析（续）五、语义分析（续）3.3. 函数举例：函数举例： Trip , node , leaf, entry, gen , Trip , node , leaf, entry, gen , newtemp, merge, backpatchnewtemp, merge, backpatch4.4. 文法改造：原因，做法文法改造：原因，做法5.5. 高级语言语句基本语句的分析高级语言语句基本语句的分析 算术表达式

9、，赋值语句，说明语句，布尔表达式，算术表达式，赋值语句，说明语句，布尔表达式，ifif语句，语句，whilewhile语句，数组元素赋值语句语句，数组元素赋值语句 六、符号表六、符号表 1.1. 什么是：项，域，定长域，变长域，什么是：项，域，定长域，变长域，2.2. 符号表的三种构造方式符号表的三种构造方式 线性表：填入符号，查找符号等工作的线性表：填入符号，查找符号等工作的 处理方法，性能处理方法，性能 有序表：填入符号，查找符号等工作的有序表：填入符号，查找符号等工作的 处理方法，性能处理方法，性能 hashhash表：填入符号，查找符号等工作的表：填入符号，查找符号等工作的 处理方法，

10、性能处理方法，性能六、符号表（续）六、符号表（续）3.3. PASCALPASCAL的符号表的符号表 作用域作用域 名字重名时，访问原则（最近嵌套作用域）名字重名时，访问原则（最近嵌套作用域） PreviousPrevious 嵌套层次表，嵌套层次表，levalleval TOP TOP 指针指针 过程的层数过程的层数 Pascal Pascal 程序的一般结构，说明部分，程序程序的一般结构，说明部分，程序体，过程体体，过程体 七、存储分配七、存储分配 1.1. 静态存储分配，动态存储分配静态存储分配，动态存储分配2.2. 定义：活动，活动记录，定义：活动，活动记录，SP,TOPSP,TOP3

11、.3. 参数传递的参数传递的4 4种方式种方式4.4. 临时变量的分配策略临时变量的分配策略七、存储分配（续）七、存储分配（续）5.5. C C语言的存储分配策略，以及主要工作语言的存储分配策略，以及主要工作 活动纪录：定义，各分项内容活动纪录：定义，各分项内容 参数参数 过程调用过程调用 过程进入过程进入 过程返回过程返回 数组分配数组分配 各种数据的访问：参数，局部名，全局名，各种数据的访问：参数，局部名，全局名，数组元素等数组元素等七、存储分配（续）七、存储分配（续）6.6. pascalpascal语言的存储分配策略，以及主要工作语言的存储分配策略，以及主要工作 非局部量的访问方式非局部量的访问方式 静态链方式下，活动记录的各分项内容静态链方式下，活动记录的各分项内容 嵌套层次表方式下，活动记录的各分项内容嵌套层次表方式下，活动记录的各分项内容 全局全局DISPLAYDISPLAY DISPLAYDISPLAY表中，过程层数与记录数量之间的关系表中，