编译原理题练习题测试题

1、编译程序分为哪几个逻辑阶段，各阶段的主要功能是什么？

2、考虑文法

S（L） | a

LL, S | S

（1）给出（a,（a, a））的最右推导。

（2）给出（a,（a, a））的语法分析树。

（3）该文法描述的是什么语言？

3、（20分）下面的文法描述命题演算公式

S S and S | S or S | not S | p | q |（S）

（1）它是二义的吗？

（2）如果是二义的，用某个句型的两个不同的最左推导来说明。

（3）如果是二义的，将其改为无二义的，其优先级从高到低依次是not, and, 和 or。

4、写出字母表 = {a, b}上表达下述语言的正规式。

（1）L = {w | w中a的个数是偶数}

（2）L = {w | w的最后两个字母是aa或bb}

5、（1） 把下面的NFA确定化。

（2） 将确定后的DFA化简。

6、构造一个DFA，它接受 = {0, 1}上能被5整除的二进制数。

7、叙述正规式 (00 | 11) ( (01 | 10) (00 | 11) (01 | 10) (00 | 11) ) 描述的语言。

8、为正规式(a | b) a (a | b) (a | b)构造NFA。

1、考虑文法 S -> A|SA A -> a|b|c|d|…|x|y|z

（1）给出name的最右推导（不可跳步）；

（2）给出name的语法分析树（只要最终结果）；

（3）给出该文法描述的语言（写出分析步骤）。

2、写出下图识别的单词符号的集合，并给出等价的正规式。

3、分析下图：

（1）写出下图能够识别的两个字符串。

（2）下图是DFA吗？如果不是，将下图确定化（写出详细步骤）。

4、下面的文法是否有二义性？如果有证明其二义性。

S -> S and S | S or S | not S | p | q |（S）

5、对于文法G：

S1A|0B|ε

A0S|1AA

B1S|0BB

(1)请写出两个文法G的句子。

(2)请写出两个文法G的句型。

(3)请写出001B的最左推导，并画出对应的语法分析树。

6、有文法G: SaB | bB, Ba | b, 写出它所能确定的语言（写出分析步骤）。

7、（1）什么是编译程序。

（2）编译程序主要分为哪几个逻辑阶段、并描述各阶段的功能。

8、有如下的状态转换图，与之等价的正规式为___________。（写出分析步骤）

9、考虑文法

S aSa|aBb

B x

给出aaaxbaa的最左推导（不可跳步），并给出其语法分析树

10、考虑如下文法

SaSb | A AbAc | c

abccb是该文法的一个句型吗？如果是，请证明。

11、文法共分为四类，即0型文法、1型文法、2型文法和3型文法。

(1)请写出这四类文法的相互关系。

(2)为每一类文法举一个例子，并写出为什么举该例。

12、已知不确定有限自动机如下图，写出其对应的正规式，（写出分析步骤）。

13、分析下图，把你分析得到的结论写出来。

14、设有字母表Σ={0,1}，举三个例子写出属于Σ*的字符串。

15、 写出与正规式(a|b)*等价的正规式。

16、 一个确定有限自动机M是一个五元式 M = (S, ∑, δ, s0, F)，其中，S表示________，∑表示________，δ表示________，s0表示________，F表示________。

17、（1）请写出字母表{a,b}上识别以两个a开头、两个b结尾的字符串的正规式。

（2）将上述正规式转化为NFA（写出详细步骤）

（3）将上述NFA确定化为DFA（写出详细步骤）

（4）将上述DFA化简（写出详细步骤）

（5）根据化简后的DFA写出识别“字母表{a,b}上识别以两个a开头、两个b结尾的字符串”的词法分析器伪代码。

（6）对于步骤(5)对应的词法分析器，若输出aabbabbcba，则输出结果应该是什么？

18、就下面文法

S A | SA

A 0 | 1

会推导出0、1构成的串。想办法打印0和1的串的值（如推导出110，则打印出的值为6，如果推导出010，则打印出的值为2）。

19、设文法G(S)：

　　 S→(L)|a S|a

　　 L→L，S|S

（1）根据第四章，给出左递归和回溯的定义；

（2）消除本文法的左递归和回溯。

20、谈谈你对词法分析器的看法（5分）。

第四章

练习1：构造下面文法的LL（1）分析表。

D TL T int | real

L id R R , id R |

练习2：证明练习1中的文法是否为LL(1)的。

练习3：利用练习1的分析表，给出分析器接受int id, id的分析步骤

