编译原理套卷

编译原理试卷三

一、单项选择题。（10分）

1. 面向机器语言指的是____C__。

A、用于解决机器硬件设计问题的语言 B、特定计算机系统所固有的语言 C、各种计算机系统都通用的语言 D、只能在一台计算机上使用的语言

2.如果文法G是无二义的，则下面 D 成立。

A、文法中的句子对应两棵不同的语法树； B、文法中某个句子有两个不同的最左推导； C、文法中某个句子有两个不同的最右推导；

D、文法中任一句子，它的最左或最右推导对应的语法树相同。 3.运行阶段的存储组织与管理的目的是____C__。

① 提高编译程序的运行速度。 ② 提高目标程序的运行速度。 ③ 为运行阶段的存储分配做准备。

A、 ①② B、 ①③ C、②③ D、①②③ 4. 设有文法G[I]:I-?I1|I0|Ia|Ic|a|b|c 下列符号串中是该文法的句子的是____C__ 1 ab0 2 a0c01 3 aaa 4 bc10

可选项有 A 1 B234 C 34 D1234 5.下面说法正确的是 A 。

A、一个SLR（1）文法一定也是LALR（1）文法 B、一个LR（1）文法一定也是LALR（1）文法 二、填空题 （15分）

1.编译程序与具体的机器 无关 ，与具体的语言 有关 。 2.SLR(1)分析法中，L的含义是 自左向右进行分析 ，R含义是 采用最右推导的逆过程 ，S含义是 简单的 ，“1”的含义是 向貌似句柄的符号串的查看一个输入符号 。

4.确定的有穷自动机是一个 五元组 ，通常表示为 M（Q，∑，t,q0,F） 。

5.在大部分现有编译中采用的方案主要有两种： 动态 分配方案和___静态____分配方案。

6.假定G是一个文法，S是它的 开始符号 ，如果S * α，则称_α__是一个句型，仅含终结符号的句型是一个 句子 。文法G所产生的 句子的全体是一个 语言 ，将它记为L(G)。 三、简答题。（30分）

1.设有文法G[S]：S?aAcB|Bd A?AaB|c B?bScA|b 请给出句子acabcbbdcc的最左推导及语法树。（6分）

s->aAcB->aAaBcB->aCaBcB->acabcB->acabcbScA->acabcbBCCA->acabcbbdcc 2.判断上题是否是算符优先文法？如是，请给出算符优先关系表。（7分） 是算符优先关系。因为产生式右部不包含相邻非终结符号

firstvt(s)={a,b,d} lastvt(s)={a,b,c,d}firstvt(s)={a,c} lastvt(s)={a,b,c} firstvt(s)={b} lastvt(s)={a,b,c} a b c d a > < = > b > > = > c < < > d > 3.对于第1小题给定的文法，句型aAaBScAcB的短语、简单短语及句柄是什么？（6分） S

1

a A C B A a B b s c A

短语：bScA AabScA aAabScAcB 简单短语：bScA 句柄：bScA

4.什么是二义性文法？请用例说明文法G[E]：

E?i | (E) | EAE A? + | - | * | /是二义性文法。（6分） 一个文法如果它的一个句子有两棵或两棵以上的语法树，则称此句子具有二义性，如果一个文法含有二义性的句子，则称此文法具有二义性。 例： i+i+i

5.符号表的作用是什么？一般有哪几种结构？（5分）

在编译过程中，始终涉及对一些语法符号的处理。要用到这些符号的相关属性。符号表的作用就是保存这些成份及其相关属性，以便在用时能找到。 无序符号表 有序符号表 栈符号表 四、词法分析——确定性有穷自动机

为以下字符集编写正规表达式，并构造与之等价的最简DFA（写出详细的具体过程）： 在字母表{a,b}上的包含偶数个a且含有任意数目b的所有字符串。（15分） （b*ab*ab*）* 状态 Action GOTO a b d e f $ S R T 0 S3 1 1 acc 2 r2 S3 r2 r2 5 3 S6 S4 2 4 r4 r4 r4 r4 5 S10 9 6 7 7 S8 8 r3 r3 r3 r3 9 r1 r1 r1 10 r6 S6 S4 r6 r6 11 11 S12 12 r5 r5 r5 五、语法分析——自底向上分析法 已知文法G： S’?S S ? bRST S ?bR R?dSa R ?e T?fRa T?f （1）求文法G中每个非终结符的First集和Follow集。 （2）构造文法G的SLR(1)预测分析表。（20分）

frist(s’)={b} follow(s’)={$} frist(s)={b} follow(s)={f,a, $}

frist(R) ={d,e} follow( R )={a,b,f, $} frist(T)={t} follow (T)={a,f,#} 六、目标代码生成

把下面程序段： 104(jND,M,-,108) While AD do 105(j,-,-,106) While M V B

Else X:= X -1; 109(j,-,-,112)

翻译成四元式序列或P代码。 110(+,X,1,X) 100（j<,A,B,102） 111(j,-,-,104) 101(j,-,-,115) 112(-,X,1,X) 102(j>,C,D,104) 113(j,-,-,114) 103(j,-,-,115) 114(j,-,-,100) 115

2