广东海洋大学编译原理-2016-2017学年第二学期期末考试

GDOU-B-11-302

广东海洋大学 2016——2017学年第二学期

《 编译原理 》课程试题

课程号：√

考试 √ A卷 √

闭卷

□ 考查 □ B卷

□ 开卷

题 号 一 二 三 四 五 六 总分 阅卷教师 各题分数 20 10 70 100 实得分数

注：文档及答案由Adao完善上传提供，如有疑问或不妥之处，请自行解决。

一、填空题

1、编译程序的基本任务是将源程序翻译成等价的目标程序。编译器的各个阶段的工作都涉及表格处理和出错处理。 2、将非LL（1）文法转换为等价的LL（1）文法的两种方法是消除左递归和提取左公共因子。 3、编译和解释程序的根本区别是是否生成目标代码。 4、文法G产生的句子的全体是该文法描述的语言。 5、文法G定义为四元组（Vn，Vt，P，S），其中，Vn为非终结符集，Vt为终结符集，P为产生式集合，S称作开始符号。

6、2型文法又称为上下文无关文法，3型文法又称为正规文法。3型文法可用作词法分析，2型文法可用作语法分析。

7、通常用于描述词法规则的工具有四种，NFA，DFA，正规文法，正规式。 8、假设G[S]是一个文法，如有S=>x，则称x是该文法G的句型。

二、判断题

如：并不是每个文法都能改写成LL(1)文法。 ( √)

三、问答题

1、画出编译程序的结构框图。

2、对下图中的DFA，要求：

（1）写出对应的五元组表示形式。 （2）求与该DFA等价的正规式。

答：

（1）DFA M=（{S，U，V，Q}，{a，b，c，d}，f，{S}，{Q}） 其中：

f（S，a）={U} f（S，c）={V} f（U，a）={V} f（U，b）={Q} f（V，a）={Q} f（V，b）={U}

f（Q，c）={Q}f（Q，d）={Q}

（2）等价正规式：(a|c)(ab)*(a|b)(c|d)*

3、将下图所示NFA转换为等价的DFA并最小化。

答：

4、给定文法G[S]：S->AB A->aB|bS|c B->AS|d

（1）给出每一个产生式右部的First集； （2）给出每一个非终结符号的Follow集； （3）给出每一个产生式的Select集；

（4）判断该文法是否为LL（1）文法？若是，给出该文法的预测分析表。 答：

5、已知文法G[S]：S->BA A->Bs|d B->aA|bS|c 的预测分析表如下：

S A B

a S->BA A->BS B->aA b S->BA A->BS B->bS c S->BA A->BS B->c d A->d #

（1）根据预测分析法，给出输入串adccd的分析过程

步骤 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 分析栈 #S #AB #AAa #AA #Ad #A #SB #Sc #S #AB #Ac #A #d # 剩余输出串 adccd# adccd# adccd# dccd# dccd# ccd# ccd# ccd# cd# cd# cd# d# d# # 推导用到的产生式或匹配 S->BA B->aA “a”匹配 A->d “d”匹配 A->BS B->c “c”匹配 S->BA B->c “c”匹配 A->d “d”匹配 “#”匹配(接受)

（2）判断adccd输入串是否为文法G[S]的正确句子。 答：是。