Skip to content

Latest commit

 

History

History
281 lines (132 loc) · 11.9 KB

compiler-knowledge-point.md

File metadata and controls

281 lines (132 loc) · 11.9 KB

编译原理

每个知识领域应有本领域的范围说明，包括领域知识的组成（知识单元）以及预期的能力培养目标，能力点的检测方法（实验设计的依据）

内容概述

编译原理知识领域包含以下内容：

  1. 编译原理概述：什么是编译程序、编译程序的逻辑结构、编译程序的组织、编译程序的伙伴程序。
  2. 词法分析：正规文法、正规式、正规文法和正规式的等价性（注：关于等价性证明在“形自”与“编原”中都没讲）、确定有穷自动机（DFA）、非确定有穷自动机（NFA）、带e转移的非确定有穷自动机（e-NFA）、正规式转换为等价的e-NFA、NFA和e-NFA转换为等价的DFA、DFA的最小化、正规式和有穷自动机的等价性、词法分析程序的自动构造工具lex 及其变种。（备注：这部分的多数内容在“形式语言与自动机”中学过，所以在上课时间上可以减少，为没有修过“形式语言与自动机”的同学提供相应的自学材料）。
  3. 自顶向下语法分析 ：确定的自顶向下分析的设计思路、LL(1)文法的判别、某些非LL(1)文法到LL(1)文法的等价变换、递归下降 LL（1）分析、表驱动 LL（1）分析、LL（1）分析中的出错处理。（注：文法的基础知识在“形式语言与自动机”中学过，相应内容在本课程语法分析相关部分不再重复，为没有修过“形式语言与自动机”的同学提供自学材料）
  4. 自底向上语法分析：自底向上分析思想、移进-归约分析、自底向上优先分析的设计思路、简单优先分析法、算符优先分析法（目前的“编原”没深入讲）、LR分析的基本思路、LR(0)分析、SLR(1)分析、LR(1)分析、LALR(1)分析、二义性文法在LR分析中的应用。（备注：自底向上优先分析相关内容目前不讲，可作为可选内容或课后拓展内容）
  5. 语法制导的语义计算：基于属性文法的语义计算、基于翻译模式的语义计算, 语法分析程序的自动构造工具yacc 及其变种。
  6. 静态语义分析和中间代码生成：符号表、静态语义分析、中间代码生成。
  7. 运行时存储组织：运行时存储组织的作用/任务/存储布局/分配策略、活动记录、过程调用、面向对象语言存储分配策略、函数式语言的存储组织方式。（备注：目前主流教材龙书和虎书中也都有函数式语言的存储组织，这部分重要性在增强）
  8. 中间代码优化：基本块、流图和循环、数据流方程、数据流分析、变量使用数据流信息、常见代码优化技术。（备注：中间代码优化在主流教材龙书和虎书中都有比重较大的部分。因课时有限，具体讲的时候可根据时间选择个别的为例，但讲义材料中可以整理出来。这部分内容，可以和后续的“编译原理专题训练”统筹考虑。但后者是选修，所以，本课程除了常见代码优化技术的概述，再讲少量简单而重要的优化算法的具体实现用以示范，或许也是有必要的，具体讲什么可以进一步规划。）
  9. 目标代码生成：目标代码生成基本过程、图着色寄存器分配。基于RISC-V的后端代码生成。（备注：当前RISC-V是计算机组成原理课程、操作系统课程中的重要组成部分，编译后端适当讲解基本指令集的生成是有必要的。）

1. 编译原理概述

核心学习成效：

  1. 掌握编译的涵义：能从代码编译的过程和编译程序的结构理解编译的内涵
  2. 掌握编译的组合：理解单源单目标编译程序（可用T-型图表示）之间的组合机制，从中进一步理解“交叉编译”、“用已有编译程序实现新语言支持”、以及“将编译程序移植到新机器”等的含义和基本设计思路。

能力检测方法：

  1. 能通过编译组合（T-形图组合）的方式解释“交叉编译”、“用已有编译程序实现新语言支持”、“将编译程序移植到新机器”等需求的单源单目标编译程序的组合设计过程。
  2. 对编译程序有一个完整的总体分析和理解。

