编译原理习题

《编译原理习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、作业一1.已知文法G[A]，写出它定义的语言描述如：G[A]:A→0B

2、1CB→1

3、1A

4、0BBC→0

5、0A

6、1CC2.给出生成下述语言的上下文无关文法：（1）{anbnambm

7、n，m>=0}(2){1n0m1m0n

8、n，m>=0}3.给出生成下述语言的三型文法：(1){anbm

9、n,m>=1}(2){anbmck

10、n,m,k>=0}4、文法G[E]为：E→E+T

11、T　　　　　　　　　　T→T*F

12、F　　　　　　　　　　F→(E)

13、i试给出句型(E+F)*i的短语，简单(直接)短语,句柄。第3章练习题一、判断题:1、编译程序中的词法分析程序以字符形

14、式的源程序作为输入，输出的单词符号常采用二元组的形式。2、正规式的运算符“

15、”读作“或“。3、若两个正规式所表示的正规集相同，则认为二者是等价的。4、用l代表字母，d代表数字，Σ={l，d}，则正规式r=dd*定义了无符号整数单词。5、一个确定的有穷自动机DFAM的转换函数f是一个从KⅹΣ到K的子集的映像。6、一个非确定的有穷自动机NFAN的转换函数f是一个从KⅹΣ*到K的映像。7、一张状态转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。8、终态与非终态是可区别的。9、对任意一个右线性文法G，都存在一个NFAM，满足L（G）=L（M）。

16、10、对任意一个右线性文法G，都存在一个DFAM，满足L（M）=L（R）。二、构造正规式1(0

17、1)*101相应的DFA.练习题2一、判断题：1、空符号串的集合{ε}={}=ф。2、设A是符号串的集合，则A0=ε。3、设G是一个文法，S是开始符号，如果S=>x且x∈VT*,则称x是文法G[S]的句型。4、在形式语言中，最右推导的逆过程也称为规范归约。5、一个语言的文法是唯一的。6、若一个语言是无穷集合，则定义该语言的文法一定是递归的。7、一个句型中出现某个产生式的右部，则此右部一定是此句型的句柄。1、每个直接短语都是某规则的右部。2、用二义性文法定义的语

18、言也是二义性的。3、文法的二义性与语言的二义性是两个不同的概念。4、任何正规文法都是上下文无关文法。5、正规文法对规则的限制比上下文无关文法对规则的限制要多一些。二、选择题（从各题的4个答案中选出一个或多个正确的答案写在横线上）（1）一般程序设计语言的描述都涉及（）3个方面。A语法B语用C语义D基本符号的确定（2）为了使编译程序能对程序设计语言进行正确的翻译，必须采用（　　　　）方法定义程序设计语言。Ａ　非形式化　Ｂ　自然语言描述问题　　　Ｃ　形式化　D自然语言和符号体系相结合（3）设x是符号串的幂运算x0=（）。A1BxCεDΦ（4）设A是符号串的集合

19、，则A*=（）。AA1∪A2∪…∪AN∪…BA0∪A1∪A2∪…∪AN∪…C{ε}∪A+DA0∪A+（5）字母表中的元素可以是（）A字母B字母和数字C数字D字母、数字和其他符号（6）文法用来描述语言的语法结构，它由如下4个部分组成：（）和文法开始符号。A文法终结符集合B文法规则的集合C文法非终结符集合D字母数字串（7）在规则中，符号“→”（：：=）表示（）。A恒等于B等于C取决于D定义为（8）在规则中，符号“

20、”表示（）。A与B或C非D定引导开关参数（9）设文法G[E]的规则如下：A→A1

21、A0

22、Aa

23、Ac

24、a

25、b

26、c,该文法的句子是下列符号串（）Aab

27、0Ba0c01CaaaDbc10(10)如果在推导过程中的任何一步α=>β,都是对α中的最右非终结符进行替换，则称这种推导为（）。A．直接推导B.最右推导C.最左推导D.规范推导（11）描述语言L={ambn

28、n≥m≥1}的文法为（）。A.S→ABbB.S→ABbA→aA

29、aA→aA

30、aB→bB

31、bB→aBb

32、bC.S→Sb

33、AD.S→aAbA→aAb

34、abA→Ab

35、aAb

36、ε(12)设有文法G[S]=（{S，B}{b},{S→bB

37、b,B→bS},S）,该文法描述的语言是（）。A.L(G[S])={bn

38、n≥0}B.L(G[S])={b2n

39、n≥0}C

40、.L(G[S])={b2n+1

41、n≥0}D.L(G[S])={b2n+1

42、n≥1}(13)一个句型最左边的（）称为该句型的句柄。A．短语B.素短语C.直接短语D.规范短语(14)设有文法G[S]：E→E+T

43、E-T

44、TT→T*F

45、T/F

46、FF→(E)

47、i该文法的句型E+T*F的句柄是下列符号串（）。AEBE+TCT*FDE+T*F(15)设有文法G[T]：T→T*F

48、FF→F^P

49、PP→(T)

50、a该文法的句型T*P^(T*F)的直接短语是下列符号串（）。A.PB.(T*F)C.T*FD.P^(T*F)(16)若一个文法满足（），则称该文法是二义文法。A.

51、文法的某一个句子存在两棵（包括两棵）以上的语法树。B.文法的某一个句子，它有两个