第五章

练习4: 文法G：

EE + T | T TT * F | F F(E) | i

(1) 证明 E + T * F 是它的一个句型。

(2) 写出 E + T * F 的所有短语、直接短语和句柄。

练习5： 文法G

Sa | ∧|(T) TT,S | S

(1) 计算其firstVT和 lastVT

(2) 得出其优先关系表，该文法是否算符优先文法。

(3) 计算该文法的优先函数。

(4) 给出 ( a, ( a , a)) 的分析步骤，思路见课件。

练习6：证明下面的文法

S S A | A A a

(1)给出其项目集规范簇

(2)构造其识别活前缀的DFA

(3)画出SLR(1)分析表，该文法是否为SLR(1)文法。

(4)构造带搜索符的识别活前缀的DFA

(5)画出LR(1)分析表，该文法是否为LR(1)文法。

练习7：对于文法G: S→aS |bS | A，A→aB，B→a|b , 与该文法等价的正规式是________。

练习8：可以进行无回溯的自上而下分析的文法是________。

其他章节

练习9：程序的文法如下：

S(L) | a L L, S | S

写出语法制导定义，它输出括号嵌套的最大深度。

练习10：表达式（┐a∨b）∧（c∨d）的逆波兰表示为（ ）。1、写出下图识别的单词符号的集合，并给出等价的正规式。

2、分析下图：

（1）写出下图能够识别的两个字符串。

（2）下图是DFA吗？如果不是，将下图确定化（写出详细步骤）。

3、有文法G: SaB | bB, Ba | b, 写出它所能确定的语言（写出分析步骤）。

4、考虑文法

S aSa|aBb

B x

给出aaaxbaa的最左推导（不可跳步），并给出其语法分析树。

5、考虑如下文法

SaSb | A AbAc | c

abccb是该文法的一个句型吗？如果是，请证明。

6、已知不确定有限自动机如下图，写出其对应的正规式，（写出分析步骤）。

7、设有字母表Σ={0,1}，举三个例子写出属于Σ*的字符串。

8、 一个确定有限自动机M是一个五元式 M = (S, ∑, δ, s0, F)，其中，S表示________，∑表示________，δ表示________，s0表示________，F表示________。

9、设文法G(S)：

　　 S→(L)|aS|a

　　 L→L，S|S

（1）根据第四章，给出左递归和回溯的定义；

（2）消除本文法的左递归和回溯。

10、文法G:

E L . L | L L LB | B B 0 | 1

(1)给出非终结符的first集和follow集。

(2) 证明该文法是否为LL（1）文法。

(3) 若文法G是LL（1）文法，给出11.1的自上而下分析过程；若不是LL（1）文法，则将其转化为LL（1）文法。

11、文法G：

E aTd | ε T Eb | a

(1) 证明该文法是SLR(1)文法。

(2) 给出该文法的SLR(1)分析表。

(3) 给出 aaadbd 的规范归约分析步骤。

12、程序的文法如下：

P D

D D ; D | id : T | proc id ; D ; S

写一个语法制导定义，打印该程序一共声明了多少个id。

13、程序的文法如下：

S(L) | a L L, S | S

写出语法制导定义，它输出括号嵌套的最大深度。

14、下面的文法

BB10 B B11 B 1

(1) 写个翻译方案计算0和1的串的值（解释为二进制的正整数）。

(2) 取消左递归，重写该翻译方案。

15、给出文法，由开始符号S产生一个二进制数，计算该二进制数的值。如101.101, 其值为5.625

SL.L | L LLB | B B 0 | 1

16、将下面的语句翻译成四元式序列。请填写(1)-(10)这十个空。

while A<C∧B<D do

if A=1 then C:=C+l

else while A≤ D do

A:=A+2；

翻译成四元式如下：

100 (j<,A,C,(1)) 101(j,,,(2)）

102 (j<,B,D,(3)) 103 (j,,,(4)) 104 (j=,A,1,(5)) 105 (j,,,(6)）

106 (＋,C,1,C)

107 (j,,,(7)_________)

108 (j≤,A,D,(8)______) 109 (j,,112) 110 (＋,A,2,A) 111 (j,,,(9)) 112(j,,,(10))

17、设文法G（S）：

S→(T)|a

T→T+S|S

计算FIRSTVT和LASTVT；

FIRSTVT(S)={a,(} FIRSTVT(T)=(1) ________

LASTVT(S)=(2) ________ LASTVT(T)=(3) ________