广工编译原理试卷A

编译原理试卷A

一、选择题（每空2分，共20分）

1.一个正规语言只能对应(B)？

A 一个正规文法；

B 一个最小有限状态自动机；

2.文法G[A]：A→ε A→aB B→Ab B→a是(B)：

A 正规文法

B 二型文法

3.下面说法正确的是(A)：

A 一个SLR（1）文法一定也是LALR（1）文法

B 一个LR（1）文法一定也是LALR（1）文法

4.一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A)：

A 必要条件

B 充分必要条件

5. （ D ）不是NFA的成分。

A 由穷字母表

B 初始状态集合

C 终止状态集合

D 有限状态集合

6．（C ）不是编译程序的组成部分

A 词法分析程序

B 代码生成程序

C 设备管理程序

D 语法分析程序

7．有文法G=({S},{a},{S→SaS, S→ε},S),该文法是（ B ）。

A. LL(1)文法

B. 二义性文法 C 算符优先文法 D SLR(1)文法

8 给定文法 A→bA|cc，则符号串①cc②bcbc③bcbcc④bccbcc⑤bbbcc中，是该文法句子的是（ D ）

A ①

B ③④⑤

C ②④

D ①⑤

9 表达式A*(B-C*(C/D))的逆波兰表示为（ B ）

A. ABC-CD/**

B. ABCCD/*-*

C. ABC-*CD/*

D. 前三个选项都不对

10 LR(1)文法都是（ A ）

A 无二义性且无左递归

B 可能有二义性但无左递归

C 无二义性但可能有无左递归

D 可以既有二义性又有左递归

二、问答题

第1题(10分)将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。

G[S]：S→bSAe | bA

A→Ab | d

答：文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为：S→bB

B→SAe | A

A→d A'

A' →bA' | ε

第2题（10分）

给出与正规式R＝（ab）*（a|b*）ba等价的NFA。

答：与正规式R＝（ab）*（a|b*）ba 等价的NFA如下图

第3题（10分）将下图的NFA确定化为DFA。

答：用子集法确定化如下表

用子集法对所给图的确定化

确定化后如下图

第4题（10分）给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。G[S]为：S →BD|D

B →aD|b

D →B

答：

解:I0

第5题(10分)文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。G[M]: 1) M →VbA 2) V →d

3) V →ε 4) A →a

5) A →Aba 6) A →ε

答：对串dbba#的分析过程如下表

对输入串dbba#的分析过程

第6题

(20分)某语言的拓广文法G′为：(0) S′→T

(1) T →aBd|ε

(2) B →Tb|ε

证明G不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。

答：

拓广文法G'，增加产生式S'→T

在项目集I

0中：

有移进项目T →·aBd和归约项目T →·

存在移进-归约冲突，所以G不是LR(0)文法。

若产生式排序为：

(0) S'→T

(1) T →aBd

(2) T →ε

(3) B →Tb

(4) B →ε

G'的LR(0)项目集族及识别活前缀的DFA如下图所示：

识别G′活前缀的DFA

由产生式知：

Follow(T)={#,b}

Follow(B)= {d}

在I0中：

Follow(T) ∩{a}={# ，b} ∩{a}=

在I2中：

Follow(B) ∩{a}= {d} ∩{a}=

Follow(T) ∩{a}={# ，b} ∩{a}=

Follow(B) ∩ Follow(T) = {d}∩{# ，b}=

所以在I0，I2，中的移进-归约和归约-归约冲突可以由Follow集解决，所以G 是SLR(1)文法。

构造的SLR(1)分析表如下表。

SLR(1)分析表

第7题（10分）对产生C语言中的条件表达式的文法G[E]：E→E?E:E

写出相应的翻译文法。

答: E1 →E? {BackPatch($1.TC,NXQ);

$$.FC=$1.FC;}

E2→E1E2:{$$.place=$2.place;

$$.temp=NXQ;

GEN(j,0,0,0);

BackPatch($1,FC,NXQ);}

E2→E2E:{$$.place=$2.place;

BackPatch($1,temp,NXQ);}