程序设计语言编译原理-考试重点.doc

《程序设计语言编译原理-考试重点.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第一章引论1.编译程序分几个阶段，每个阶段的任务是什么？五个阶段：词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成词法分析任务：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。（如基本字，标识符，常数，算符和界符）。语法分析任务：在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（短语、子句、句子、程序段、程序），并确定整个输入串是否构成语法上正确的程序。语义分析和中间代码生成任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。

2、代码优化任务：对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码　。目标代码生成任务：将中间代码变换成特定机器上的低级语言代码2.表格管理和出错处理：编译各阶段均须维持表格并进行表格管理，建表的技术支持是数据结构，表格的分类、结构、处理方法决定于语言及机器，还有优化措施。一个好的编译程序应该：全，最大限度发现错误；准，准确指出错误的性质和发生地点；局部化，将错误的影响限制在尽可能小的范围内。源程序中的错误通常分为：语法错误，不符合语法（或词法）规则的错误，如单词拼

3、写错误、括号不匹配...语义错误，不符合语义规则的错误，如说明错误、作用域错误、类型不匹配...3.前端、后端：编译前端主要由与源语言有关，但与目标机无关的那些部分组成。编译后端包括编译程序中与目标机有关的那些部分。4.遍：根据系统资源的状况、运行目标的要求……等，可以将一个编译程序设计成多遍扫描的形式，在每一遍扫描中，完成不同的任务。遍可以和阶段相对应，也可无关。单遍代码不太有效。遍是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。5.“运算符与运算对象

4、类型不符”属于语义错误6.算法逻辑上的错误属于语义错误第二章高级语言及其语法描述1.程序语言是由语法和语义两方面定义的。2.上下文无关文法的定义：四个组成部分：一组终结符号、一组非终结符号、一个开始符号、一组产生式。一个上下文无关文法G是一个四元式（VT,VN,S,P），其中:VT：是非空有限集，它的每个元素是终结符号；VN：是非空有限集，它的每个元素是非终结符号，VT∩VN=Φ，VT∪VN=V;S：S∈VN，称为开始符号；P：产生式集合（有限），每个产生式形式是{P->α

5、P∈VN，α∈(VT∪V

6、N)*，S至少一次为P}；3.推导、最左推导、最右推导：1、推导：如两个串u0、un，存在一个串序列u0=>u1=>…=>un，则我们称这个序列是从u0到un的一个推导。U1un：表示从u0出发，经一步或若干步，可推导出un.U1un：表示从u0出发，经0步或若干步，可推导出un.最左推导是指，任何一步α=>β都是对α中的最左非终结符进行替换的。最右推导是指，任何一步α=>β都是对α中的最右非终结符进行替换的。4.语法树：在编译中产生语法树是为了语法分析。5、什么是句型？什么是句子？什么是语言？假定

7、G是一个文法，S是它的开始符号。如果S=>α，则称α是一个句型。仅含终结符的句型是一个句子。文法G所产生的句子的全体是一个语言。语言是由句子组成的集合，是由一组记号所构成的集合。6.乔姆斯基把文法分成4种类型，即0型文法、1型文法、2型文法和3型文法。0型文法也称为短语文法。1型文法也称为上下文有关文法。2型文法也称为上下文无关文法。3型文法也称为正规文法。与程序语言语法有关的文法是上下文无关文法。第三章词法分析1.状态转换图：使用状态转换图是设计词法分析程序的一种好途径，状态转换图是一张有限方向图

8、。在状态转换图中，结点代表状态，用圆圈表示。一个状态转换图可用于识别（或接受）一定的字符串。2.确定的有限自动机（DFA）、非确定有限自动机（NFA）。五元式：有限状态集合、有穷字母表、转换函数、唯一的初始状态、终止状态集合。一个确定有限自动机（DFA）M是一个五元式：M＝(S,∑,δ,s0,F)，其中S是一个有限集，它的每个元素称为一个状态，∑是一个有穷字母表，它的每个元素称为一个输入字符，δ是一个从S×∑至S的单值部分映射。δ(s,a)=s´意味着：当现行状态为、输入字符为a时，将转换到下一状态

9、s´。我们称s´为s的一个后继状s0∈S是唯一的初态F是一个终态集（可空）。一个非确定有限自动机（NFA）M是一个五元式：M＝(S,∑,δ,S0,F)，其中S是一个有限集，它的每个元素称为一个状态，∑是一个有穷字母表，它的每个元素称为一个输入字符，δ是一个从S×∑*至S的子集的映射，即δ：S×∑*→2s，S0∈S是唯一的初态，F是一个终态集（可空）。3.设有确定的有限自动机DFAM=({0,1,2,3},{a,b},δ,0,{3})，其中δ为:δ(0,a)=1δ(0,