《编译原理与技术练习题汇总》由会员分享，可在线阅读，更多相关《编译原理与技术练习题汇总（31页珍藏版）》请在金锄头文库上搜索。
1、练习 1 1.1为什么高级程序语言需要编译程序？1.2 解释下列术语：源程序，目标程序，翻译程序，编译程序，解释程序1.3 简单叙述编译程序的主要工作过程。1.4 编译程序的典型体系结构包括哪些构件，主要关系如何，请用辅助图示意。1.5 编译程序的开发有哪些途径？了解你熟悉的高级编程语言编译程序的开发方式。1.6 运用编译技术的软件开发和维护工具有许多类，简单叙述每一类的主要用途。1.7了解一个真实编译系统的组成和基本功能。1.8 简单说明学习编译程序的意义和作用。1.9 如果机器H上有两个编译：一个把语言A翻译成语言B，另一个把B翻译成C，那么可以把第一个编译的输出作为第二个编译的输入，结果
2、在同一类机器上得到从A到C的编译。请用T形图示意过程和结果。练习 22.1 词法分析器的主要任务是什么？2.2 下列各种语言的输入字母表是什么？(1) C(2) Pascal(3) Java(4) C#2.3 可以把词法分析器写成一个独立运行的程序，也可以把它写成一个子程序，请比较各自的优劣。2.4 用高级语言编写一个对C#或Java程序的预处理程序，它的作用是每次调用时都把下一个完整的句子送到扫描缓冲区，去掉注释和无用的空格、制表符、回车、换行。2.5 用高级语言实现图2.5所示的Pascal语言数的状态转换图。2.6 用高级语言编程实现图2.6所示的小语言的词法扫描器。2.7 用自然语言描
3、述下列正规式所表示的语言： (1) 0(0|1)*0(2) (e|0)1)*)*(3) (a|b)*a(a|b|e) (4) (A|B|.|Z)(a|b|.|z)* (5) (aa|b)*(a|bb)* (6) (0|1|.|9|A|B|C|D|E)+(t|T)2.8 为下列语言写正规式(1) 所有以小写字母a开头和结尾的串。 (2) 所有以小写字母a开头或者结尾（或同时满足这两个条件）的串。(3) 所有表示偶数的串。(4) 所有不以0开始的数字串。(5) 能被5整除的10进制数的集合。(6) 没有出现重复数字的全体数字串。2.9 试构造下列正规式的NFA，并且确定化，然后最小化。(1) (a
4、|b)*a(a|b)(2) (a|b)*a(a|b) *(3) ab(ba|ab)*(bb|aa)*ab(4) 00|(0|1)*|11(5) 1(0|1)*01(6) 1(1010*|1(010)*1*02.10 请分别使用下面的技术证明(a|b)*，(a*|b*)*以及(a|e)b*)*这三个正规式是等价的： (1) 仅用正规式的定义及其代数性质；(2) 从正规式构造的最小DFA的同构来证明正规式的等价。2.11 构造有限自动机M，使得(1) L(M) = anbn | n 1；(2) L(M) = anbncn | n 1；(3) 它能识别S0, 1上0和1的个数都是偶数的串；(4) 它
5、能识别字母表0, 1上的串，但是串不含两个连续的0和两个连续的1；(5) 它能接受形如dd*，d*E和dd的实数，其中d=0，1，2，3，4，5，6，7，8，9。(6) 它能识别a, b上不含子串aba的所有串。2.12 分别将下列NFA确定化，并画出最小化的DFA：(a)a10a,bb(b)a40a,ba123abbba(c)eabFAa,bBCDebbaSEee2.13 下面是URL的一个极其简化的扩展正规式的描述： letter A-Za-zdigit 0-9letgit letter| digit letgit_hyphen letgit | _letgit_hyphen_string
6、 letgit_hyphen | letgit_hyphen letgit_hyphen_stringlabel letter (letgit_hyphen_string? letgit)？ URL (label.)*label (1) 请将这个URL的扩展正规改写成只含字母表A, B, 0, 1, _, .上符号的正规式； (2) 构造出识别（1）更简化的URL串的有限自动机。2.14 用某种高级语言实现(1) 将正规式转换成NFA的算法；(2) 将NFA确定化的算法；(3) 将DFA最小化的算法。2.15 描述下列语言词法记号的正规表达式：(1) 描述C浮点数的正规表达式。(2) 描述Ja
7、va表达式的正规表达式。2.16 Pascal语言的注释允许两种不同的形式：花括弧对.，以及括弧星号对(*.*)。(1) 构造一个识别这两种注释形式的DFA；(2) 用Lex的符号构造它的一个正规式。2.17 写一个Lex输入源程序，它将产生一个把C语言程序中（注释除外）的保留字全部大写。练习 33.1对于文法G3.26EE T | E+T | E-TT F | T*F | T/FF (E) | i 证明(i+T)*i是它的一个句型。3.2 给定文法G3.27SS aAcB | BdS B aScA | cAB | b A BaB | aBc | a 试检验下列符号串中哪些是G3.27 S中的
8、句子。(1) aacb (2) aabacbadcd (3) aacbccb (4) aacabcbcccaacdca (5) aacabcbcccaacbca3.3 考虑文法G3.28S S (L) | aL L, S | S(1) 指出该文法的终结符号及非终结符号。(2) 给出下列各句子的语法分析树： (a,a) (a,(a, a) (a, (a, a), (a, a) (3) 分别构造(b)中各句子的一个最左推导和最右推导。3.4 考虑文法G3.29S S aSbS | bSaS |(1) 讨论句子abab的最左推导，说明该文法是二义性的。(2) 对于句子abab构造两个相应的最右推导。
9、 (3) 对于句子abab构造两棵相应的分析树。 (4) 此文法所产生的语言是什么？3.5 文法G3.30S为： S Ac | aB A ab B bc 写出L(G3.30)的全部元素。 3.6 试描述由下列文法GS所产生的语言。 (1) S 10S0 | aA AbA | a (2) S SS | 1A0 A1A0 | (3) S 1A | B0 A1A | C BB0 | C C1C0 | (4) S bAdc AAS | a (5) S aSS Sa(6) A 0B | 1CB 1 | 1A | 0BBC 0 | 0A | 1CC3.7 设已给文法G3.31=(VN,VT,P,S)，其中
10、： VN = S VT = a1,a2,an, , , P = Sai| i=1,2,nS S, S SS, S SS，试指出此文法所产生的语言。3.8 已知文法G3.32=(A,B,C,a,b,c,A,P)，其中P由以下产生式组成：A abc A aBbcBb bB Bc CbccbC Cb aC aaBaC aa 问：此文法表式的语言是什么？3.9 已知文法 G3.33 P:P aPQR |abR RQ QR bQ bb bR bc cR cc 证明 aaabbbccc 是该文法的一个句子。3.10 构造一个文法，使其产生的语言是由算符+, *, (, ) 和运算对象a构成的算术表达式的集
11、合。3.12 已知语言L=anbbn| n1, 写出产生语言L的文法。3.13 写一文法，使其语言是偶正整数的集合。 要求：(1) 允许0打头。 (2) 不允许0打头。3.14 文法G3.34 S为： S Ac|aB, A ab B bc 该文法是否为二义的？为什么？（提示：找一个句子，使之有两棵不同的分析树。） 3.15 证明下述文法G3.35表达式是二义的： 表达式 a | (表达式) |表达式运算符表达式 运算符 + | - | * | / 3.16 下面的文法产生a的个数和b的个数相等的非空a、b串 S aB | bAB bS | aBB | b A aS | bAA | a 其中非终
12、结符B推出b比a的个数多1个的串，A则反之。(1) 证明该文法是二义的。 (2) 修改上述文法，不增加非终结符，使之成为非二义文法，并产生同样的语言。 3.17 考虑文法G3.36R RR | R | RR | R* | (R) | a | b 其中R | R表示R或R；RR表示R与R的连接；R*表示R的闭包。(1) 证明此文法生成=a, b上的除了和的所有正规表达式。 (2) 试说明此文法是二义性的。(3) 构造一个等价的无二义性文法，该文法给出*、连接和|等运算符号的优先级和结合规则。3.18 给出产生下述语言的上下文无关文法：(1) an bn am bm | n, m0。(2) 1n
13、0m1m 0n | n, m0。(3) wcwT | wa, b*，其中wT是w的逆。(4) w | wa,b+，且w中a的个数恰好比b多1 。(4) w | wa,b+，且|a|b|2|a| 。(5) w | w是不以0开始的奇数集 。3.19 设G=(VN,VT,P,S)为CFG，1,2,n为V上的符号串，试证明： 若 12n 则存在V上的符号串1,2，,n，使=12n，且有 aii (i=1,2,n)。3.20 设G=(VN,VT,P,S)为CFG，和都是V上的符号串，且 ，试证明：(1) 当的首符号为终结符号时，的首符号也必为终结符号；(2) 当的首符号为非终结符号时，则的首符号也必为非终结符号。3.21 写出下列语言的3型文法：(a) an | n0(b) anbm | n, m1 (c) anbmck | n, m, k1 3.22 已知文法G3.37 S：S dABA aA|aB |Bb 给出相应的正规式和等价的正规文法。3.23给出下列文法GA消除左递归后的等价文法：(1) A BaC | CbBB Ac | cC Bb | b (2)
