08计算机函授编译原理a卷答案及评分标准

《08计算机函授编译原理a卷答案及评分标准》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2008计算机函授本科编译原理期末试卷（A）答案及评分标准一、填空题(20分，每空2分)1、传值；传地址2、从左向右分析；最右推导的逆过程；向右查看K个输入符3、二义性的4、最左素短语5、2006、aab*d-abd*-*d/-7、词法分析器二、选择题（20分，每个选项2分）1、D2、B3、D4、B5、C6、C7、C8、D9、D10、A三、简答题(10分)1、　因为存在推导序列:EE+TE+*F所以E+T*F是文法G[E]的一个句型(2分)　　句型E+T*F的　　短语有:E+T*F,T*F(2分)　　直接短语有:T*

2、F(1分)　　句柄为:T*F(1分)2、最左推导N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>06DD=>062D=>0625（2分）最右推导N=>ND=>N5=>ND5=>N25=>ND25=>N625=>D625=>0625（2分）四、综合应用题(50分)1、解：对应的NFA（6分）,确定化后的DFA（9分）如图所示2、　(1)将A->SB代入S的产生式，得：S->Sba

3、b　　　　消除左递归,改写为文法G1：S->bS'S’->BaS’

4、εB->ab（4分）　　　(2)在G1中，有两个关于S’的产

5、生式，它们不含左公共因子，相应的SELECT集分别如下：SELECT(S’->BaS’)=FIRSET(BaS’)={a}SELECT(S’->ε)=FOLLOW(S’)={#}SELECT(S’->BaS’)与SELECT(S’->ε)的交集为空集，所以G1是LL(1)文法　　　　（5分）　　　　(3)　　　　a　　　　　b　　　＃SS’B　　S→bS’　　　　　　　　　S’→BaS’　　　　S’→ε　　B→ab　　　　　　　　　　　　　　（4分）3、%{#include%}digit[0-9]（

6、2分）number350-{digit}{15}（3分）%%{number}{printf("该身份证号码是福建省的身份证号码");}（1分）.*{printf("该身份证号码不是福建省的身份证号码");}（1分）%%main(){yylex();return0;}（2分）intyywrap(){return1;}（1分）4、编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；中间代码生成；代码优化；目标代码生成。主要是进行词法分析和语法分析，又称为源程序分析，分析过程中发现

7、有语法错误，给出提示信息。（1）词法分析词法分析的任务是对由字符组成的单词进行处理，从左至右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。执行词法分析的程序称为词法分析程序或扫描器。源程序中的单词符号经扫描器分析，一般产生二元式：单词种别；单词自身的值。单词种别通常用整数编码，如果一个种别只含一个单词符号，那么对这个单词符号，种别编码就完全代表它自身的值了。若一个种别含有许多个单词符号，那么，对于它的每个单词符号，除了给出种别编码以外，还应给出自身的值。词法分析器

8、一般来说有两种方法构造：手工构造和自动生成。手工构造可使用状态图进行工作，自动生成使用确定的有限自动机来实现。（2）语法分析编译程序的语法分析器以单词符号作为输入，分析单词符号串是否形成符合语法规则的语法单位，如表达式、赋值、循环等，最后看是否构成一个符合要求的程序，按该语言使用的语法规则分析检查每条语句是否有正确的逻辑结构，程序是最终的一个语法单位。编译程序的语法规则可用上下文无关文法来刻画。语法分析的方法分为两种：自上而下分析法和自下而上分析法。自上而下就是从文法的开始符号出发，向下推导，推出句子。而自下而上分析

9、法采用的是移进归约法，基本思想是：用一个寄存符号的先进后出栈，把输入符号一个一个地移进栈里，当栈顶形成某个产生式的一个候选式时，即把栈顶的这一部分归约成该产生式的左邻符号。（3）中间代码生成中间代码是源程序的一种内部表示，或称中间语言。中间代码的作用是可使编译程序的结构在逻辑上更为简单明确，特别是可使目标代码的优化比较容易实现。中间代码即为中间语言程序，中间语言的复杂性介于源程序语言和机器语言之间。中间语言有多种形式，常见的有逆波兰记号、四元式、三元式和树。（4）代码优化代码优化是指对程序进行多种等价变换，使得从变换

10、后的程序出发，能生成更有效的目标代码。所谓等价，是指不改变程序的运行结果。所谓有效，主要指目标代码运行时间较短，以及占用的存储空间较小。这种变换称为优化。有两类优化：一类是对语法分析后的中间代码进行优化，它不依赖于具体的计算机；另一类是在生成目标代码时进行的，它在很大程度上依赖于具体的计算机。对于前一类优化，根据它所涉及的程序范围可分为局部优化