2. 词法分析：

词法分析：正规文法、正规式、正规文法和正规式的等价性（也可在“形式语言与自动机”课中增加这一内容）、确定有穷自动机（DFA）、非确定有穷自动机（NFA）、带e转移的非确定有穷自动机（e-NFA）、正规式转换为等价的e-NFA、NFA和e-NFA转换为等价的DFA、DFA的最小化、正规式和有穷自动机的等价性、词法分析程序的自动构造工具lex 及其变种。。

核心学习成效：

  1. 正规文法（注：在“形自”与“编原”中都没深入讲）、正规式、有穷自动机（DFA，NFA和e-NFA）的基本概念。

  2. 正规文法和正规式的等价性的证明过程（注：可选，关于等价性证明在“形自”与“编原”中都没深入讲）。

  3. 正规式转换为等价的e-NFA的过程与算法（注：可选）

  4. NFA和e-NFA转换为等价的DFA的过程与算法（注：可选）

  5. 确定有穷自动机（DFA）的过程与最小化算法（注：可选）

  6. 正规式和有穷自动机的等价性的证明过程（注：可选）

  7. lex及其变种的使用方法

能力检测方法：

  1. 能够根据正规式 推出 正规文法

  2. 能够根据正规文法 推出 正规式

  3. 能证明正规文法和正规式的等价性（也可在“形式语言与自动机”课中增加这一内容）。（注：可选）

  4. 能把一个NFA或e-NFA转换为等价的DFA（注：可选）

  5. 能最小化DFA（注：可选）

  6. 能完成词法分析器的编译原理实验

3. 自顶向下语法分析

核心学习成效：

  1. LL(1)文法的判别：判断某文法是否是LL(1)文法

  2. 某些非LL(1)文法到LL(1)文法的等价变换方法

  3. 递归下降 LL（1）分析的方法

  4. 表驱动 LL（1）分析的方法

  5. LL（1）語法分析中的出错处理

能力检测方法：

  1. 能计算FIRST集合，FOLLOW集合，SELECT集

  2. 对于某些非LL(1)文法，能提取左公因子

  3. 对于某些非LL(1)文法，能消除左递归

  4. 基于某LL(1)文法，能进行递归下降 LL（1）分析

  5. 基于某LL(1)文法，能进行表驱动 LL（1）分析

  6. 理解应急恢复、短语层恢复的出错处理的方法

  7. 能完成基于LL(1)分析的语法分析器的编译原理实验

4. 自底向上语法分析

核心学习成效：

  1. 理解自底向上优先分析的设计思路

  2. 掌握简单优先分析法：优先关系的定义、简单优先文法的定义、简单优先分析法的操作步骤

  3. 掌握算符优先分析法：直观算符优先分析、算符优先文法的定义、算符优先关系表的构造、算符优先分析算法

  4. 理解算符优先分析法的局限性

  5. 理解LR分析的基本思路和重要步骤：移进、归约、接受、报错

  6. 掌握LR(0)分析：可归前缀、活前缀、句柄、识别活前缀的有限自动机、活前缀及其可归前缀的一般计算方法、LR(0)项目集规范族的构造方法

  7. 掌握SLR(1)分析：SLR(1)项目集规范族的构造方法

  8. 掌握LR(1)分析：LR(1)项目集规范族的构造方法

  9. 掌握LALR(1)分析：LALR(1)项目集规范族的构造方法

  10. 了解根据特殊限定消解某些二义性文法带来的冲突问题、以适应LR分析的方法

能力检测方法：

  1. 能描述自底向上优先分析的基本处理过程

  2. 基于某些无二义的文法，能进行简单优先分析

  3. 能完成基于简单优先分析的语法分析器的编译原理实验

  4. 能完成基于LR(0)、LALR(1)等分析的语法分析器的编译原理实验

5. 语法制导的语义计算

