1 概论
1.1 程序语言的分类
- 命令式语言(Imperative Language)
- 通过指明一系列可执行的运算及运算的次序来描述计算过程的语言
- 程序的层次性和抽象性不高
- 声明式语言（Declarative Language）
- 着重描述要处理什么，而非如何处理的非命令式语言
- 函数(应用)式语言(Functional Language)
- 基本运算单位是函数
- 逻辑式(基于规则)语言(Logical Language)
- 基本运算单位是谓词
- SQL
- 面向对象语言(Object-Oriented Language)
- 以对象为核心
- 具有识认性（对象）、类别性（类）、多态性和继承性
1.2 程序翻译的方式有哪几种?有何不同?
1.3 编译程序包含有多少个阶段,各阶段的功能任务分别是什么?
词法分析 ==> 语法分析 ==> 语义分析 ==> 中间代码生成 ==> 代码优化 ==> 目标代码生成
2 词法分析
2.1 DFA、NFA的基本概念
- DFA、NFA是由哪几部分构造的？
- 构造一个正则表达式描述语言L={anbm|n>m}，然后画出DFA
2.2 正则表达式 → NFA → DFA → DFA最小化
- 给出一个问题，用正则表达式写出解，然后进行转换。
- e.g. 写出以a开始，b结束，不包含aabb的正则表达式，然后转化成DFA
2.3 词法分析器的基本构造。
- 要求会用伪代码写出简单的词法分析器（直接用条件语句实现DFA）。
- e.g. 识别C语言中浮点数的词法分析器片段。
- 要求掌握DFA图的存储方式以及基于DFA图实现词法分析的算法。
3 上下文无关文法及分析
3.1 文法、语言?
- e.g. 描述一个文法所定义的语言
3.2* 文法的分类是怎么样的？它们之间有何关系？
乔姆斯基文法系统(Chomsky Grammar Sys-terns)
- 0型文法 短语结构文法(Phrase Structure Grammar)
- 1型文法 上下文有关文法(Context-Sensitive Grammar)
- 2型文法 上下文无关文法(Context-Free Grammar)
- 3型文法 正则文法(Ragular Grammar)
3.2 推导、规约、语法树、文法的二义性？
3.3 如何画语法树？
- e.g. 给出一个文法以及一个句子，画出推导的语法树
3.4* 文法二义性的消除方法有多少种？
4 自顶向下分析！！！
4.1 自顶向下分析法的问题分析
- e.g. 给出某个文法（例如正则表达式，四则运算表达式，匹配注释，匹配括号，二叉树等）的描述，要求写出对应的上下文无关文法。
4.2 递归下降语法分析方法
- e.g. 给出一个上下文无关文法，写出递归下降分解程序。
4.3 LL(1)分析方法
- e.g. 描述各个步骤的算法，例如如何消除左递归，如何求First与follow集合。
4.4* First与Follow集合
5 自底向上分析
5.1 SLR(1), LR(1)中各个字母/数字的含义是什么？
5.2 如何画出LR(0) DFA和LR(1) DFA图？
- e.g. 给出一个文法，要求画出LR(0) DFA图
5.3 LR(0)文法和SLR(1)文法的判断
- e.g. 给出一个文法，判断该文法是否是LR（0），SLR（1）
6 语义分析&代码生成
6.1 语法制导翻译的应用
- e.g. 实现常见的C语言控制语句的文法和翻译的语义动作（if、while、switch）。
