编译原理 龙书 第二版 1、3章

第一章

习题1.6.3：对于图1-14中的块结构代码，假设使用常见的声明的静态作用域规则，给出其中12个声明中的每一个的作用域？

习题1.6.4：下面C代码的打印结果是什么？

答：输出结果是 3 2

调用函数b()时，a=x+1此处x为全局变量值2，故输出为3

调用函数c()时，x局部定义为1，此处a=x+1为2，故输出为2

第三章

习题3.3.2：试描述下列正则表达式定义的语言：

(1)a(a|b)*a:以a开头和以a结束的中间由任意个a或b组成的串的集合

(2)(( |a)b*)*:由0个和多个b组成的串以及由0个或多个以a开头由任意个b组成的实例所组成的串的集合

(3)(a|b)*a(a|b)(a|b)：由a或b构成的长度至少为3的且倒数第三个字符为a的串的集合

(4)a*ba*ba*ba*：由a、b构成的b的个数为3的串的集合

习题3.3.5：试写出下列语言的正则定义：

(1)包含5个元音的所有小写字母串，这些串中的元音按顺序出现

：a[bcd]*e[fgh]* i[jklmn]*o[pqrst]*u[vwxyz]*

(2)所有由按字典递增排序的小写字母组成的串

：a*b*c*d*…z*

(3)注释，即/*和*/之间的串，且串中没有不在双引号(＂)中的*/

：[/*]([a-zA-Z]|(＂*/＂))*[*/]

习题3.4.1：给出识别练习3.3.2中各个正则表达式所描述的语言的状态转换图(1)a(a|b)*a

(3)(a|b)* a(a|b)(a|b)

习题3.7.3使用算法3.23和3.20将下列正则表达式转换成DFA

(1)(a|b)*

由(a|b)*生成相应的NFA，如下图所示

由上面的NFA生成相应的DFA

1)标记集合A，A是ε-closure(1)，即A={1,2,3,5,8}

2)标记集合B，B是ε-closure（move(A,a)）={1,2,3,4,5,7,8}

3)标记集合C，C是ε-closure（move(A,b)）={1,2,3,5,6,7,8}

得到一个只含有三个状态的DFA，其中A是接受状态,其状态转换图如下

(2)(a*|b*)*

由(a*|b*)*得到相应的NFA如下图所示

由上述NFA得到相应的DFA如下

1)标记集合A，A是ε-closure(0)，即A={0,1,2,3,4,5}

2)可以得到ε-closure（move(A,a)）={0,1,2,3,4,5}=A，ε-closure（move(A,b)）={0,1,2,3,4,5}=A，故该DFA中应只有一个状态A，得到一个一状态的DFA，其状态转换图如下

编译原理龙书答案

P532.8 构建一个语法制导翻译模式，将算术表达式从后缀表示翻译成中缀表示。给出输入95-2*和952*-的注释分析树。（仅供参考一定要保证转换后的中缀表达式与原后缀表达式的优先级相同） 1 后缀算术表达式的文法如下： expr →expr expr + | expr expr – | expr expr * | expr expr / |digit digit →0 | 1 | 2 | 3 | … | 9 2 将后缀表达式翻译成中缀表达式的语法制导定义（文法+语义规则）

4 95-2*和952*-的翻译成后缀形式的语义动作与注释分析树。 expr expr expr * print(‘(‘) print(‘)‘) expr expr - 5 9 digit 2 print(‘-’) ‘9’) print(‘5’) print(‘2’) print(‘*’) 95-2*的深度优先遍历语义动作 expr expr expr - print(‘(‘) print(‘)‘) expr expr digit 2 digit 5 digit 9 print(‘*’) ‘5’) print(‘2’) print(‘9’) print(‘-’) 952*-的深度优先遍历语义动作

expr.t=(9-5)*2 expr=(9-5) expr.t=2 * expr.t=9 expr.t=5 - digit.t=5 5 digit.t=9 9 digit.t=2 2 输入为95-2*的注释分析树 expr.t=(9-5*2) expr.t=5*2 expr.t=9 - expr.t=5 expr.t=2 * digit.t=2 2 digit.t=5 5 digit.t=9 9 输入为952*-的注释分析树

