济南大学练习自测题

《济南大学练习自测题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章 绪论1、填空题（1）程序设计语言中参数传递的方式有_________、_________、_________和_________。（2）符号表的构造和处理方法有_________、_________和_________。2、什么是源程序？什么是目标程序？3、画图说明编译程序主要由哪几个主要部分组成？各部分的功能是什么？第二章 文法和语言1、一:文法G1:     E→ET+

2、T     T→TF*

3、F     F→FP↑

4、P     P→E

5、i （1）试证明符号串TET+*i↑是G1的一个句型(要求画出

6、语法树). （2）写出该句型的所有短语,简单短句和句柄.2、已知文法G2:     T→T*F

7、F     F→(T)

8、i （1）试给出语句(i*i)#的自上而下分析过程(填下表); （2）画出对应的语法树,指出每一步归纳的句柄.3、已知文法G(E)    　　E→T

9、E＋T    　　T→F

10、T *F    　　F→(E)

11、i    　　(1)给出句型(T *F＋i)的最右推导及画出语法树；    　　(2)给出句型(T *F＋i)的短语、素短语。4、写一个文法，使其语言是奇数集，且每个奇数不以0开头。5、目

12、标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？6、已知文法G(S)    　　S→a

13、∧

14、(T)    　　T→T，S

15、S    　　写出句子((a，a)，a)的规范归约过程及每一步的句柄。7、生成语言l={albmclanbn l>=0,m>=1,n>=2 }的文法是什么？它是chomsky那一型文法？8、设有字母表A1={a,b,…,z}，A2={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个? (2) 集合A1A2含有多少个元素? (3) 列出集合A1 (A1∪

16、A2)*中的全部长度不大于3的符号串。9、设已给文法G=(VN,VT,P,S)，其中： VN={S} VT={a1,a2,…,an,∨,∧, ~, ［,］} P={S→ai

17、i=1,2,…,n}∪{S→~S,S→［S∨S］,S→［S∧S］}， 试指出此文法所产生的语言。10、设已给文法G［〈程序〉］： 〈程序〉→〈分程序〉

18、〈复合语句〉 〈分程序〉→〈无标号分程序〉

19、〈标号〉：〈分程序〉 〈复合语句〉→〈无标号复合语句〉

20、〈标号〉：〈复合语句〉 〈无标号分程序〉→〈分程序首部〉；〈复合尾部〉 〈无标号复合语句〉

21、→begin〈复合尾部〉 〈分程序首部〉→begin〈说明〉

22、〈分程序首部〉；〈说明〉 〈复合尾部〉→〈语句〉end

23、〈语句〉；〈复合尾部〉 〈说明〉→d 〈语句〉→s 〈标号〉→L (1) 给出句子 L: L: begin d; d; s; s end 的最左推导和最右推导。 (2) 画出上述句子的语法树。11、设已给文法G［S］： S→aAcBS→BdSB→aScAB→cAB A→BaBA→aBcA→aB→b 试检验下列符号串中哪些是G［S］中的句子，给出这些句子的最左推导、最右推导和相应的语法树。 (1)

24、 aacb (2) aabacbadcd (3) aacbccb (4) aacabcbcccaacdca (5) aacabcbcccaacbca第三章 词法分析1、已知正规文法G2:     S→aS

25、A     A→bB     B→aB

26、ε 试构造一确定有限自动机DFA(要求化简),使得它接受的语言正是该文法产生的语言,要求画出状态图.2、已知文法G1: S→aB

27、ε     B→bC

28、bD     C→cB

29、c     D→d （1）试构造一个最小DFA,画出状态转换图. （2）由该DFA给出它所识别

30、的语言(用正规式表示).3、已知正规式α=ab*c*d, （1）试构造一个DFAM,其接受的语言为此α(画出图); （2）由该DFAM写出对应的正规文法。4、已知正规文法中的左线性文法      G1:S→Sa

31、Sb

32、c 试构造无ε产生式的等价右线性文法,并构造相应的确定有限自动机DFA,画出状态转换图即可.5、已知正规文法(X为开始符号)      G2: X→0Y

33、1Z

34、0      Y→0X

35、1Y

36、1      Z→1X （1）该文法产生语言是什么?请用正规式表示. （2）构造最简的确定有限自动机DFA,

37、并画出状态转换图.6、写出正规式（a

38、b）*(aa

39、bb)(a

40、b)*的DFA7、已知正规式：(8分)（1）(（a

41、b）* 

42、aa)*b和正规式（2）（a

43、b）*b,试用有限自动机的等价性证明正规式（1）和（2）是等价的,给出相应的正规文法。8、已知文法G[S]为：(6分)     S→dAB     A→aA

44、a     B→Bb

45、ε ① 试向G[S]是否为正规文法，为什么？ ② G