下载文档原格式
第八章 语法制导翻译和中间代码生成1．给出下面表达式的逆波兰表示(后缀式)： (1) a*(-b+c)(4) (A ∧B) ∨(⌝C ∨ D)(7) if(x+y)*z=0 then s ∶=(a+b)*c else s ∶=a*b*c解(1) ab-c+*(4) AB ∧C ⌝D ∨∨(7) xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else 运算）2. 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。
答案：三元式(1) (+ a, b) (2) (+ c, d)(3) (* (1), (2)) (4) (- (3), /) (5) (+ a, b)(6) (+,(5),c) (7) (- (4), (6)) 间接三元式间接三元式序列 间接码表 (1) (+ a, b) (1) (2) (+ c, d) (2) (3) (* (1), (2)) (3) (4) (- (3), /) (4)￥= :=*:=+ xyzs +cxa bs* c*a b(5) (- (4), (1)) (1)(6) (- (4), (5)) (5)(6)四元式(1) (+, a, b, t1) (2) (+, c, d, t2) (3) (*, t1, t2, t3) (4) (-, t3, /, t4)(5) (+, a, b, t5) (6) (+, t5, c, t6) (6) (-, t4, t6, t7)3. 采用语法制导翻译思想，表达式E 的"值"的描述如下： 产生式 语义动作(0) S ′→E {print E.VAL}(1) E →E1+E2 {E.VAL ∶=E1.VAL+E2.VAL} (2) E →E1*E2 {E.VAL ∶=E1.VAL*E2.VAL} (3) E →(E1) {E.VAL ∶=E1.VAL} (4) E →n {E.VAL ∶=n.LEXVAL}如果采用LR 分析法，给出表达式(5 * 4 + 8) * 2的语法树并在各结点注明语义值VAL 。
第2章形式语言基础2.2 设有文法G[N]: N -> D | NDD -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9(1)G[N]定义的语言是什么?(2)给出句子0123和268的最左推导和最右推导。
解答：(1)L(G[N])={(0|1|2|3|4|5|6|7|8|9)+} 或L(G[N])={α| α为可带前导0的正整数}(2)0123的最左推导：N ⇒ ND ⇒ NDD ⇒ NDDD ⇒ DDDD ⇒ 0DDD ⇒ 01DD ⇒ 012D ⇒ 0123 0123的最右推导：N ⇒ ND ⇒ N3 ⇒ ND3 ⇒ N23 ⇒ ND23 ⇒ N123 ⇒ D123 ⇒ 0123268的最左推导：N ⇒ ND ⇒ NDD ⇒ DDD ⇒ 2DDD ⇒ 26D ⇒ 268268的最右推导：N ⇒ ND ⇒ N8 ⇒ ND8 ⇒ N68 ⇒ D68 ⇒ 2682.4 写一个文法，使其语言是奇数的集合，且每个奇数不以0开头。
解答：首先分析题意，本题是希望构造一个文法，由它产生的句子是奇数，并且不以0开头，也就是说它的每个句子都是以1、3、5、7、9中的某个数结尾。
如果数字只有一位，则1、3、5、7、9就满足要求，如果有多位，则要求第1位不能是0，而中间有多少位，每位是什么数字（必须是数字）则没什么要求，因此，我们可以把这个文法分3部分来完成。
分别用3个非终结符来产生句子的第1位、中间部分和最后一位。
引入几个非终结符，其中，一个用作产生句子的开头，可以是1－9之间的数，不包括0，一个用来产生句子的结尾，为奇数，另一个则用来产生以非0整数开头后面跟任意多个数字的数字串，进行分解之后，这个文法就很好写了。
N -> 1 | 3 | 5 | 7 | 9 | BNB -> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | B02.7 下面文法生成的语言是什么？G1：S->ABA->aA| εB->bc|bBc G2：S->aA|a A->aS解答：B ⇒ bcB ⇒ bBc⇒ bbccB ⇒ bBc⇒ bbBcc ⇒ bbbccc……A ⇒εA ⇒ aA ⇒ aA ⇒ aA ⇒ aaA ⇒ aa……∴S ⇒ AB ⇒ a m b n c n , 其中m≥0,n≥1即L(G1)={ a m b n c n | m≥0,n≥1} S ⇒ aS ⇒ aA ⇒ aaS ⇒ aaaS ⇒ aA ⇒ aaS ⇒ aaaA ⇒aaaaS ⇒ aaaaa ……∴S ⇒ a2n+1 , 其中n≥0即L(G2)={ a2n+1 | n≥0}2.11 已知文法G[S]: S->(AS)|(b)A->(SaA)|(a)请找出符号串(a)和(A((SaA)(b)))的短语、简单短语和句柄。
编译原理(龙书)课后习题解答(详细)编译原理(龙书)课后题解答第一章1.1.1 ：翻译和编译的区别？答：翻译通常指自然语言的翻译，将一种自然语言的表述翻译成另一种自然语言的表述，而编译指的是将一种高级语言翻译为机器语言（或汇编语言）的过程。
1.1.2 ：简述编译器的工作过程？答：编译器的工作过程包括以下三个阶段：(1) 词法分析：将输入的字符流分解成一个个的单词符号，构成一个单词符号序列；(2) 语法分析：根据语法规则分析单词符号序列中各个单词之间的关系，确定它们的语法结构，并生成抽象语法树；(3) 代码生成：根据抽象语法树生成目标程序（机器语言或汇编语言），并输出执行文件。
1.2.1 ：解释器和编译器的区别？答：解释器和编译器的主要区别在于执行方式。
编译器将源程序编译成机器语言或汇编语言等，在运行时无需重新编译，程序会一次性运行完毕；而解释器则是边翻译边执行，每次执行都需要进行一次翻译，一次只执行一部分。
1.2.2 ：Java语言采用的是解释执行还是编译执行？答：Java一般是编译成字节码的形式，然后由Java虚拟机（JVM）进行解释执行。
但是，Java也有JIT（即时编译器）的存在，当某一段代码被多次执行时，JIT会将其编译成机器语言，提升代码的执行效率。
第二章2.1.1 ：使用BNF范式定义简单的加法表达式和乘法表达式答：<加法表达式> ::= <加法表达式> "+" <乘法表达式> | <乘法表达式><乘法表达式> ::= <乘法表达式> "*" <单项式> | <单项式><单项式> ::= <数字> | "(" <加法表达式> ")"2.2.3 ：什么是自下而上分析？答：自下而上分析是指从输入字符串出发，自底向上构造推导过程，直到推导出起始符号。
第七章
习题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),返回值是什么？
答：x是传值,而b和c是传地址方式；由函数定义可以得到：b=&c,a=&b, 而**a=**a+1=c+1=5 => c=5; *b=*b+2=c+2=7 =>c=7,**a=7;c=c+3=4+3=7
所以调用f(c,b,a)返回值是7+7+ 7=21
练习7.3.2：假设我们使用显示表来实现下图中的函数。
请给出对fib0（1）的第一次调用即将返回时的显示表。
同时指明那时在栈中的各种活动记录中保存的显示表条目
答：结果如下
第八章
练习8.2.1：假设所有的变量都存放在内存中，为下面的三地址语句生成代码：
5）下面的两个语句序列
X=b*c
Y=a+X
答：生成的代码如下
练习8.5.1：为下面的基本块构造构造DAG
d=b*c
e=a+b
b=b*c
a=e-d
答：DAG如下
练习8.6.1：为下面的每个C语言赋值语句生成三地址代码1)x=a+b*c
答：生成的三地址代码如下。
编译原理8参考答案编译原理8参考答案编译原理是计算机科学中的一门重要课程，它研究的是将高级语言转化为机器语言的过程。
在编译原理的学习过程中，学生们经常会遇到各种难题，而参考答案则是帮助他们解决这些问题的有力工具。
下面是一些编译原理8的参考答案，希望能对学习者有所帮助。
1. 什么是编译器？编译器是一种将高级语言转化为机器语言的程序。
它负责将源代码进行词法分析、语法分析、语义分析等一系列处理，最终生成可执行的目标代码。
2. 请简述编译器的工作原理。
编译器的工作原理主要包括以下几个步骤：- 词法分析：将源代码分解为一个个的词法单元。
- 语法分析：根据语法规则将词法单元组织成语法树。
- 语义分析：对语法树进行类型检查、语义检查等操作。
- 中间代码生成：将语法树转化为中间代码，比如三地址码、四元式等。
- 代码优化：对中间代码进行优化，提高程序的执行效率。
- 目标代码生成：将优化后的中间代码转化为目标机器代码。
- 目标代码优化：对目标机器代码进行优化，进一步提高执行效率。
3. 什么是词法分析？词法分析是编译器的第一步，它将源代码分解为一个个的词法单元。
词法单元包括关键字、标识符、运算符、常量等。
词法分析器通常使用正则表达式、有限自动机等方法进行实现。
4. 什么是语法分析？语法分析是编译器的第二步，它根据语法规则将词法单元组织成语法树。
语法分析器通常使用上下文无关文法和语法分析算法（如LL(1)、LR(1)等）进行实现。
5. 什么是语义分析？语义分析是编译器的第三步，它对语法树进行类型检查、语义检查等操作。
语义分析器通常使用符号表、类型检查规则等进行实现。
6. 什么是中间代码生成？中间代码生成是编译器的第四步，它将语法树转化为中间代码。
中间代码是一种介于源代码和目标代码之间的抽象表示形式，可以是三地址码、四元式、虚拟机指令等。
7. 什么是代码优化？代码优化是编译器的第五步，它对中间代码进行优化，提高程序的执行效率。
第八章习题答案2、请将算术表达式翻-（a+b）*(c+d)+(a+b+c)翻译为：（1）四元式（2）三元式（3）间接三元式答：（2）三元式（3）间接三元式间接码表：三元式：4、修改图8.5中计算声明语句中的名字的类型及相对对峙的翻译方案，以允许在一个声明中可以同时声明多个变量名。
答：翻译方案如下：P->{ offset:= 0 } DD-> D;DD->LL->id,L1 {L.type = L1.type;L.width = L1.width;enter(id,name,L.type,offset;Offset:= offset +L.width}L->:T{ L.type = T.type;L.width = T.width;}T->integer { T.type = integer; T.width:= 4 }T->real { T.type= real; T.width:= 8 }T-> array[num] of T1 { T.type:= array(num.val, T1.type);T.width:= num.val X T1.width }T->^T1 {T.type:=pointer(T1.type); T.width : = 4 }7、利用8.11的翻译方案，将下面的赋值语句翻译成三地址代码：A[i，j] = B[i,j] + C[A[k,l]]+D[i+j]答：令:域宽为wA的维数为：da1,da2, 不变部分为na, B的维数为db1,db2, 不变部分nbC的维数为dc,不变部分ncD的维数为dd,不变部分nd,t1 := i*db1t1:= t1+jt2:= B-nbt3:=w*t1t4:=t2[t3]xb = t4;t1 := k*da1t1:= t1+lt2:= A-nat3:=w*t1t4:=t2[t3]xa = t4;t1:=xa;t2:=C-nc;t3:=w*t1t4:=t2[t3]xca:=t4t1:=i+j;t2:=D-nd;t3:=w*t1;t4:=t2[t3];xd=t4;t5:=xb+xca;t6:=t5+xd;t1 := i*da1t1:= t1+jt2:= A-nat3:=w*t1t2[t3]:=t6。
第一章习题解答1.解：源程序是指以某种程序设计语言所编写的程序。
目标程序是指编译程序（或解释程序）将源程序处理加工而得的另一种语言（目标语言）的程序。
翻译程序是将某种语言翻译成另一种语言的程序的统称。
编译程序与解释程序均为翻译程序，但二者工作方法不同。
解释程序的特点是并不先将高级语言程序全部翻译成机器代码，而是每读入一条高级语言程序语句，就用解释程序将其翻译成一段机器指令并执行之，然后再读入下一条语句继续进行解释、执行，如此反复。
即边解释边执行，翻译所得的指令序列并不保存。
编译程序的特点是先将高级语言程序翻译成机器语言程序，将其保存到指定的空间中，在用户需要时再执行之。
即先翻译、后执行。
2.解：一般说来，编译程序主要由词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、信息表管理程序、错误检查处理程序组成。
3.解：C语言的关键字有：auto break case char const continuedefault do double else enum extern float for goto if int longregister return short signed sizeof static struct switch typedef union unsigned void volatile while。
上述关键字在C语言中均为保留字。
4.解：C语言中括号有三种：{}，[]，（）。
其中，{}用于语句括号；[]用于数组；（）用于函数（定义与调用）及表达式运算（改变运算顺序）。
C语言中无END关键字。
逗号在C语言中被视为分隔符和运算符，作为优先级最低的运算符，运算结果为逗号表达式最右侧子表达式的值（如：(a,b,c,d)的值为d）。
5.略第二章习题解答1.（1）答：26*26=676（2）答：26*10=260（3）答：{a,b,c,...,z,a0,a1,...,a9,aa,...,az,...,zz,a00,a01,...,zzz},共26+26*36+26*36*36=34658个2.构造产生下列语言的文法（1）{anbn|n≥0}解：对应文法为G(S) = ({S},{a,b},{ S→ε| aSb },S)（2）{anbmcp|n,m,p≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)（3）{an # bn|n≥0}∪{cn # dn|n≥0}解：对应文法为G(S) = ({S,X,Y},{a,b,c,d,#}, {S→X, S→Y,X→aXb|#,Y→cYd|# },S)（4）{w#wr# | w?{0,1}*,wr是w的逆序排列}解：G(S) = ({S,W,R},{0,1,#}, {S→W#, W→0W0|1W1|# },S)（5）任何不是以0打头的所有奇整数所组成的集合解：G(S) = ({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e, I→J|2|4|6|8, Jà1|3|5|7|9},S)（6）所有偶数个0和偶数个1所组成的符号串集合解：对应文法为 S→0A|1B|e，A→0S|1C B→0C|1S C→1A|0B3.描述语言特点（1）S→10S0S→aAA→bAA→a解：本文法构成的语言集为：L(G)={(10)nabma0n|n, m≥0}。
第八、九章习题解答参考Aho：《编译原理技术与工具》书中习题（Aho）8.3、9.6 将下面C程序，翻译为三地址码，画出流图，翻译为汇编代码main(){int i;int a[10];i = 1;while (i <= 10) {a[i] = 0; i = i + 1;}}解：三地址码为i := 1L1: if i <= 10 goto L2goto LnextL2: t1 := ct2 := 4 * it1[t2] := 0t1 := i + 1i := t1goto L1Lnext:汇编码为采取了9.7节寄存器优化算法并已进行窥孔优化：MOV 1, R0L1：CMP R0, 10J<= L2GOTO LnextL2: MOV 4, R1MUL R0, R1MOV 0, a(R1)MOV i, R1ADD 1, R1MOV R1, R0GOTO L1Lnext: 文案编辑词条B 添加义项?文案，原指放书的桌子，后来指在桌子上写字的人。
现在指的是公司或企业中从事文字工作的职位，就是以文字来表现已经制定的创意策略。
文案它不同于设计师用画面或其他手段的表现手法，它是一个与广告创意先后相继的表现的过程、发展的过程、深化的过程，多存在于广告公司，企业宣传，新闻策划等。
基本信息中文名称文案外文名称Copy目录1发展历程2主要工作3分类构成4基本要求5工作范围6文案写法7实际应用折叠编辑本段发展历程汉字"文案"(wén àn)是指古代官衙中掌管档案、负责起草文书的幕友,亦指官署中的公文、书信等;在现代，文案的称呼主要用在商业领域，其意义与中国古代所说的文案是有区别的。
在中国古代，文案亦作" 文按"。
公文案卷。
《北堂书钞》卷六八引《汉杂事》:"先是公府掾多不视事，但以文案为务。
"《晋书·桓温传》:"机务不可停废，常行文按宜为限日。
1、已知文法：A → aAd|aAb|ξ判断该文法是否是SLR（1）文法，若是构造相应分析表，并对输入串 #ab# 给出分析过程。
解：(0) A’→ A(1)A → aAd(2) A → aAb(3) A →ξ构造该文法的活前缀DFA：由上图可知该文法是SLR（1）文法。
构造SLR（1）的分析表：3、考虑文法：S →AS|b A→SA|aFollow(A) = first(S) = {b}+first(A)= {a,b}(1)列出这个文法的所有LR（0）项目(2)按（1）列出的项目构造识别这个文法活前缀的NFA，把这个NFA确定化为DFA，说明这个DFA的所有状态全体构成这个文法的LR（0）规范族。
(3)这个文法是SLR的吗？若是，构造出它的SLR分析表。
(4)这个文法是LALR或LR（1）的吗？解：（0）S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a(1)列出所有LR（0）项目：S’→·S S→·b A→·a S’→ S· S→b· A→a·S →·AS A→·SAS →A·S A→S·AS →AS· A→SA·(3)构造该文法的活前缀NFA：由上可知：I1 I3 I5 中存在着移进和归约冲突在I1中含项目：S’→ S·归约项 Follow(S’)={#}A →·a 移进项 Follow(S’)∩{a}=∮S →·b 移进项 Follow(S’)∩{b}=∮在I3中含项目：A →SA·归约项 Follow(A)={a,b}S →·b 移进项 Follow(A) ∩ {b}≠∮A →·a 移进项 Follow(A) ∩ {a}≠∮在I5中含项目：S →AS·归约项 Follow(S)={#,a,b}A →·a 移进项 Follow(S) ∩ {a}≠∮S →·b 移进项 Follow(S) ∩ {b }≠∮由此可知，I3、I5的移进与归约冲突不能解决，所以这个文法不是SLR （1）文法。
第八章习题答案
2、请将算术表达式翻-（a+b）*(c+d)+(a+b+c)翻译为：（1）四元式
（2）三元式
（3）间接三元式
答：
（2）三元式
（3）间接三元式
间接码表：
三元式：
4、修改图8.5中计算声明语句中的名字的类型及相对对峙的翻译方案，以允许在一个声明中可以同时声明多个变量名。
答：
翻译方案如下：
P->{ offset:= 0 } D
D-> D;D
D->L
L->id,L1 {
L.type = L1.type;
L.width = L1.width;
enter(id,name,L.type,offset;
Offset:= offset +L.width
}
L->:T{ L.type = T.type;
L.width = T.width;}
T->integer { T.type = integer; T.width:= 4 }
T->real { T.type= real; T.width:= 8 }
T-> array[num] of T1 { T.type:= array(num.val, T1.type);
T.width:= num.val X T1.width }
T->^T1 {T.type:=pointer(T1.type); T.width : = 4 }
7、利用8.11的翻译方案，将下面的赋值语句翻译成三地址代码：
A[i，j] = B[i,j] + C[A[k,l]]+D[i+j]
答：
令:
域宽为w
A的维数为：da1,da2, 不变部分为na, B的维数为db1,db2, 不变部分nb
C的维数为dc,不变部分nc
D的维数为dd,不变部分nd,
t1 := i*db1
t1:= t1+j
t2:= B-nb
t3:=w*t1
t4:=t2[t3]
xb = t4;
t1 := k*da1
t1:= t1+l
t2:= A-na
t3:=w*t1
t4:=t2[t3]
xa = t4;
t1:=xa;
t2:=C-nc;
t3:=w*t1
t4:=t2[t3]
xca:=t4
t1:=i+j;
t2:=D-nd;
t3:=w*t1;
t4:=t2[t3];
xd=t4;
t5:=xb+xca;
t6:=t5+xd;
t1 := i*da1
t1:= t1+j
t2:= A-na
t3:=w*t1
t2[t3]:=t6。