编译原理第第7和第8章作业

第七章作业 练习7.2.5：在一个通过引用传递参数的语言中，有一个函数f(x,y)完成下面的计算：x=x+1;y=y+2;return x+y; 如果将a赋值为3，然后调用f(a,a)，那么返回值是什么？ 解：执行语句x=x+1，则a=a+1=4， 再执行语句y=y+2，则a=a+2=5， 最后返回x+y，则返回a+a=9。 练习7.2.6：C语言函数f的定义如下： int f(int x,*py,**ppz) { **ppz+=1;*py+=2;x+=3;return x+*py+**ppz; } 变量a是一个指向b的指针；变量b是一个指向c的指针，而c是一个当前值为4的整数变量。如果我们调用f(c,b,a)，返回值是什么？ 解：先执行语句**ppz+=1，则c=*b=**a=5， 再执行语句*py+=2，则*b=*b+2=7，c=*b=**a=7, 接着执行语句x+=3，则x=4,x=x+3=7,而c=*b=**a=7， 最后执行语句return x+*py+**ppz，则返回7+7+7=21。 练习7.3.2：假使我们使用显示表来实现下图中的函数。请给出对fib0(1)的第一次调用即将返回时的显示表。同时指明那时在栈中的各个活动记录中保存的显示表条目。 计算Fibonacci数的嵌套函数 解：

第八章练习 练习8.2.1：假设所有的变量都存放在内存中，为下面的三地址语句生成代码： 5）两个语句的序列 x=b*c y=a+x 解：生成的代码如下： LD R1, b LD R2, c MUL R1, R1, R2 ST x, R1 LD R2, a ADD R1, R2, R1 ST y, R1 练习8.2.6：确定下列指令序列的代价。 1）LD R0,y LD R1,z ADD R0,R0,R1 ST x,R0 解：2+2+1+2=7 2）LD R0,i MUL R0,R0,8 LD R1,a(R0) ST b,R1 main() fib0(4) 保存的d[2] fib1(4) 保存的d[3] fib2(4) 保存的d[4] fib1(3) 保存的d[3] fib0(2) 保存的d[2] fib1(2) 保存的d[3] fib0(1) 保存的d[2] d[1] d[2] d[3] d[4]

编译原理龙书课后部分答案(英文版)

1) What is the difference between a compiler and an interpreter? A compiler is a program that can read a program in one language - the source language - and translate it into an equivalent program in another language – the target language and report any errors in the source program that it detects during the translation process. Interpreter directly executes the operations specified in the source program on inputs supplied by the user. 2) What are the advantages of: (a) a compiler over an interpreter a. The machine-language target program produced by a compiler is usually much faster than an interpreter at mapping inputs to outputs. (b) an interpreter over a compiler? b. An interpreter can usually give better error diagnostics than a compiler, because it executes the source program statement by statement. 3) What advantages are there to a language-processing system in which the compiler produces assembly language rather than machine language? The compiler may produce an assembly-language program as its output, because assembly language is easier to produce as output and is easier to debug. 4.2.3 Design grammars for the following languages: a) The set of all strings of 0s and 1s such that every 0 is immediately followed by at least 1. S -> SS | 1 | 01 | 4.3.1 The following is a grammar for the regular expressions over symbols a and b only, using + in place of | for unions, to avoid conflict with the use of vertical bar as meta-symbol in grammars: rexpr -> rexpr + rterm | rterm rterm -> rterm rfactor | rfactor rfactor -> rfactor * | rprimary rprimary -> a | b a) Left factor this grammar. rexpr -> rexpr + rterm | rterm rterm -> rterm rfactor | rfactor rfactor -> rfactor * | rprimary rprimary -> a | b

编译原理 龙书答案

