重点：
① 词法分析、语法分析的基本理论和方法。
② NFA向DFA的转换。

难点：
① 词法分析、语法分析的基本理论和方法。
② NFA向DFA的转换。

亮点/应用/重要性：
　　本部分内容从总体上看是比较难。语法分析和词法分析的部分在各种相关类型的考试中均会出现，所以在复习中要特别关注这部分内容。

主要内容：
① 词法分析、语法分析的基本理论和方法。
② 有限自动机的基本工作原理，NFA向DFA的转换。

一、编译原理(20060320)在线专题授课音视频

（本课程正式学员可登录学习系统，进入对应课程，在窗口左边的“课程资料室”内进行在线浏览。）

二、编译原理(20060320)在线答疑整理

1. 编译程序和解释程序的区别
解释程序也称为解释器，它或者直接解释执行源程序，或者将源程序翻译成某种中间表示形式后再执行。而编译程序则是将源程序翻译成目标语言程序，然后在运行目标程序。两种语言处理程序的根本区别是：
（1）在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程。
（2）在解释方式下，源程序和解释程序要参与到程序的运行过程中，运行程序的控制权在解释程序。
（3）解释器翻译源程序时不生成独立的目标程序，而编译器则需将源程序翻译成独立的目标程序。

2. 编译程序的工作过程可分六个阶段：
(1). 词法分析阶段：这个阶段的任务是对源程序从前到后逐个字符进行扫描，从中识别出一个个“单词”符号。
(2). 语法分析阶段：语法分析任务是在词法分析的基础上，根据语言的语法规则将单词符号序列分解成各类语法单位，如“表达式”“语句”“程序”等。
(3). 语义分析阶段：语义分析阶段主要检查源程序是否存在语义错误，只有语法和语义都正确的源程序才能翻译成正确的目标代码。
(4). 中间代码生成阶段：中间代码生成阶段的工作是根据语义分析的输出生成中间代码
(5). 代码优化阶段：当需要生成高效的目标代码时，就必须进行优化，优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行
(6). 目标代码生成阶段：这一阶段的任务是把中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或汇编指令代码。

3. 文法的定义：
描述语言语法结构的形式规则称为文法。文法是一个四元组，可表示为：，其中是一个非空有限集，其中的每个元素称为一个终结符；是一个非空有限集，其每个元素称为非终结符。，即和不含公共元素。令，称为文法的词汇表，中的符号称为文法符号，包括终结符和非终结符。，称为开始符号，它至少要在一条产生式中作为左部出现。是产生式的有限集合，每个产生式是形如“”的规则，其中，称为产生式的左部，∈V+且中至少含有一个非终结符；称为产生式的右部且。

4. 确定的有限自动机（DFA）：
一个确定的有限自动机是个五元组：，其中：
· 是一个有限集，其每个元素称为一个状态；
· 是一个有限字母表，其每个元素称为一个输入字符；
· 是从上的单值部分映像。表示当前状态为、输入为?时，将转换到的下一状态。我们称为的一个后继状态；
· ，是惟一的一个开始状态；
· 是非空的终止状态集合，。

5. 不确定的有限自动机（NFA）
一个不确定的有限自动机也是一个五元组，它与确定有限自动机的区别是：
· 是从上的映像。对于中的一个给定状态及输入符号，返回一个状态的集合。即当前状态的后继状态不一定是惟一的。
· 有向弧上的标记可以是。
对于每个NFA M，都存在一个DFA N，且。

6. NFA转换为DFA
设NFA N=，与之等价的DFA M=，用子集法将非确定的有限自动机确定化的算法步骤如下：
① 求出DFA M的初态，即令,此时仅含初态,并且没有标记；
②对于中尚未标记的状态, 进行以下处理：标记；对于每个,令；若尚不在中，则将作为一个未加标记的新状态添加到，并把状态转换函数添加到DFA M中；
③ 重复步骤②，直到中不再有未标记的状态时为止；
④ 令。