核心学习成效：

  1. 掌握基于属性文法的语义计算：属性文法的定义、S-属性文法和L-属性文法、基于S-属性文法的语义计算、基于L-属性文法的语义计算

  2. 掌握基于翻译模式的语义计算：翻译模式的定义、基于S-翻译模式的语义计算、基于L-翻译模式的自顶向下语义计算、基于L-翻译模式的自底向上语义计算

  3. yacc及其变种的使用方法

能力检测方法：

  1. 能够对基于S-属性文法进行语义计算

  2. \2. 能够对基于L-属性文法进行语义计算

  3. 能够对基于S-翻译模式进行语义计算

  4. 能够对基于L-翻译模式进行语义计算

  5. 能通过使用lex,yacc 实现对一个小语言（如四则计算等）的处理

  6. 能完成语义计算相关的编译原理实验

6. 静态语义分析和中间代码生成

核心学习成效：

  1. 理解符号表：符号表的作用、常见属性和实现、作用域与可见性

  2. 理解静态语义分析：类型检查

  3. 理解中间代码生成：中间表示形式、抽象语法树、三地址码

能力检测方法：

  1. 理解符号表的创建和操作过程

  2. 能判断单符号表组织的作用域与可见性

  3. 能判断多符号表组织的作用域与可见性

  4. 能结合语法制导的语义计算进行类型检查

  5. 能结合语法制导的语义计算生成抽象语法树

  6. 能结合语法制导的语义计算生成三地址码

  7. 能完成符号表和中间代码生成相关的编译原理实验

运行时存储组织

核心学习成效：

  1. 了解存储组织的作用和任务

  2. 掌握程序运行时存储空间的布局

  3. 掌握静态、栈式、堆式存储分配策略

  4. 掌握活动记录：过程活动记录、嵌套过程定义中非局部量的访问、嵌套程序块的非局部量访问

  5. 掌握动态作用域规则和静态作用域规则

  6. 掌握过程调用的编译生成

  7. 理解面向对象语言存储分配策略

  8. 理解函数式语言的存储组织方式

能力检测方法：

  1. 能用对某程序代码的运行时布局下的活动记录进行推演和计算。

  2. 能区分静态、栈式、堆式存储分配策略的区别。

  3. 能用对某程序代码的运行时布局下的控制链（动态链）和访问链（静态链）进行分析。

  4. 能根据单继承面向对象语言的特性，给出面向对象存储组织的方式和具体内容。

  5. 能根据基本函数式语言的特性，给出相应的运行时存储设计方案。

  6. 能完成运行时存储组织相关的编译原理实验。

8. 中间代码优化

核心学习成效：

  1. 掌握基本块、流图和循环的基本概念

  2. 掌握数据流方程的概念、一般框架和一般求解过程

  3. 掌握典型的数据流分析：到达-定值数据流分析、活跃变量数据流分析

  4. 掌握变量使用数据流信息：UD链、DU链、基本块内变量的待用信息、基本块内变量的活跃信息

  5. 掌握代码优化技术：了解窥孔优化、局部优化、循环优化、全局优化及过程间优化的基本思想和典型示例，掌握其中某些优化算法的具体实现方法。

能力检测方法：

  1. 能求解数据流方程，进行到达-定值数据流分析、活跃变量数据流分析

  2. 能通过求解数据流方程，获得UD链、DU链、基本块内变量的待用信息、基本块内变量的活跃信息

  3. 可对代码片段进行优化：能设计实现窥孔优化、局部优化、循环优化、全局优化中某些典型的优化方法。

  4. 能完成中间代码优化相关的编译原理实验。

9. 目标代码生成

核心学习成效：

  1. 掌握目标代码生成基本过程

  2. 目标代码生成的主要环节：指令选择、寄存器分配、指令调度

  3. 理解图着色寄存器分配算法

能力检测方法：

  1. 能基于图着色算法进行寄存器分配

  2. 基于某种中间码格式和目标码定义，能手动完成一个简单的中间码到目标代码生成过程

  3. 能完成（RISC-V）目标代码生成相关的编译原理实验。