资源描述：
《2011年成人高考专升本数学模拟试题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2012-03-2121:2930人阅读评论(0)收藏举报编译原理要点第一章编译引论1、编译程序：将某一种程序设计语言写的程序翻译成等价的另一种语言的程序的程序2、源语言：用来编写源程序的语言（汇编，高级程序设计语言）3、源程序：用源语言写的程序4、目标语言：目标程序描述的语言5、目标程序：源程序经过编译后生成的程序6、宿主语言：编译程序的实现语言7、宿主机：编译程序的运行环境8、分类：解释程序【接受某语言的源程序将其直接翻译成目标代码且执行】；编译程序【接受某语言的源程序将其直接翻译成等价的目标代
2、码，然后执行且允许重复执行】；汇编程序【接受汇编源程序将其直接翻译成等价的极其语言的目标程序，然后执行且允许重复执行】9、编译执行：由编译程序生成一个与源程序等价的目标程序，完全取代源程序【笔译】10、解释执行：不生成目标程序，仅是对源程序逐句解释逐句执行【口译】11、编译程序逻辑结构：词法分析-语法分析-语义分析和中间代码生成-代码优化-目标代码生成（表格管理，出错处理）12、遍：对源程序或源程序的中间形式从头到尾扫描一遍，并做有关的分析加工，生成新的源程序的中间形式或生成目标程序13、编译程序构
3、造要素：源语言，目标语言，编译方法、技术与工具第二章形式语言自动机理论基础1、语言要素：语法（语言的描述规则），语义（语言的含义）2、元语言：描述另一个语言的语言3、字母表：元素的非空有穷集合，表中的元素称为符号，字母表也称为符号集4、符号串：由字母表中的符号组成的任何有穷序列，符号串长度指符号串x中有m个符号，长度为m5、x是一个符号串，把从x的尾部删去0个或若干个符号之后剩余的部分称为x前缀【后缀相反，不是自身称为真前缀或真后缀】6、从一个符号串中删去它的一个前缀或一个后缀之后的剩余部分称为子串
4、7、文法是一个四元组G=(Vn,Vt,S,P)Vn非空有限的非终结符号集，Vt非空有限终结符号集，S公理，P有限产生式集8、符号串的正闭包A+=A1UA^2U....UA^n；A的自反闭包为A*=A+U{E}9、语言：给定一部文法G，从G的开始符号S出发，反复使用产生式对非终结符进行替换，最后得到的终结符号串的全体10、直接推导，直接推导序列，最左推导（总是对句型中最左边的非终结符进行替换），最右推导，句型（包含非终结符），句子（只含终结符），规范推导（最右推导），规范推导得到规范句型，规范推导逆序
5、为规范归约；给定一个句子或句型其最左最右推导惟一11、递归文法：其中包括自身；直接递归（直接到自身），间接递归（经过中间到自身），左（右）递归12、语言：推导的句子a属于终结符，S能推导出a；如果L(G1)=L(G2)，则G1，G2文法等价；BNF表示法，扩充的BNF表示法13、语法树是句子结构的图形表示，代表了句子的推导结果，有利于理解句子语法结构层次；一棵语法树包括了一个句型的所有可能的推导过程14、二义文法：对一部文法，如果至少存在一个句子，有两棵不同语法树，称该句子是二义性的，包含二义性的句
6、子的文法称为二义文法。15、0型文法：对文法G中的规则不加任何限制，由图灵机来识别16、1型文法：对产生式限制aAb->aBb，上下文有关，由线性有界自动机来识别17、2型文法：A->aA属于非终结符，a属于终结符和非终结符自反闭包，上下文无关文法，由非确定的下推自动机来识别18、3型文法：A->aB,或A->aa是终结符，A，B属于非终结符，称文法G为3型文法，3型文法可由确定的有限状态自动机来识别【从0型到3型，产生式越来越严，描述功能越来越弱】19、确定的有限自动机(DFA)：M=(S,E,f
7、,S0,Z)。其中S是状态的有限集合，E是输入字符的有限集合，每个元素是一个输入字符，f状态转换函数，S0是M的惟一初态，Z是M的终态集20、DFA等价表示：DFA形式定义-状态转换图-状态矩阵21、非确定的有限自动机M(NFAM)是一个五元组M=(S,E,f,S0,Z)S0指M的非空初始状态，f状态转换函数，但这里后继状态不唯一；对任何一个NFAM，都存在一个DFAM'使L(M')=L(M)22、等价：设DFAM的两个不同状态q1,q2，如果对任意输入字符串w，从q1,q2状态出发，总是同时到达接
8、收状态或拒绝状态之中，称q1,q2等价，如果两个状态不等价，称q1,q2是可区别的23、如果从DFAM的初始状态开始，任何输入序列都不能到达的那些状态称为无关状态；如果DFAM没有无关状态，且没有彼此等价的状态，称DFAM是归约的24、DFA化简实现思想：通过删除无关状态，合并等价状态的归约过程，直到得到归约机，实现方法划分法（核心是寻找且合并等价状态）25、由正规式表示的集合称为正规集，正规式不是集合26、字母表上确定的有限自动机M所接受的语言L(M)是E上的一个正