第四章部分习题解答 Aho：《编译原理技术与工具》书中习题 （Aho）4.1 考虑文法 S →( L ) | a L →L, S | S a)列出终结符、非终结符和开始符号 解： 终结符：(、)、a、， 非终结符：S、L 开始符号：S b)给出下列句子的语法树 i)(a, a) ii)(a, (a, a)) iii)(a, ((a, a), (a, a))) c)构造b)中句子的最左推导 i)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, a) ii)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, (a, S) ?(a, (a, a)) iii)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, ((L), S)) ?(a, ((L, S), S)) ?(a, ((S, S), S)) ?(a, ((a, S), S)) ?(a, ((a, a), S)) ?(a, ((a, a), (L))) ?(a, ((a, a), (L, S))) ?(a, ((a, a), (S, S))) ?(a, ((a, a), (a, S))) ?(a, ((a, a), (a, a))) d)构造b)中句子的最右推导

i)S?(L)?(L, S) ?(L, a) ?(S, a) ?(a, a) ii)S?(L)?(L, S) ? (L, (L)) ?(L, (L, S)) ?(L, (L, a)) ?(L, (S, a)) ?(L, (a, a)) ?(S, (a, a)) ?(a, (a, a)) iii)S?(L)?(L, S) ?(L, (L)) ?(L, (L, S)) ?(L, (L, (L))) ?(L, (L, (L, S))) ?(L, (L, (L, a))) ?(L, (L, (S, a))) ?(L, (L, (a, a))) ?(L, (S, (a, a))) ?(L, ((L), (a, a))) ?(L, ((L, S), (a, a))) ?(L, ((L, a), (a, a))) ?(L, ((S, a), (a, a))) ?(L, ((a, a), (S, S))) ?(S, ((a, a), (a, a))) ?(a, ((a, a), (a, a))) e)该文法产生的语言是什么 解：设该文法产生语言（符号串集合）L，则 L = { (A1, A2, …, A n) | n是任意正整数，A i=a，或A i∈L，i是1～n之间的整数} （Aho）4.2考虑文法 S→aSbS | bSaS | ε a)为句子构造两个不同的最左推导，以证明它是二义性的 S?aSbS?abS?abaSbS?ababS?abab S?aSbS?abSaSbS?abaSbS?ababS?abab b)构造abab对应的最右推导 S?aSbS?aSbaSbS?aSbaSb?aSbab?abab S?aSbS?aSb?abSaSb?abSab?abab c)构造abab对应语法树 d)该文法产生什么样的语言？ 解：生成的语言：a、b个数相等的a、b串的集合 （Aho）4.3 考虑文法 bexpr→bexpr or bterm | bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor | ( bexpr ) | true | false a)试为句子not ( true or false)构造分析树 解：

编译原理第4章作业答案

第四章 习题4.2.1：考虑上下文无关文法： S->S S +|S S *|a 以及串aa + a* (1)给出这个串的一个最左推导 S -> S S * -> S S + S * -> a S + S * -> a a + S * -> aa + a* (3)给出这个串的一棵语法分析树 习题4.3.1：下面是一个只包含符号a和b的正则表达式的文法。它使用+替代表示并运算的符号|，以避免和文法中作为元符号使用的竖线相混淆： rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 1)对这个文法提取公因子 2)提取公因子的变换使这个文法适用于自顶向下的语法分析技术吗？ 3)提取公因子之后，原文法中消除左递归 4)得到的文法适用于自顶向下的语法分析吗？ 解 1)提取左公因子之后的文法变为 rexpr→ rexpr + rterm | rterm rterm→rterm rfactor | rfactor rfactor→ rfactor * | rprimary rprimary→a | b 2)不可以，文法中存在左递归，而自顶向下技术不适合左递归文法 3)消除左递归后的文法

rexpr -> rterm rexpr’ rexpr’-> + rterm rexpr’|ε rterm-> rfactor rterm’ rterm’-> rfactor rterm’|ε rfactor-> rprimay rfactor’ rfactor’-> *rfactor’|ε rprimary-> a | b 4)该文法无左递归，适合于自顶向下的语法分析 习题4.4.1：为下面的每一个文法设计一个预测分析器，并给出预测分析表。可能要先对文法进行提取左公因子或消除左递归 (3)S->S(S)S|ε (5)S->(L)|a L->L,S|S 解 (3) ①消除该文法的左递归后得到文法 S->S’ S’->(S)SS’|ε ②计算FIRST和FOLLOW集合 FIRST(S)={(,ε} FOLLOW(S)={),$} FIRST(S’)={(,ε} FOLLOW(S’)={),$} ③ (5) ①消除该文法的左递归得到文法 S->(L)|a

