编译原理期末复习概要.doc

编译原理期末复习 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 1、简答题（或者名词解释） 下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。 注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。 （1）简述编译程序的概念及其构成 答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成： （2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务） 答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。 语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合） 答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序 3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。 6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别： 1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。 （5） 文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(VT，VN，S，P)，其中VT：终结符集合(非空) VN：非终结符集合(非空)，且VT ( VN=( S：文法的开始符号，S(VN P：产生式集合(有限)。 （6）二义性文法：一个文法中存在某个句子，它有两个不同的最左（或者最右推导），则称该文法是二义性的。 例子如文法G：S→if expr then S |other S→if expr then S else S 句子if e1 then if e2 then s1 else s2是二义性的。 （7）文法的形式（注：文法的形式一定要牢记，特别是2型和3型文法一定要牢记，不仅在概念题中有用，在下面的根据语言写文法题中也有重要作用，如果所写的文法形式不对，一切都是无用功……） 1）0型文法(短语文法，图灵机)：产生式形：其中： (VT ( VN)*且至少含有一个非终结符；(( (VT ( VN)* 2）1型(上下文有关文法，线性界限自动机)：产生式 其中：|| ( |(|，仅 S(( 例外，但是S不得出现在任何产生式右部。 3）2型文法（上下文无关文法，非确定下推自动机)：产生式形式为：P((， P(VN， ( ( (VT ( VN)* 。 4）3型文法(正规文法，有限自动机)：右线性文法：产生式形如A ( (B 或 A ( (其中：(( VT*；A，B(VN 左线性文法：产生式形如：A ( B( 或 A ( ( 其中：(( VT*；A，B(VN 例题：设G=(VT，VN，S，P)是一个上下文无关文法，产生集合P中的任一个产生式应具有什么样的形式？若G是1型文法呢？若G是正则文法呢？ 1型文法：产生式 其中：|| ( |(|，仅 S(( 例外，但是S不得出现在任何产生式右部。 正则文法：右线性文法：产生式形如A ( (B 或 A ( (其中：(( VT*；A，B(VN 左线性文法：产生式形如：A ( B( 或 A ( ( 其中：(( VT*；A，B(VN (8)什么是PDA(下推自动机)? 答：PDA是下推自动机，PDA M用一个七元组表示(K,Σ,f,H,h0,S,Z) K: 有穷状态集 (：输入字母表(有穷) H:下推栈符号的有穷字母表 h0 :H中的初始符号 f: K (（Σ({(}) ( H – K ( H* S：属于K是初始状态。 Z:包含于，是终结状态集合 (9) 什么是DFA（有穷状态自动机）? 自动机M是一个五元式M=(S, (, f, S0, F),其中： 1）S: 有穷状态集， 2） (：输入字母表(有穷)， 3） f: 状态转换函数，为S(((S的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s的