当前位置:文档之家› 编译原理与技术练习题汇总

编译原理与技术练习题汇总

练习11.1 为什么高级程序语言需要编译程序?1.2 解释下列术语:源程序,目标程序,翻译程序,编译程序,解释程序1.3 简单叙述编译程序的主要工作过程。

1.4 编译程序的典型体系结构包括哪些构件,主要关系如何,请用辅助图示意。

1.5 编译程序的开发有哪些途径?了解你熟悉的高级编程语言编译程序的开发方式。

1.6 运用编译技术的软件开发和维护工具有许多类,简单叙述每一类的主要用途。

1.7 了解一个真实编译系统的组成和基本功能。

1.8 简单说明学习编译程序的意义和作用。

1.9 如果机器H上有两个编译:一个把语言A翻译成语言B,另一个把B翻译成C,那么可以把第一个编译的输出作为第二个编译的输入,结果在同一类机器上得到从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 用自然语言描述下列正规式所表示的语言:(1) 0(0|1)*0(2) ((ε|0)1)*)*(3) (a|b)*a(a|b|ε)(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|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|ε)b*)*这三个正规式是等价的:(1) 仅用正规式的定义及其代数性质;(2) 从正规式构造的最小DFA的同构来证明正规式的等价。

2.11 构造有限自动机M,使得(1) L(M) = {anbn | n ≥ 1};(2) L(M) = {anbncn | n ≥ 1};(3) 它能识别∑={0, 1}上0和1的个数都是偶数的串;(4) 它能识别字母表{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:(b) (c)(a)2.13 下面是URL的一个极其简化的扩展正规式的描述:letter → [A-Za-z]digit → [0-9]letgit → letter| digitletgit_hyphen → letgit | _letgit_hyphen_string → 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) 描述Java表达式的正规表达式。

2.16 Pascal语言的注释允许两种不同的形式:花括弧对{...},以及括弧星号对(*...*)。

(1) 构造一个识别这两种注释形式的DFA;(2) 用Lex的符号构造它的一个正规式。

2.17 写一个Lex输入源程序,它将产生一个把C语言程序中(注释除外)的保留字全部大写。

练习33.1对于文法G3.26[E]E→ T | E+T | E-TT→ F | T*F | T/FF→ (E) | i证明(i+T)*i是它的一个句型。

3.2 给定文法G3.27[S]S→ aAcB | BdSB→ aScA | cAB | bA→ BaB | aBc | a试检验下列符号串中哪些是G3.27 [S]中的句子。

(1) aacb(2) aabacbadcd(3) aacbccb(4) aacabcbcccaacdca(5) aacabcbcccaacbca3.3 考虑文法G3.28[S]S→ (L) | aL→ L, S | S(1) 指出该文法的终结符号及非终结符号。

(2) 给出下列各句子的语法分析树:①(a,a) ②(a,(a, a)) ③(a, ((a, a), (a, a)))(3) 分别构造(b)中各句子的一个最左推导和最右推导。

3.4 考虑文法G3.29[S]S→aSbS | bSaS |ε(1) 讨论句子abab的最左推导,说明该文法是二义性的。

(2) 对于句子abab构造两个相应的最右推导。

(3) 对于句子abab构造两棵相应的分析树。

(4) 此文法所产生的语言是什么?3.5 文法G3.30[S]为:S→ Ac | aBA→ abB→ bc写出L(G3.30)的全部元素。

3.6 试描述由下列文法G[S]所产生的语言。

(1) S→ 10S0 | aA A→bA | a(2) S→ SS | 1A0 A→1A0 | ε(3) S→ 1A | B0 A→1A | C B→B0 | C C→1C0 | ε(4) S→ bAdc A→A S | a(5) S→ aSS S→a(6) A → 0B | 1C B → 1 | 1A | 0BB C → 0 | 0A | 1CC3.7 设已给文法G3.31=(V N,V T,P,S),其中:V N = {S}V T = {a1,a2,…,a n,∨,∧, ~, [,]}P = {S→a i| i=1,2,…,n}∪{S→ ~S, S→[ S∨S], S → [ S∧S]},试指出此文法所产生的语言。

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 |abRRQ → QRbQ → bbbR → bccR → cc证明aaabbbccc 是该文法的一个句子。

3.10 构造一个文法,使其产生的语言是由算符+, *, (, ) 和运算对象a构成的算术表达式的集合。

3.12 已知语言L={a n bb n| n≥1}, 写出产生语言L的文法。

3.13 写一文法,使其语言是偶正整数的集合。

要求:(1) 允许0打头。

(2) 不允许0打头。

3.14 文法G3.34 [S]为:S→ Ac|aB, A→ abB→ bc该文法是否为二义的?为什么?(提示:找一个句子,使之有两棵不同的分析树。

)3.15 证明下述文法G3.35[〈表达式〉]是二义的:〈表达式〉→ a | (〈表达式〉) |〈表达式〉〈运算符〉〈表达式〉〈运算符〉→+ | - | * | /3.16 下面的文法产生a的个数和b的个数相等的非空a、b串S→ aB | bAB→ bS | aBB | bA→ aS | bAA | a其中非终结符B推出b比a的个数多1个的串,A则反之。

(1) 证明该文法是二义的。

(2) 修改上述文法,不增加非终结符,使之成为非二义文法,并产生同样的语言。

3.17 考虑文法G3.36[R]R→R '|' R | RR | R* | (R) | a | b其中R '|' R表示R或R;RR表示R与R的连接;R*表示R的闭包。

(1) 证明此文法生成∑={a, b}上的除了∅和ε的所有正规表达式。

(2) 试说明此文法是二义性的。

(3) 构造一个等价的无二义性文法,该文法给出*、连接和|等运算符号的优先级和结合规则。

3.18 给出产生下述语言的上下文无关文法:(1) { a n b n a m b m | n, m≥0}。

(2) { 1n 0m1m 0n | n, m≥0}。

(3) { ωcωT | ω∈{a, b}*},其中ωT是ω的逆。

(4) { w | w∈{a,b}+,且w中a的个数恰好比b多1 }。

(4) { w | w∈{a,b}+,且|a|≤|b|≤2|a| }。

(5) { w | w是不以0开始的奇数集}。

3.19 设G=(V N,V T,P,S)为CFG,α1,α2,…,αn为V上的符号串,试证明:若α1α2…αnβ 则存在V上的符号串β1,β2,…,βn,使β=β1β2…βn,且有a iβi(i=1,2,…,n)。

3.20 设G=(V N,V T,P,S)为CFG,α和β都是V上的符号串,且αβ,试证明:(1) 当α的首符号为终结符号时,β的首符号也必为终结符号;(2) 当β的首符号为非终结符号时,则α的首符号也必为非终结符号。

3.21 写出下列语言的3型文法:(a) {a n| n≥0}(b) {a n b m | n, m≥1}(c) {a n b m c k | n, m, k≥1}3.22 已知文法G3.37 [S]:S→ dABA→ aA|aB→ε |Bb给出相应的正规式和等价的正规文法。

3.23 给出下列文法G[A]消除左递归后的等价文法:(1) A→ BaC | CbBB→ Ac | cC→ Bb | b(2) A → B a | A a | cB → B b | A b | d(3) S→ SA | AA→ SB | B | (S) | ( )B→ [S] | [ ](4) S→ AS | bA→ SA | a(5) S→ (T) | a | εT→ S | T, S练习44.1 证明:含有左递归的文法不是LL(1)文法。

相关主题