编译原理期末复习.pdf

编译原理期末复习鉴于编译原理马上就要期末考试,我将手中集中的一些资料上的题目进行了整理归类,每种类型题目给出了所涉及到的基本知识,然后对每类题目中的第一道例题进行了做法进行了讲解,剩下的例题请给大家作为练习,答案也都给出,希望对大家复习有所帮助,最后由于时间很紧,整理的有些仓促,整理中难免有遗漏或错误,请大家见谅;注：下面出现的字母中,若无特别说明,小写英文字母为终结符,大写英文字母为非终结符,希腊字母为终结符与非终结符的任意组合;1、简答题或者名词解释下面涉及到的概念中,加下划线的都是在以往一些试卷中出现的原题,务必掌握;注：这类题目老师说答案不会超过一百个字,否则写的再多也不给分,有些点到即可,不要重复啰嗦;1简述编译程序的概念及其构成答：1编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序;2构成：2简述词法分析阶段的主要任务也有可能问语法分析阶段主要任务答：词法分析的任务是输入源程序,对源程序进行扫描,识别其中的单词符号,把字符串形式的源程序转换成单词符号形式的源程序;语法分析的主要任务是对输入的单词符号进行语法分析根据语法规则进行推导或者归约,识别各类语法单位,判断输入是不是语法上正确的程序3简述编译程序的构造过程这个大家看看,是对1和2的综合答：1构造词法分析器：用于输入源程序进行词法分析,输出单词符号；2构造语法分析器：对输入的单词符号进行语法分析,识别各类语法单位,判断输入是不是语法上正确的程序3构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码;4构造优化器：对中间代码进行优化;5构造目标代码生成器：把中间的代码翻译成目标程序;6构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况;7构造错误处理程序：对出错进行处理;4说明编译和解释的区别：1编译要程序产生目标程序,解释程序是边解释边执行,不产生目标程序；2编译程序运行效率高而解释程序便于人机对话;5文法：描述语言语法结构的形式规则,一般用一个四元式表示：G=V,V,S,P,TN其中V：终结符集合非空V：非终结符集合非空,且VV=S：文法的开始符TNTN号,SVP：产生式集合有限;N6二义性文法：一个文法中存某个句子,它有两个不同的最左或者最右推导,则称该文法是二义性的;例子如文法G：S→ifexprthenS|otherS→ifexprthenSelseS句子ife1thenife2thens1elses2是二义性的;7文法的形式注：文法的形式一定要牢记,特别是2型和3型文法一定要牢记,不仅在概念题中有用,在下面的根据语言写文法题中也有重要作用,如果所写的文法形式不对,一切都是无用功……10型文法短语文法,图灵机：产生式形式为：,其中：VV且至少含有一个非TN终结符；VVTN21型上下文有关文法,线性界限自动机：产生式形式为:其中：||||,仅S例外但是S不得出现在任何产生式右部;32型文法上下文无关文法,非确定下推自动机：产生式形式为：P,PV,VV;NTN43型文法正规文法,有限自动机：右线性文法：产生式形如：AB或A其中：V；TA,BV左线性文法：产生式形如：AB或A其中：V；A,BVNTN例题：设G=V,V,S,P是一个上下文无关文法,产生集合P中的任一个产生式应具TN有什么样的形式若G是1型文法呢若G是正则文法呢上下文无关文法,产生式形式为：P,PV,VV;NTN1型文法：产生式形式为:其中：||||,仅S例外;正则文法：右线性文法：产生式形如：AB或A其中：V；A,BVTN左线性文法：产生式形如：AB或A其中：V；A,BVTN8什么是PDA下推自动机答：PDA是下推自动机,PDAM用一个七元组表示K,Σ,f,H,h0,S,ZK:有穷状态集：输入字母表有穷H:下推栈符号的有穷字母表h0:H中的初始符号f:KΣ{}H–>KHS：属于K是初始状态;Z:包含于K,是终结状态集合;9什么是DFA有穷状态自动机自动机M是一个五元式M=S,,f,S,F,其中：01S:有穷状态集,2：输入字母表有穷,3f:状态转换函数,为SS的单值部分映射,fs,a=s’表示：当现行状态为s,输入字符为a时,将状态转换到下一状态s’;我们把s’称为s的一个后继状态;4SS是唯一的一个初态；5FS：终态集可空;010推导：所谓推导就是对于一个含非终结符A的符号串,利用规则A→α,把A替换成α得到新符号串的过程;最左推导：在推导的每一步,选择符号串最左边的非终结符进行替换;最右推导：在推导的每一步,选择符号串最右边的非终结符进行替换;11归约：归约是推倒的逆过程,即用产生式的左部非终结符替换右部符号串;12什么是句型什么称为句子什么是语言句型：从文法的起始符号出发,经过有限步的推导能够推导出来的符号称