编译原理练习题解答.doc

《编译原理练习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一.名词解释：1)前缀答：前缀——是指符号串任意首部。2)可归前缀答：可归前缀——是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。3)活前缀答：活前缀——规范句型的一个前缀，这种前缀不含句柄之后的任何符号。或给定文法规范句型的可归前缀的任意首部。4)简单短语答：简单短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:①ZxUy；②UÞu；则称句型xuy中的子串u是句型xuy的简单短语。5)扫描遍答：扫描遍——指编译程序对源程序或中间代码程序从头到尾扫描一次。6)句柄答：句柄——给定句型

2、中的最左简单短语就是句柄。7)句型答：句型——设G是一个给定的文法，S是文法的开始符号，如果Sx(其中x∈V*),则称x是文法的一个句型。*Þ8)句子答：句子——设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*），则称x是文法的一个句子。9)非终结符答：非终结符——出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。10)终结符答：终结符——出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。11）属性文法答：一个属性文法形式的定义为一个三元组AG，AG=（G，V，E）。其中G为一个

3、上下文无关文法；V为属性的有穷集；E为一组语义规则。12）语法制导翻译答：语法制导翻译——语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。13）后缀式答：后缀式——一种把运算量（操作数）写在前面，把算符写在后面（后缀）的表示法。14）短语答：短语——设G[Z]是给定文法,w=xuy∈V+，为该文法的句型,如果满足下面两个条件:①ZxUy；②Uu；则称句型xuy中的子串u是句型xuy的短语。或：句型语法树的全部子树的叶从左到右排列起来构成的符号串均是句型的短语。1

4、5）基本块答：基本块——源程序或者中间代码程序中只有一个入口和一个出口的顺序执行的代码段。16）语义规则答：对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。17）语法分析答：语法分析——按文法的产生式识别输入的符号串是否为一个句子的分析过程。18）四元式答：四元式——是一个带有四个域的记录结构，这四个域分别称为操作符域、左运算对象域、右运算对象域及运算结果域。二．简答题：1)什么是句子？什么是语言?*Þ解答：句子——设G是一个给定的文法，S是文法的开始符号，如果Sx（其中x∈VT*），则称x是文法的一个句子。语言——语言是

5、句子的集合。或——设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│Sx,x∈VT*}。2)DFA与NFA有何区别?解答:DFA与NFA的区别表现为两个方面:一是NFA可以有若干个开始状态，而DFA仅只有一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。3)自顶向下的语法分析方法的基本思想是什么?解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之

6、与给定的输入串匹配。4)自底向上的语法分析方法的基本思想是什么?解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。5)一个上下文无关文法G包括哪四个组成部分？解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。6)在自底向上的语法分析方法中，分析的关键是什么？解答:关键是寻找句柄。7)在自顶向下的语法分析方法中，分析的关键是什么？解答:关键是选择候选式。1)编译程序中语法分析器接收以什么为单位的输入？解答:接收以单词为单位的输入。2)若一个文法是递归的，则它所产生的语

7、言的句子是可枚举的吗？解答:它所产生的语言的句子不是可枚举的，而是无穷多个。3)编译程序生成的目标程序是不是一定是机器语言的程序？解答:不一定是机器语言的程序。4)词法分析器是用于做什么的？解答:词法分析器是用于识别单词的。5)“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法正确吗？解答:不正确。6)把汇编语言程序翻译成机器可执行的目标程序的工作是由什么完成的？程序代码区静态数据区栈区堆区解答:由汇编器（汇编程序）完成的。14)图示运行时存储空间的划分（分为哪几个区）。解答:一般分为静态区和动态区：程序代码区

8、、静态数据区、栈区和堆区15)词法分析的主要任务是什么？解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度