编译原理部分复习材料.doc

1翻译器：能够完成从一种语言到另一种语言的变化软件。编译器：一种翻译器，它进行语言变换的特点是目标语言比源语言低级。编译的各个阶段：P2词法分析器语法分析器语义分析器中间代码生成器独立于机器的代码优化器代码生成器依赖于机器的代码优化器2词法记号：由记号名和属性值构成的二元组，属性值有时不必要。记号名是代表一类词法单元的抽象名字，如标识符、某个特定的关键字。记号名是语法分析的输入符号。通常直接用记号名来引用记号。模式：记号的模式描述属于该记号的词法单元的形式。在一个关键字作为一个记号的情况下，它的模式就是构成该关键字的字符序列。对于标识符和其他一些记号，它们的模式有更复杂的结构并且有很多字符串可以匹配它们。 词法单元：又称单词，是源程序中匹配一个记号模式的字符序列，它由词法分析器标识为该记号的实例。在大多数编程语言中，关键字、算符、标识符、常数、文字串（字符串）和标点符号都处理为记号。P16词法错误（概念）P18正规式的定义不确定的有限自动机：P231. 一个有限的状态集合S；2. 一个输入符号的集合（也称输入符号字母表，空串绝不会出现在中）；3. 一个转换函数move：S*()P(S),它把状态和符号（可以是）两组映射到一个状态集合。4. 状态s。是一个唯一的开始状态；5. 状态集合F是接受（或终止）状态集合，并且F包含于S；3上下文无关文法定义：P39（1） VT 是一个非空有限集合，其元素称为终结符。（2） VN是一个非空有限集合，其元素称为非终结符，并有VTVN=非空（3） S是一个非终结符，称为开始符号。（4） P是产生式的有限集合。概念：句子; 推导；语言；句型 P41文法的优点：（1） 文法为语言给出了精确的、易于理解的语法说明。（2） 对于某些文法类，可以自动产生高效的分析器。（3） 如果文法设计得当，则它赋予语言的结构对于把源程序翻译成为正确的目标代码和对于错误诊断都是有用的。（4） 语言也是逐渐完善的，增加新构造以完成新任务的情况时有发生。分离词法分析器的理由：（1） 编译器的效率会改进。（2） 编译器的可移植性加强。（3） 把语言的语法结构分成词法和非词法两部分，为编译器前端的模块划分提供了方便的途径。P47 消除左递归普通的编程错误会出现在不同的层次上：（1） 词法错误。如标识符、关键字或算符的拼写错误，遗漏字符串两端的引号。（2） 语法错误。如算术表达式的刮号不配对。（3） 语义错误。如算符和运算对象之间类型不匹配。（4） 逻辑错误。如在c语言中用赋值号“”代替了比较算符“= =”。LR分析器富有吸引力的原因：（1） LR分析器能够被构造来识别所有能用上下文无关文法写出的编程语言构造。（2） LR分析方法是已知的最一般的无回溯的移进归约方法，它能和其他移进归约方法一样有效地实现。（3） LR方法能分析的文法类是预测分析法或者说LL方法能分析的文法类的直超集。（4） 在自左向右扫描输入的前提下，LR分析器尽可能快地发现语法错误。4综合属性：如果b是A的属性，c1，c2，ck是产生式右部文法符号的属性或A的其他属性，那么b称为A的综合属性。继承属性：如果b是产生式右部某个文法符号X的属性，c1，c2，ck是A的属性或右部文法符号的属性，那么b称为X的继承属性。S属性定义：仅仅使用综合属性的语法制导定义称为S属性定义。注释分析树：每个结点的属性值都标注出来的分析树。依赖图：分析树结点的属性之间的互相依赖可以用依赖图的有向图来描绘。构造翻译方案的规则：（1） 产生式右部符号的继承属性必须在先于这个符号的动作中计算。（2） 一个动作不能引用该动作右边符号的综合属性。（3） 左部非终结符的综合属性只能在它所引用的所有属性都计算完后才能计算。（4） 只有综合属性的情况最简单。6活动纪录的结构：（1） 临时数据；保存临时值。（2） 局部数据；保存过程的局部数据。（3） 保存的机器状态；保存刚好在过程调用前的机器状态信息，包括返回地址及调用过程使用并且在返回时必须恢复的寄存器的内容。（4） 访问链；有些语言需要通过访问链来访问非局部数据。（5） 控制链；用来指向调用者的活动记录。（6） 参数；调用过程提供的实在参数，由被调用过程使用。（7） 返回值。用于存放被调用过程返回给调用过程的值。活动纪录设计布局原则：（1） 调用者和被调用者之间交流的数据一般放在被调用者活动纪录的开始处，并尽可能靠近调用者的活动纪录。（2） 固定长度的项通常放在活动纪录的中间，一般包括控制链、访问链和机器状态链。（3） 在编译时不能及时知道大小的一些项放在活动纪录的末端。参数传递的方法及特点：（1） 值调用。值调用是最简单的传递参数的方法。调用者计算实参，并把它的值（右值）传给被调用过程。（2） 引用调用。调用者把实参存储单元的地址（即实参的左值）传给被调用者，被调用者对形参的任何访问就是对对应实参的访问。（3） 换名调用。P1817.使用独立于机器的中间形式的好处：（1） 再目标比较容易。把针对新机器的后端加到现成的前端上，可以得到另一种机器的编译器。（2） 独立于机器的代码优化器可用于这种中间表示。8.目标程序类型和特点：（1）绝对机器语言程序。目标程序可以放在内存的固定地方并且立即执行，因此程序可用被迅速地编译和执行。（2）可重定位机器语言程序。需要连接装入程序把一组可重定位目标模块连接成一个可执行的目标程序。虽然产生可重定位目标模块必须增加额外的开销来进行连接，但它带来的好处是灵活性。（3）汇编语言程序。产生汇编语言程序作为输出使得代码