龙书 第四章课后作业答案

P1774.14 为练习4.3的文法构造一个预测语法分析器 bexpr→bexpr or bterm|bterm bterm→bterm and bfactor | bfactor bfactor→not bfactor|(bexpr)|true |false 解1 非递归方法 1)消除左递归 ①bexpr→bterm A ②A→or bterm A ③A→ε ④bterm→bfactor B ⑤B→and bfactor B ⑥B→ε ⑦bfactor→not bfactor ⑧bfactor→(bexpr) ⑨bfactor→true ⑩bfactor→false 2)求first集与follow集 针对以同一非总结符开头的产生式右部求first集如果该非终结符能产生ε则需要求其follow集 ①bexpr→bterm A first(bterm A)= {not,(,true,false} ②A→or bterm A first(or bterm A)={or} ③A→εfollow(A）=follow(bexpr)= {$, )} ④bterm→bfactor B first(bfactor B)={not,(,true,false} ⑤B→and bfactor B first(and bfactor B)={and} ⑥B→εfollow(B）=follow(bterm)=first(A) 因为first(A)= {or , ε} 包含ε 所以follow(B）=follow(bterm) =first(A)∪follow(A）-{ε}={or, $, )} ⑦bfactor→not bfactor first(not bfactor)={not} ⑧bfactor→(bexpr)first((bexpr))={(} ⑨bfactor→true first(true)={true} ⑩bfactor→false first(false)={false} 表中空白处填error，表示调用错误处理程序 4)根据步骤3）编写预测分析程序 下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。 repeat

编译原理龙书第六章课后作业答案

6.1 假如有下面的Pascal说明 TYPE atype=ARRAY [0..9,-10..10] OF integer; cell=RECORD a,b:integer END; pcell=↑cell; foo=ARRAY [1..100] OF cell; FUNCTION bar(r:integer;y:cell):pcell; BEGIN……END; 写出atype,cell,pcell,foo和bar的类型表达式。 解答: atype: ARRAY(0..9, ARRAY(-10..10, integer)); cell: RECORD((a× integer)× (b×integer)); pcell: POINTER(cell); 或 : POINTER(RECORD((a ×integer)× (b× integer))); foo: ARRAY(1..100, cell); 或 : ARRAY(1..100, RECORD((a ×integer)× (b× integer))); bar: integer× cell→pcell; 或 : integer× cell→POINTER(RECORD((a×integer) ×(b×integer))); 6.4 假定类型定义如下: TYPE link=↑cell; cell=RECORD info:integer; next: link END; 下面哪些表达式结构等价？哪些名字等价？ （1）Link （2）pointer(cell) （3）pointer(Link) （4）pointer(record(info?integer)?(next ? pointer(cell))) 解答:(1)(2)(4)结构等价，无名字等价。

编译原理 龙书答案

第五章部分习题解答 Aho：《编译原理技术与工具》书中习题 （Aho）5.3 为下面表达式构造有向无环图，标出结点（子表达式）编号，+是左结合的 a + a + (a + a + a + (a + a + a + a)) 解： （Aho）5.5 设计语法制导定义，实现多项式（包含+和*，如x*(3*x+x*x)）的求导，结果无需化简，如3*x直接翻译为3*1+0*x即可。（思路：(xy)?=x?y+y?x，(x+y)?=x?+y?） 解： 综合属性diff为求导后的表示形式，val为原多项式表示形式 E→E1 + T { E.val = E1.val || “+” || E.val; E.diff = E1.diff || “+” || E.diff; } | T { E.val = T.val; E.diff = T.diff; } T→T1 * F { T.val = T1.val || “*” || F.val; T.diff = “(” || T1.diff || “*” || F.val || “+” || T1.val || “*” || F.diff || “)”; } | F { T.val = F.val; T.diff = F.diff; } F→( E ) { F.val = “(” || E.val || “)”; F.diff = “(” || E.diff || “)”; } | num { F.val = num.val; F.diff = 0; } | x { F.val = “x”; F.diff = 1; } 此题和后面两题均可编写Lex&Yacc程序进行验证。 （Aho）5.4 设计翻译模式，实现将中缀表达式翻译为无多余括号形式 解：所谓“多余括号”，可以理解为： 本该是表达式E，写成了(E)的形式， 本该是项T，写成了(T)的形式， 本该是因式F，写成了(F)的形式，因此，可写出文法和翻译模式： E→( E1 ) { E.s = E1.s; } | E1 + T { E.s = E1.s || …+? || T.s; } | T { E.s = T.s; } T→( T1 ) { T.s = T1.s; } | T1 + F { T.s = T1.s || …*? || F.s; } | F { T.s = F.s; }

编译原理 龙书 第二版 第5、6章

第五章 练习5.1.1： 对于图5-1中的SDD，给出下列表达式对应的注释语法分析树： 1）（3+4）*（5+6）n 练习5.2.4： 这个文法生成了含“小数点”的二进制数： S->L.L|L L->LB|B B->0|1 设计一个L属性的SDD来计算S.val，即输入串的十进制数值。比如，串101.101应该被翻译为十进制的5.625。提示：使用一个继承属性L.side来指明一个二进制位在小数点的哪一边。 答： 元文法消除左递归后可得到文法： S->L.L|L L->BL’ L’->BL’|ε B->0|1 使用继承属性L.side指明一个二进制位数在小数点的哪一边,2表示左边，1表示右边 使用继承属性m记录B的幂次 非终结符号L和L’具有继承属性inh、side、m和综合属性syn

练习5.3.1：下面是涉及运算符+和整数或浮点运算分量的表达式文法。区分浮点数的方法是看它有无小数点。 E-〉E+T|T T-〉num.num|num 1）给出一个SDD来确定每个项T和表达式E的类型 2）扩展（1）中得到的SDD，使得它可以把表达式转换成为后缀表达式。使用一个单目运算符intToFloat把一个整数转换为相等的浮点数 答： 练习5.4.4：为下面的产生式写出一个和例5.10类似的L属性SDD。这里的每个产生式表

示一个常见的C语言中的那样的控制流结构。你可能需要生成一个三地址语句来跳转到某个标号L，此时你可以生成语句goto L 1）S->if (C) S1 else S2 2）S->do S1 while (C) 3）S->’{’ L ‘}’; L -> LS|ε 请注意，列表中的任何语句都可以包含一条从它的内部跳转到下一个语句的跳转指令，因此简单地为各个语句按序生成代码是不够的。 第六章 练习6.1.1：为下面的表达式构造DAG （（x+y）-（（x+y）*（x-y）））+（（x+y）*（x-y）） 答：DAG如下

编译原理 第5章习题解答

第五章习题解答 5.1 设一NDPDA识别由下述CFG定义的语言，试给出这个NDPDA的完整形式描述。 S→SASC S→ε A→Aa A→b C→DcD D→d 5.2 消除下列文法的左递归： ① G[A]: A→BX∣CZ∣W B→Ab∣Bc C→Ax∣By∣Cp ② G[E]: E→ET+∣ET–∣T T→TF*∣TF/F F→(E)∣i ③ G[X]: X→Ya∣Zb∣c Y→ Zd∣Xe∣f Z→X e∣Yf∣a ④ G[A]: A→Ba|Aa|c B→Bb|Ab|d 5.3 设文法G[<语句>]： <语句>→<变量>: = <表达式>|if<表达式>then<语句> |if<表达式>then<语句>else<语句> <变量>→i <表达式>→<项>|<表达式>+<项> <项>→<因子>|<项>*<因子> <因子>→<变量>|′(′<表达式>′)′ 试构造该文法的递归下降子程序。 5.4 设文法G[E]： E→ TE' E'→ + E∣ε T→ FT' T'→ T∣ε F→ PF' F'→ *F∣ε

P→ (E)∣ a∣^ ①构造该文法的递归下降分析程序； ②求该文法的每一个非终结符的FIRST集合和FOLLOW集合； ③构造该文法的LL（1）分析表，并判断此文法是否为LL（1）文法。 5.5 设文法G[S]： S→ SbA∣aA B→ Sb A→ Bc ①将此文法改写为LL（1）文法； ②求文法的每一个非终结符的FIRST集合和FOLLOW集合； ③构造相应的LL（1）分析表。 5.6 设文法G[S]： S→ aABbcd∣ε A→ ASd∣ε B→ SAh∣eC∣ε C→ Sf∣Cg∣ε D→ aBD∣ε ①求每一个非终结符的FOLLOW集合； ②对每一个非终结符的产生式选择，构造FIRST集合； ③该文法是LL（1）文法。 5.7 设文法G[E]： E→ Aa∣Bb A→ cA∣eB B→ bd 试画出其自上而下分析程序框图。 第五章习题参考答案 5.1 解：NDPDA M=(Q,∑,H,δ,q0,F,Z0) Q={q} ∑={a,b,c,d} H={S,A,C,D,a,b,c,d} q0=q F={q} Z0=S δ: δ(q,ε,S)={(q,SASC),(q,ε)} δ(q,ε,A)={(q,Aa),(q,b)} δ(q,ε,C)={(q,DCD)} δ(q,ε,D)={(q,d)} δ(q,a,a)=(q,ε) δ(q,b,b)=(q,ε) δ(q,c,c)=(q,ε) δ(q,d,d)=(q,ε)

编译原理作业参考答案汇总

第1章引言 1、解释下列各词 源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 （结果程序）一般可由计算机直接执行。 低级语言：机器语言和汇编语言。 高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言）， 然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。 2、什么叫“遍”？ 指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。 3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。 词法分析：输入源程序，进行词法分析，输出单词符号。 语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语法正确的“程序”。 中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。 优化：对中间代码进行优化处理。 目标代码生成：把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别？ 编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。 5、有人认为编译程序的五个组成部分缺一不可，这种看法正确吗？ 编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。 6、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。

编译原理龙书答案

编译原理龙书答案

————————————————————————————————作者：————————————————————————————————日期：

第四章部分习题解答 Aho：《编译原理技术与工具》书中习题 （Aho）4.1 考虑文法 S →( L ) | a L →L, S | S a)列出终结符、非终结符和开始符号 解： 终结符：(、)、a、， 非终结符：S、L 开始符号：S b)给出下列句子的语法树 i)(a, a) ii)(a, (a, a)) iii)(a, ((a, a), (a, a))) c)构造b)中句子的最左推导 i)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, a) ii)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, (a, S) ?(a, (a, a)) iii)S?(L)?(L, S) ?(S, S) ?(a, S) ?(a, (L)) ?(a, (L, S)) ?(a, (S, S)) ?(a, ((L), S)) ?(a, ((L, S), S)) ?(a, ((S, S), S)) ?(a, ((a, S), S)) ?(a, ((a, a), S)) ?(a, ((a, a), (L))) ?(a, ((a, a), (L, S))) ?(a, ((a, a), (S, S))) ?(a, ((a, a), (a, S))) ?(a, ((a, a), (a, a))) d)构造b)中句子的最右推导

