编译原理名词解释.doc

编译原理名词解释. 名词解释: 1) 前缀答:前缀——是指符号串任意首部。 2) 可归前缀答:可归前缀——是指规范句型的一个前缀,这种前缀包含句柄且不含句柄之后的任何符号。 3) 活前缀答:活前缀——规范句型的一个前缀,这种前缀不含句柄之后的任何符号。或给定文法规范句型的可归前缀的任意首部。 4) 简单短语答: 简单短语——设 G[Z] 是给定文法,w=xuy ∈ V+, 为该文法的句型, 如果满足下面两个条件:①Z xUy ;② Uu; 则称句型 xuy 中的子串 u 是句型 xuy 的简单短语。 5) 扫描遍答:扫描遍——指编译程序对源程序或中间代码程序从头到尾扫描一次。 6) 句柄答:句柄——给定句型中的最左简单短语就是句柄。 7) 句型答:句型——设G 是一个给定的文法, S 是文法的开始符号,如果 Sx( 其中 x∈ V*), 则称 x 是文法的一个句型。 8) 句子答:句子——设G 是一个给定的文法, S 是文法的开始符号,如果Sx (其中 x∈ VT* ) ,则称 x 是文法的一个句子。 9) 非终结符答:非终结符—出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。 10) 终结符答:终结符——出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。 11 )属性文法答:一个属性文法形式的定义为一个三元组 AG, AG= (G,V,E)。其中 G 为一个上下文无关文法;V 为属性的有穷集;E 为一组语义规则。 12 )语法制导翻译答:语法制导翻译——语法制导翻译就是在语法分析的过程中, 当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作,从而实现语义处理。 13 )后缀式答:后缀式——一种把运算量(操作数)写在前面,把算符写在后面(后缀)的表示法。 14 )短语答:短语——设 G[Z] 是给定文法,w=xuy ∈ V+ ,为该文法的句型, 如果满足下面两个条件:①Z xUy ;②Uu; 则称句型 xuy 中的子串 u 是句型 xuy 的短语。或:句型语法树的全部子树的叶从左到右排列起来构成的符号串均是句型的短语。 15 )基本块答:基本块——源程序或者中间代码程序中只有一个入口和一个出口的顺序执行的代码段。 16 )语义规则答:对于文法的每个产生式都配备了一组属性的计算规则,称为语义规则。 17 )语法分析答: 语法分析——按文法的产生式识别输入的符号串是否为一个句子的分析过程。 18 )四元式答: 四元式——是一个带有四个域的记录结构, 这四个域分别称为操作符域、左运算对象域、右运算对象域及运算结果域。: 什么是句子? 什么是语言? 解答:句子——设G 是一个给定的文法, S 是文法的开始符号, 如果 Sx (其中 x∈ VT* ) ,则称 x 是文法的一个句子。语言——语言是句子的集合。或——设 G[S] 是给定文法, 则由文法 G 所定义的语言 L(G) 可描述为: L(G) = {x│ Sx,x ∈ VT*} 。 DFA 与 NFA 有何区别? 解答:DFA 与 NFA 的区别表现为两个方面: 一是 NFA 可以有若干个开始状态,而 DFA 仅只有一个开始状态。另一方面, DFA 的映象 M是从K ×∑到K ,而 NFA 的映象 M 是从 K ×∑到K 的子集,即映象