编译原理所有名词解释

1/1第一章编译程序是一种程序，它把高级语言编写的源程序翻译成与之在逻辑上等价的机器语言或汇编语言的目标程序。一个高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段。如果编译生成的目标程序是汇编语言形式，那么在编译与运行阶段之间还要添加一个汇编阶段。解释程序也是一种翻译程序，它将源程序作为输入，一条语句地读入并解释执行。解释程序与编译程序的主要区别是：编译程序是将源程序翻译成目标程序后再执行该目标程序，而解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不源程序产生目标程序。编译过程可以划分成五个阶段：词法分析阶段、语法分词法分析器析阶段、语义分析和中间代码生成阶段、优化阶段和目单词符号标代码生成阶段。词法分析的任务是对构成源程序的字语法分析器表出符串进行扫描和分解，根据语言的词法规则识别出一个语法单位个具有独立意义的单词；语法分析的任务是在词法分析格错语义分析与的基础上，根据语言的语法规则（文法规则）从单词符中间代码生成器管处号串中识别出各种语法单位并进行语法检查；语义分析四元式理和中间代码生成阶段的任务是首先对每种语法单位进行理优化静态语义检查，然后分析其含义，并用另一种语言形式四元式来描述这种语义即生成中间代码；优化的任务是对前阶目标代码生成器段产生的中间代码进行等价变换或改造，以期获得更为目标程序高效（节省时间和空间）的目标代码；目标代码生成阶段的任务是把中间代码（或经优化处、理之后）变换成特编译程序结构示意图定机器上的机器语言程序或汇编语言程序，实现最终的翻译工作。自编译：用某种高级语言书写自己的编译程序。交叉编译：指用A机器上的编译程序来产生可在B机器上运行的目标代码。自展：首先确定一个非常简单的核心语言L0，然后用机器语言或汇编语言书写出它的编译程序T0：再把语言L0扩充到L1，此时有L0L1，并用L0编写L1的编译程序T1（即自编译）。移植：指A机器上的某种高级语言的编译程序稍加改动后能够在B机器上运行。第二章对程序设计语言的描述是从语法、语义和语用3个因素来考虑的。所谓语法是对语言结构的定义；语义是描述了语言的含义；语用则是从使用的角度去描述语言。形式化的方法：用一整套带有严格规定的符号体系来描述问题的方法。标识符：以字母打头的字母数字串字母表：是元素的非空有穷集合。字符：字母表中的元素称为符号，或称为字符。可以是字母、数字和其他符号。符号串：符号的有穷序列。前缀：指从末尾删除0个或多个符号后得到的符号串。后缀：指从开头删除…..（同上）符号串的运算：符号串的连接、集合的乘积、符号串的幂运算、集合的幂运算、集合A的+正闭包A与闭包A*形式语言：字母表上所有的字符按照某种规则所组成的集合。句子：均对应与字母表中的符号串。文法：是规则的非空有穷集合（描述语言的文法不唯一）文法四元组：G[S]=(VN，VT，P，S)VN：非xx集VT：xx集（VN^VT=空集）P：产生式集S：文法的开始符号直接推导：在推导过程中只使用了一个产生式。推导：经一步到多步推导出结果。（推导：用产生式的右部取代其左部的过程规约：用产生式的左部取代其右部的过程）xx推导：经0步到多步推导出结果。句型：S经0步到多步推导出x且x属于V*（V是VNVT的并集），则x是该文法的一个句型。句子：S经0步到多步推导出x且x属于VT*，则x是该文法的一个句子。句子是一种句型语言：文法G[S]产生的所有句子的集合称为文法G所定义的语言，记为L（G[S]）：L（G[S]）={x|S经一步到多步推导出x且x属于VT*}（文法给定，则语言确定）最左（右）推导：每步推导都坚持替换当前句型最左（右）边的非终结符。（最右推导也称规范推导。用规范推导出的句型称为规范句型。其逆过程是最左规约，也成为规范规约）递归规则（产生式递归）：是指在规则的左部和右部具有相同非终结符的规则。如左递归：A->A„„右递归：A->„„A递归：A->„A„文法的递归性：对于一文法若存在任一非终结符经过0步或多步可以推导出含有其自身的字符串，则该文法是递归的。（语言无穷，文法递归）（产生式集中无递归规则，文法也可能是递归的。若文法中有直接左（右）递归规则，则称该文法为左递归文法或称文法左递归）短语：直接短语：（肯定是某个产生式的右部）句柄：一个句型的最左直接短语语法树：推导的图形表示。一棵倒立的树，以开始符号作为树根，每步画分支的过程都和推导相对应。xx：语法树中任一结点连同所用分支组成的部分。对应短语简单xx：只有上下两代的子树。对应直接短语文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树（或最左推导或最右推导）则说这个文法是二义性的。（文法二义性不同语言二义性：文法二义性，有时可以找到等价的无二义性的文法，则其对应的语言无二义性；语言若有二义性，则它不存在无二义性的文法）文法和语言的分类：0型文法（无限制文法）：若文法G=（VN，VT，P，S）中的每条规则->是这样一种结构：且至少含一个非终结符，而，则称G是0型文法。对应图灵机1型文法（上下文有关文法）：若文法G=（VN，VT，P，S）中的每一条规则形式为->，其中，，则称G是1型文法。对应线型界限自动机2型文法（上下文无关文法）：若文法G=（VN，VT，P，S）中的每一条规则形式为->，其中，，则称G是2型文法。对应下推自动机3型文法（正规文法）：若文法G=（VN，VT，P，S）中的每一条规则形式为->或->，其中，，则称G是右线型文法。若文法G=（VN，VT，P，S）中的每一条规则形式为->或->，其中，，则称G是左线型文法。右线型文法和左线型文法统称3型文法。对应有穷自动机。4种文法的范围是逐渐缩小的。判别规则：根据产生式左部的xx是否为1，分为0、1和2、3，为1,为2、3型，不为1为0、1型；若为1看是否为左右线型，若为是3型，为是2型；若不为1，看左部长度是否小于等于右部，若小于等于是1型，否则是0型文法的化简：删除P->P及永远推导不出终结符号串的产生式及永远不被使用的产生式。第三章正规集：正规语言（正规文法描述的语言）的集合正规式：正规集的形式化描述，只能出现“.”连接、“|”或、“*”闭包三种运算。多数程序语言的单词都可用正规文法或正规式来描述。确定有穷自动机（DFA）：一个确定的有限自动机M是一个五元组M=（Q,Σ,f,S,Z），其中：(1)Q是一个有限状态集，它的每一个元素称为一个状态；(2)Σ是一个有穷输入字母表，它的每一个元素称为一个输入字符；(3)f是一个从Q×Σ到Q的单值映射，即f(qi,a)=qj且有qi、qj∈Q和a∈Σ；(4)S∈Q，是惟一的一个初态；(5)ZS，是一个终态集。非确定有穷自动机：一个非确定有限自动机M是一个五元组Mn=(Q,Σ,f,S,Z)，其中：(1)Q、Σ、Z的意义与DFA相同；(2)状态转换函数f不是单值函数，它是一个多值函数。是一个从S×Σ*到S的子集映射；(3)SQ，是一个非空初态集。第四章素短语：是这样一种短语，它至少包含一个终结符并且除自身外，不再包含其他素短语，有最简性。句型最左边的素短语称为最左素短语。规范句型活前缀：（1）字符串的前缀是指字符串的任意首部。如，字符串abc的前缀有空串、a、ab、abc。（2）规范句型活前缀是指规范句型的前缀，这种前缀不包含句柄右边的任何符号。LR[0]项目集规范族：构成识别一个文法活前缀的DFA的状态（项目集）的全体。冲突项目：“移进——规约”“规约——规约”冲突移进项目：形如，其中，，即圆点后面为终结符的项目，它表示期待从输入串中移进一个符号，以待形成句柄。规约项目：形如A->a.，其中，即圆点在最右端的项目，它表示一个规则的右部已分析完，句柄已形成，应该按此规则进行规约。待约项目：形如，其中，，即圆点后面为非终结符的项目，它表示期待从剩余的输入串中进行规约而得到B，然后才能继续分析A的又部。接受项目：形如，其中为文法的开始符号，即文法开始符号的规约项目。为左部的规则仅有一个，它是规约项目的特殊情况，它表示整个句子已经分析完毕，可以接受。第五章静态语义检查：(1)类型检查，如参与运算的操作数其类型应相容。(2)控制流检查，用以保证控制语句有合法的转向点。(3)一致性检查，如在相同作用域中标识符只能说明一次、case语句的标号不能相同等。直接生成目标代码的优点是编译时间短且无需中间代码到目标代码的翻译。中间代码的优点是使编译结构在逻辑上更为简单明确，特别是使目标代码的优化比较容易实现属性文法：一个属性文法是在上下文无关文法的基础上，允许每个文法符号X（终结符或非终结符）根据处理的需要，定义与X相关联的属性。文法符号的属性可分为继承属性与综合属性两类。综合属性用于“自下而上”传递信息，继承属性用于“自上而下”传递信息。语法制导翻译的基本思想：第七章代码优化：提高代码质量的技术常称为代码优化。根据是否与具体机器有关，分为两类：一类与机器有关，在目标代码上进行；一类与机器无关，在中间代码上进行。根据优化对象不同，可分为局部优化、循环优化、全局优化。常用优化技术：删除公共子表达式（删除多余运算）、代码外提、强度削弱、变换循环控制变量（删除归纳变量）、合并已知量、复习传播、删除无用赋值。局部优化：是指对代码的每一个线性部分所进行的优化，使得在这个线性部分只存在一个入口和一个出口，而这个线性部分我们称之为基本块。划分四元式程序为基本块的算法：(1)从四元式序列确定满足以下条件的入口语句：①四元式序列的第一个语句；②能由条件转移语句或无条件转移语句转移到的语句；③紧跟在条件转移语句后面的语句(2)确定满足以下条件的出口语句：①下一个xx语句的前导语句；②转移语句(包括转移语句自身)；③停语句(包括停语句自身)。循环优化：对循环中的代码可以实行代码外提、强度削弱和删除归纳变量等优化。第九章目标代码的形式：(1)能够立即执行的机器语言