编译原理 龙书 第二版 1、3章

第一章 习题1.6.3：对于图1-14中的块结构代码，假设使用常见的声明的静态作用域规则，给出其中12个声明中的每一个的作用域？ 习题1.6.4：下面C代码的打印结果是什么？ 答：输出结果是 3 2 调用函数b()时，a=x+1此处x为全局变量值2，故输出为3 调用函数c()时，x局部定义为1，此处a=x+1为2，故输出为2 第三章 习题3.3.2：试描述下列正则表达式定义的语言： (1)a(a|b)*a:以a开头和以a结束的中间由任意个a或b组成的串的集合 (2)(( |a)b*)*:由0个和多个b组成的串以及由0个或多个以a开头由任意个b组成的实例所组成的串的集合 (3)(a|b)*a(a|b)(a|b)：由a或b构成的长度至少为3的且倒数第三个字符为a的串的集合 (4)a*ba*ba*ba*：由a、b构成的b的个数为3的串的集合 习题3.3.5：试写出下列语言的正则定义： (1)包含5个元音的所有小写字母串，这些串中的元音按顺序出现

：a[bcd]*e[fgh]* i[jklmn]*o[pqrst]*u[vwxyz]* (2)所有由按字典递增排序的小写字母组成的串 ：a*b*c*d*…z* (3)注释，即/*和*/之间的串，且串中没有不在双引号(＂)中的*/ ：[/*]([a-zA-Z]|(＂*/＂))*[*/] 习题3.4.1：给出识别练习3.3.2中各个正则表达式所描述的语言的状态转换图(1)a(a|b)*a (3)(a|b)* a(a|b)(a|b) 习题3.7.3使用算法3.23和3.20将下列正则表达式转换成DFA (1)(a|b)* 由(a|b)*生成相应的NFA，如下图所示

