编译原理所有名词解释.docx

编译程序是一种程序，它把高级语言编写的源程序翻译成与之在逻辑上等价的机器语言或汇编语言的目标程序。一个高级语言程序的执行通常分为两个阶段，即编译阶段和运行阶段。如果编译生成的目标程序是汇编语言形式，那么在编译与运行阶段之间还要添加一个汇编阶段。解释程序也是一种翻译程序，它将源程序作为输入，一条语句一条语句地读入并解释执行。解释程序与编译程序的主要区别是：编译程序是将源程序翻译成目标程序后再执行该目标程序，而解释程序则是逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。编译过程可以划分成五个阶段：词法分析阶段、语法分析阶段、语义分析和中间代码生成阶段、优化阶段和目标代码生成阶段。词法分析的任务是对构成源程序的字符串进行扫描和分解，根据语言的词法规则识别出一个个具有独立意义的单词；语法分析的任务是在词法分析的基础上，根据语言的语法规则（文法规则）从单词符号串中识别出各种语法单位并进行语法检查；语义分析和中间代码生成阶段的任务是首先对每种语法单位进行静态语义检查，然后分析其含义，并用另一种语言形式来描述这种语义即生成中间代码；优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效（节省时间和空间）的目标代码；目标代码生成阶段的任务是把中间代码（或经优化处、理之后）变换成特 编译程序结构示意图定机器上的机器语言程序或汇编语言程序，实现最终的翻译工作。形式化的方法：用一整套带有严格规定的符号体系来描述问题的方法。标识符：以字母打头的字母数字串字母表：是元素的非空有穷集合。字符：字母表中的元素称为符号，或称为字符。可以是字母、数字和其他符号。符号串的运算：符号串的连接、集合的乘积、符号串的幂运算、集合的幂运算、集合A的正闭包A+与闭包A*形式语言：字母表上所有的字符按照某种规则所组成的集合。句子：均对应与字母表中的符号串。文法：是规则的非空有穷集合 （描述语言的文法不唯一）文法四元组：GS=(VN，VT，P，S) VN ：非终结符集 VT：终结符集 （VN VT=空集）P：产生式集S：文法的开始符号直接推导：在推导过程中只使用了一个产生式。推导：经一步到多步推导出结果。（推导：用产生式的右部取代其左部的过程 规约：用产生式的左部取代其右部的过程）广义推导：经0步到多步推导出结果。句型：S经0步到多步推导出x且x属于V*（V是VNVT的并集），则x是该文法的一个句型。句子：S经0步到多步推导出x且x属于VT*，则x是该文法的一个句子。句子是一种句型语言：文法GS产生的所有句子的集合称为文法G所定义的语言，记为L（GS）： L（GS）=x|S经一步到多步推导出x且x属于VT* （文法给定，则语言确定）最左（右）推导：每步推导都坚持替换当前句型最左（右）边的非终结符。（最右推导也称规范推导。用规范推导推导出的句型称为规范句型。其逆过程是最左规约，也成为规范规约）递归规则（产生式递归）：是指在规则的左部和右部具有相同非终结符的规则。如 左递归：A-A右递归：A-A 递归：A-A文法的递归性：对于一文法若存在任一非终结符经过0步或多步可以推导出含有其自身的字符串，则该文法是递归的。（语言无穷，文法递归）（产生式集中无递归规则，文法也可能是递归的。若文法中有直接左（右）递归规则，则称该文法为左递归文法或称文法左递归）句柄：一个句型的最左直接短语语法树：推导的图形表示。一棵倒立的树，以开始符号作为树根，每步画分支的过程都和推导相对应。子树：语法树中任一结点连同所用分支组成的部分。对应短语简单子树：只有上下两代的子树。对应直接短语文法的二义性：如果一个文法存在某个句子对应两棵不同的语法树（或最左推导或最右推导）则说这个文法是二义性的。（文法二义性不同语言二义性：文法二义性，有时可以找到等价的无二义性的文法，则其对应的语言无二义性；语言若有二义性，则它不存在无二义性的文法）句子的二义性:文法GS的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。LL(1)的含义：(LL(1)文法是无二义的；LL(1)文法不含左递归)第1个L：从左到右扫描输入串第2个L：生成的是最左推导1：向右看1个输入符号便可决定选择哪个产生式某些非LL(1)文法到LL(1)文法的等价变换:1.提取公因子2.消除左递归。文法和语言的分类：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种文法的范围是逐渐缩小的。判别规则：根据产生式左部的长度是否为1，分为0、1和 2、3，为1,为2、3型，不为1为0、1型；若为1看是否为左右线型，若为是3型，为是2型；若不为1，看左部长度是否小于等于右部，若小于等于是1型，否则是0型正规集：正规语言（正规文法描述的语言）的集合正规式：正规集的形式化描述，只能出现“.”连接、“|”或、“*”闭包三种运算。多数程序语言的单词都可用正规文法或正规式来描述。素短语：是这样一种短语，它至少包含一个终结符并且除自身外，不再包含其他素短语，有最简性。句型最左边的素短语称为最左素短语。规范句型活前缀：（1）字符串的前缀是指字符串的任意首部。如，字符串abc的前缀有空串、a、ab、abc。（2）规范句型活前缀是指规范句型的前缀，这种前缀不包含句柄右边的任何符号。LR0项目集规范族：构成识别一个文法活前缀的D