第一章

1、典型的编译器可以划分成几个主要的逻辑阶段？各阶段的主要功能是什么？

答：典型的编译器可以划分成七个主要的逻辑阶段，分别是词法分析器、语法分析器、语义分析器、中间代码生成器、独立于机器的代码优化器、代码生成器、依赖于机器的代码优化器。 各阶段的主要功能：

（1）词法分析器：词法分析阅读构成源程序的字符流，按编程语言的词法规则把它们组成词法记号流。

（2）语法分析器：按编程语言的语法规则检查词法分析输出的记号流是否符合这些规则，并依据这些规则所体现出的该语言的各种语言构造的层次性，用各记号的第一元建成一种树形的中间表示，这个中间表示用抽象语法的方式描绘了该记号流的语法情况。

（3）语义分析器：使用语法树和符号表中的信息，依据语言定义来检查源程序的语义一致性，以保证程序各部分能有意义地结合在一起。它还收集类型信息，把它们保存在符号表或语法树中。

（4）中间代码生成器:为源程序产生更低级的显示中间表示，可以认为这种中间表示是一种抽象机的程序。 中间代码生成所依据的是语义规则。

（5）独立于机器的代码优化器：试图改进中间代码，以便产生较好的目标代码。通常，较好是指执行较快，但也可能是其他目标，如目标代码较短或目标代码执行时能耗较低。 （6）代码生成器：取源程序的一种中间表示作为输入并把它映射到一种目标语言。如果目标语言是机器代码，则需要为源程序所用的变量选择寄存器或内存单元，然后把中间指令序列翻译为完成同样任务的机器指令序列。

（7）依赖于机器的代码优化器：试图改进目标机器代码，以便产生较好的目标机器代码。

第二章

1、通常在词法记号流中已经没有行的概念，因此复制源程序的事情一般有词法分析器完成。 2、词法记号：简称记号，有记号名和属性值构成的二元组，属性值有时不必要，记号名代表一类词法单元的抽象名字（如标示符、某个特定的关键字），是语法分析的输入符号。 3、模式：记号的模式描述属于该记号的词法单元的形式。在一个关键字作为一个记号的情况下，它的模式就是构成该关键字的字符序列。

4、词法单元：又称单词，是源程序中匹配一个记号模式的字符序列，它由词法分析器标识为该记号的实例。

5、在大多数编程语言中，关键字、算符、标示符、常数、文字串和标点符号处理为记号。 6、词法记号的属性

position = initial + rate* 60的记号和属性值：

position 、initial、rate均为标识符，种类均为id

7、c语言的6个关系算符都属于记号relation。

8、字母表：表示符号的有限集合，符号的典型例子有英文字母和标点符号。

9、语言的运算 并： L U M = {s | s L 或 s M } 连接： LM = {st | s L 且 t M} 幂： L0是{}，Li是

闭包： L* = L0 U L1 U L2 U … 正闭包： L + = L1 U L2 U …

10、正规定义的例子

无符号数集合，例1946,11.28,63E8,1.99E6 digit 0 | 1 | … | 9 //表示0-9的整数 digits digit digit* //多个数字整数 optional_fraction .digits|ε //表示小数，可出现可不出现 optional_exponent ( E ( + | — | ε) digits ) | ε//表示指数，可出现也可不出现 number digits optional_fraction optional_exponent //无字符号数由整数部分、小数和指数部分，其中小数和指数部分可出现可不出现。 简化表示 number digit+ (.digit+)? (E(+|—)? digit+)? 11、状态转换图： 正规定义的例子 while while do do relop < | < = | = | < > | > | > = letter A | B | … | Z | a | b | … | z id letter (letter | digit )* number digit+ (.digit+)? (E (+ |—)? digit+)? 标识符号relops的转换图如下：（relop的属性值有LT、LE、EQ、NE、GT、GE）

12、不确定的有限自动机（简称NFA） 一个数学模型，它包括： 1、有限的状态集合S

2、输入符号集合

? × (

3、转换函数move : S

? U{ε} ) P(S)

4、状态s0是唯一的开始状态 5、F S是接受状态集合

13、确定的有限自动机（简称DFA) 一个数学模型，包括： 1、有限的状态集合S 2、输入字母集合 3、转换函数move : S

×

? S，且可以是部分函数

4、唯一的开始状态 s0 5、接受状态集合F S 14、

表示识别：

表示选择

表示连接：

表示闭包：

15、从正规式建立识别器的步骤：从正规式构造NFA、把NFA变成DFA、 将DFA化简。

第三章

1、上下文无关文法是四元组（VT , VN , S, P） VT : 终结符集合 VN : 非终结符集合

S : 开始符号，非终结符中的一个

P : 产生式集合， 产生式形式 : A 2、 推导

把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替 例 E→E + E | E * E | (E ) | —E | id

E => —E =>—(E) =>—(E + E) => —(id + E) =>—(id + id) 例 E→ E + E | E*E | (E ) |— E | id

最左推导（从最左边的飞终结符开始推导） E =>lm —E => lm —(E)=> lm —(E + E) => lm—(id + E)=> lm —(id + id)