编译原理练习题答案[1]1汇总

一、填空题: 1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码优化等几个基本阶段,同时还会伴有表格处理和出错处理 . 1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称为编译程序. 1-03.编译方式与解释方式的根本区别在于是否生成目标代码 . 1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程 序 . 1-05.对编译程序而言,输入数据是源程序 ,输出结果是目标程序 . 1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段和运 行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: 编译阶段 , 汇编阶段和运行阶段 . 1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 1-09.编译方式与解释方式的根本区别为是否生成目标代码。 2-01.所谓最右推导是指：任何一步α β都是对α中最右非终结符进行替换的。 2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 2-03.产生式是用于定义语法成分的一种书写规则。 2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈V T*} 。 2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法的一个句型。2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个句子。3-01.扫描器的任务是从源程序中识别出一个个单词符号。 4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。 4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。 4-03.递归下降法不允许任一非终极符是直接左递归的。 4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。 4-05.递归下降分析法是自顶向上分析方法。 4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。 5-03.简单优先方法每次归约当前句型的句柄，算符优先方法每次归约当前句型的最左素短语，二者都是不断移进输入符号，直到符号栈顶出现可归约串的尾，再向前找到可归约串的头，然后归约。 5-04.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最左归约，0 的含义是向貌似句柄的符号串后查看0个输入符号。

