最全的编译原理知识点-完美总结

第一章1.程序设计语言是人与计算机联系的工具，通过程序设计语言指挥计算机按照自己的意志进行运算和操作显示信息和输出运算结果。2.最早的计算机程序设计语言是机器语言(指令系统)。机器语言中的指令都是用二进制代码直接表示的。3.机器语言和符号语言以及汇编语言都是低级程序设计语言。4.1954年FORTRANI语言的问世标志计算机高级程序设计语言的诞生。5.计算机高级程序设计语言独立于机器，比较接近于自然语言，容易学习掌握,编写程序效率高,编写的程序易读易理解易移植。6.翻译程序：将高级语言编写的程序翻译成机器语言。7.编译程序的工作过程：编译程序这要功能是将源程序翻译成等价的目标程序，这个翻译过程分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成。8.编译程序的重要意义在于它使高级语言独立于机器语言，使程序员用高级语言编写程序时不必考虑那些直接与机器有关的琐碎的环节，这些细节由编译程序区处理。9.编译程序包括：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序和目标代码生成程序以及表格处理程序和出错处理程序。10.编译程序的组织方式：编译过程分为六个阶段,改划分是编译程序的逻辑组织方式。编译过程分为前端和后端。前端包括词法分析、语法分析、语义分析、中间代码生成、代码优化。后端包括目标代码生成,依赖于计算机的硬件系统和机器指令系统。这种组织方式便于编译程序的移植，如果移植到不同类型的机器上只需修改编译程序的后端即可。11.翻译方式：编译方式和解释方式。12.源程序：用高级语言编写的程序。源程序是编译程序加工的对象。13.编译方式：先将源程序翻译成汇编语言程序或机器语言程序（目标程序），然后再执行。这个翻译程序为编译程序.14.编译方式中源程序的编译和目标程序的运行时分成两个阶段完成的。编译所的目标程序计算机暂时不能执行,必须由连接装配程序将目标程序和编译程序及系统子程序连接成一个可执行程序,这个可执行程序可直接被计算机执行。例如FORTRAN,ALGOL,PASCAL,C,C++等等。15.解释方式：对源程序边翻译边执行，按解释方式进行翻译的翻译程序为解释程序。优点在于便于对源程序调试和修改，加工处理过程慢。16.解释程序：按解释方式进行翻译的翻译程序.17.词法分析：词法分析是编译过程的基础，任务是扫描源程序，根据语言的词法规则分解和识别出每个单词，并把单词翻译成相应的机内表示。在识别单词的过程中同时也做词法检查。18.语法分析：语法分析师在词法分析的基础上进行的。任务是根据语言的语法规则把单词符号串分解成格内语法单位，如表达式、语句等。通过语法分析确定整个输入符号串是否构成一个语法正确的程序。19.语义分析：任务是对源程序进行语义检查，其目的是保证标识符和常数的正确使用，把必要的信息收集保存到符表或中间代码程序中，并进行相应的处理。20.中间代码生成：是必不可少的阶段，任务是在语法分析和语义分析基础上把语法成分的语义对其继续翻译，翻译的结果是某种中间代码形式，这种中间代码的结果简单，接近计算机的指令形式，能够很容易被翻译成计算机指令，常用的中间代码有三元式，四元式和逆波兰式。21.目标代码生成：任务:将中间代码或优化之后的中间代码转换为等价的目标代码,即机器指令或汇编语言。由中间代码很容易生成目标程序（地址指令序列）。这部分工作与机器关系密切，所以要根据机器进行。在做这部分工作时（要注意充分利用累加器），也可以进行优化处理。22.编译程序的自展、移植与自动化：高级语言的自编译性是指可以用这个语言来编写自己的编译程序。对于具有自编译性的高级语言，可运用自展技术构造其编译程序。即先对语言的核心部分构造一个小小的编译程序(可用低级语言实现)，再以它为工具构造一个能够编译更多语言成分的较大编译程序，如此扩展下去，最后形成整个编译程序。23.高级语言的自编译性：是指可以用这个语言来编写自己的编译程序。一个具有自编译性的高级语言该机其他高级语言的编译程序。24.编译程序的移植：将一个机器(宿主机)上的具有自编译性的高级语言编译程序移植到另一个机器上(目标机)。25.编译程序的自动化：在编译程序自动化中开发早和应用广泛的是分析程序生成器和语法分析程序生成器。LEX是一个有代表的性的词法分析生成器。输入的是正规表达式,输出的是词法分析器。LEX的基本思想是由正规表达式构造有穷自动机。YACC是一种基于LALR(1)文法的语法分析生成器。他接受LALR(1)文法生成一个相应的LALR(1)分析表以及一个LALR(1)分析器，而且YACC得语法分析程序可以和扫描器连接。在YACC源程序中除2型语言的规则之外，还可以包括一段语义程序指定相应的语义操作(填写,查找符号表,语义检查,生成语法树,代码生成)。LEX和YACC是关于编译程序前端的生成器。编译程序后端(代码生成,代码优化)。26.编译程序编写系统(TWS):将有助于减轻编写翻译程序(编译程序汇编程序解释程序)工作的任何软件系统或工具包统称为翻译程序编写系统。包括产生式语言的编译程序和自动分析算法的改构造程序,以及翻译程序所必须执行的各种基本操作(建立,查找符号表操作,生成目标代码,处错处理操作等)。27.TWS分为三类：第一类为自动产生编译程序的“编译程序的编译程序”,只要给出一个高级语言的语法规则和语义描述这类程序就能自动产生相应语言的编译程序。第二类为面向语法的符号加工程序。比较通用，例如表达式符号化简,数据格式转换,高级语言之间的相互转换等。当输入对象可用巴科斯范式BNF表示法加以描述时该TWS适用。第三类为由可扩充语言组成的集合。允许程序员用已有的数据类型和语句自定义新的数据类型和语句。28.规格说明：以某种方式告知计算机所需要的是什么样的程序，要求这一程序干什么。29.目标语言：是自动程序设计系统用以表示最后生成的程序的语言。30.问题范围：是指希望生成的程序的应用范围，问题范围与规格说明有关，对系统采用的方法有很大影响。31.采用方法：程序转换，知识工程等。32.串行编译程序：适合于SISD结构计算机的编译程序。33.并行编译程序：适合于SIMD和MIMD结构计算机，具有并行处理功能的编译程序。34.并行编译程序的功能：把串行的源程序和尚未充分并行化的并行源程序自动转换成并行计算机上运行的并行目标程序或它所能接受的并行源程序。35.并行编译程序的任务：实现对并行语言的翻译，受到并行语言的约束和并行计算机体系结构以及和操作系统提供的基本手段的限制。36.并行语言分为扩充式语言和全新设计语言。37.扩充式语言流行原因：向上兼容串行语言。用扩充式语言编译程序可以使串行源程序不必修改或者极少的修改就可以转换成并行程序。当前全新式并行语言不能够全面的支持并行语言。兼容性不高，不容易掌握。38.实现扩充语言编译程序的方式有：直接法：直接接受扩充式语言，并按语言的语义规则处理。间接法：接受串行源程序(或带并行指示标志的串行源程序)，并行编译程序对源程序进行并行性检查，将检测到的并行成分转换成并行语句。或者立即进行并行编译处理。39.并行粒度是对并行执行任务或者事务大小的度量。分为作业级,用户级,程序级,指令级(语句级)。作业级粒度最大，指令级粒度最小。并行编译程序应该选择适当的并行粒度。40.加速比Sp可认为是应用程序在单处理机上串行执行时间Ts和p个处理器并行执行的时间Tp之比，即Sp=Ts/Tp。分析比较并行编译程序所生成的目标程序的执行速度是可用此指标。41.并行硬件上实现神经模型和连接机制模型途径：用大量的专门的神经元器件连接成特定的模型。用通用并行计算机支持各种连接模型。第二章1.字母表：字母表是元素的非空有穷集合。字母表中的元素称为符号。2.符号串：符号的有穷序列成为符号串。什么符号也不包含的符号称为空符号串。符号串中符号的个数称为符号的长度。3.符号串相等若xy是集合上的两个符号串。且符号串的每个元素和元素的位置均相等时符号串相等。4.符号串的正闭包：A+为集合A上所有符号串的集合。5.符号串的自反闭包：A*自反闭包不包含A本身A+=AA*=A*A6.文法：文法是对语言结构的定义与描述。即从形式上用于描述和规定语言结构的称为“文法”（或称为“语法”）。对于we妇女发要研究它的句型、句子和语言。7.语法规则：我们通过建立一组规则，来描述句子的语法结构。规定用“::=”表示“由„„组成”或“定义为„„”。8.产生式的定义；设VN、VT分别是非空有限的非终结符号集和终结符号集，V=VN∪VT,VN∩VT=Φ。一个产生式是一个有序偶对（α,β）,其中α∈V+,β∈V*，通常表示为α→β或α::=β。称α为产生式的左部，称β为产生式的右部。产生式又称为重写规则，它意味着能将一个符号串用另一个符号串替换。9.文法的定义：文法G=（VN，VT，P，S）。VN：非终结符号集。VT：终结符号集。P：产生式或规则的集合。S：开始符号（识别符号）S∈VN.10.文法和语言分类Chomsky将文法分为四类：0型、1型、2型、3型。这几类文法的差别在于对产生式施加不同的限制。11.0型文法：P：α::=β其中α∈(VN∪VT)＋，β∈(VN∪VT)*0型文法称为短语结构文法。规则的左部和右部都可以是符号串，一个短语可以产生另一个短语。0型语言：L0这种语言可以用图灵机(Turing)接受。12.1型文法：P：γ1Aγ2::=γ1δγ2其中γ1,γ2∈(VN∪VT)*,A∈VN,δ∈(VN∪VT)+称为上下文有关文法或上下文敏感文法。也即只有在γ1,γ2这样的上下文中才能把A改写为δ1型语言：L1这种语言可以由一种线性界限自动机接受.13.2型文法：P：A::=δ其中A∈VN，δ∈(VN∪VT)+称为上下文无关文法。也即把A改写为δ时，不必考虑上下文。注意：2型文法与BNF表示相等价。2型语言：L2这种语言可以由下推自动机接受.14.3型文法：（右线性）P：A::=a或A::=aB其中A、B∈VN。a∈VT。3型文法称为正则文法。它是对2型文法进行进一步限制。3型语言：L3又称正则语言、正则集合这种语言可以由有穷自动机接受.根据上述分析，L0L1L2L30型文法可以产生L0、L1、L2、L3，但2型文法只能产生L2，不能产生L1。从0型文法到3型文法，各文法描述语言的能力依次减弱。15.直接推导设文法G＝(VN,VT,P,S)(α,β)∈P，γ,δ∈(VN∪VT)*则称符号串γβδ为符号串γαδ应用产生式α::=β所得到的直接推导，记为γαδ=γβδ特别有，当γ＝δ＝ε时，有α=β即每个产生式得右部都是它左部的直接推导。16.最左直接推导在xUy=》xuy直接推导中，若x属于Vt*，U属于Vn，即U是符号串最左非终结符，即最左直接推导，若每一步都是最左直接推导，称为最左推导。17.最右直接推导在xUy=》xuy直接推导中，若y属于Vt*，U属于Vn，即U是符号串最右非终结符，即最右直接推导，若每一步都是最右直接推导（规范直接推导），称为最右推导（规范推导）。18.句型：S是文法G的识别符号，若S*=u，则称u为文法G的句型。S也是。19.句子：S是文法G的识别符号，若S*=u，u属于Vt*，则U为文法G的句子。20.语言：S是文法G的识别符号,G语言L(G)={u|S*=u，u属于V*t}，即文法的语言是文法所有句子构成的集合。21.语法树：句子结构的图示表示法，它是一种有向图，由结点和有向边组成。（1）：树中每个结点都有一个标记，该标记是Vn并上Vt并上空中的一个符号。（2）：树的根节结标记是文法的标志符号S（3）：若书的一个节点至少有一个叶子结点，则该结点的标记一点是一个非终结22二义性：若对于一个文法的某一句子存在两棵不同的语法树，则该文法是二义性文法，否则是无二义性文法。（包含二义性的句子）23.无用非终结符号：如果文法的某个非终结符不出现的任何一个句型中，并且不能从它推导出非终结号串，则称该非终结符称为无用非终结符号。24.不可达