编译原理(龙书)答案第三章

3.3.2, 3.3.6, 3.3.7, 3.3.8, 3.3.9, 3.6.3, 3.6.4, 3.6.5 3.7.1, 3.7.2, 3.7.3 3.8.1, 3.8.2 3.9.3 《编译原理》（龙书）第三章答案 3.3.2 描述下列正则表达式代表的语言。 a) a(a|b)*a b) ((ε|a)b*)* c) (a|b)*a(a|b)(a|b) d) a*ba*ba*ba* e) (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)* 答案 (a)由a开头并结尾的由a和b构成的字符串 (b)由a和b构成的字符串 (c)倒数第三位为a的由a和b构成的字符串 (d)仅含3个b的由a和b构成的字符串 (e)含有偶数个a和偶数个b的由a和b构成的字符串 注意：请准确描述语言的性质而不是列举满足正则表达式的串 3.3.6 写出满足下列定义的字符 a) The first ten letters in either upper or lower case b) The lowercase consonants c) The “digits” in a hexadecimal number d) The characters that can appear at the end of a legitimate English sentence 答案 (a)a-jA-J (b)a-j (c)0-9a-f (d).?! 3.3.7 写出匹配字符串“\ 的正则表达式 答案： \”\\

3.6.3 对于图3.29表示的NFA,列出aabb的所有路径。这个NFA能否接受aabb? 答案： aabb的所有路径 01223 00111 012000 00000 01222 00011 00123 存在路径1223和0123所以能接受aabb 3.6.4 对于图3.30表示的NFA,列出aabb的所有路径。这个NFA能否接受aabb? 答案：