下载文档原格式
第八章 语法制导翻译和中间代码生成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、已知文法：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）文法。
第七章
习题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
答：生成的三地址代码如下。
第一章练习题（绪论）一、选择题1．编译程序是一种常用的软件。
A) 应用B) 系统C) 实时系统D) 分布式系统2．编译程序生成的目标代码程序是可执行程序。
A) 一定B) 不一定3．编译程序的大多数时间是花在上。
A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。
A)提高编译程序的执行效率；B)使编译程序的结构更加清晰，提高目标程序质量；C)充分利用内存空间，提高机器的执行效率。
5．编译程序各个阶段都涉及到的工作有。
A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。
A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。
A) 多遍扫描B) 一遍扫描8．编译方式与解释方式的根本区别在于。
A) 执行速度的快慢B) 是否生成目标代码C) 是否语义分析9．多遍编译与一遍编译的主要区别在于。
A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部分只执行一遍；B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程序重复多遍分析再执行；C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直接分析执行；D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调用执行完成。
10．编译程序分成“前端”和“后端”的好处是A)便于移植B)便于功能的扩充C)便于减少工作量D)以上均正确第二章练习题（文法与语言）一、选择题1．文法 G 产生的 (1) 的全体是该文法描述的语言。
A.句型B. 终结符集C. 非终结符集D. 句子2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法；1 型文法又称为(C)文法；2 型语言可由(G) 识别。
A 短语结构文法B 上下文无关文法C 上下文有关文法D 正规文法E 图灵机F 有限自动机G 下推自动机4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。
编译原理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)是指古代官衙中掌管档案、负责起草文书的幕友,亦指官署中的公文、书信等;在现代，文案的称呼主要用在商业领域，其意义与中国古代所说的文案是有区别的。
在中国古代，文案亦作" 文按"。
公文案卷。
《北堂书钞》卷六八引《汉杂事》:"先是公府掾多不视事，但以文案为务。
"《晋书·桓温传》:"机务不可停废，常行文按宜为限日。
编译原理作业第八章符号表与错误处理
8.1 完成下列选择题：
(1) 编译程序使用b区别标识符的作用域。
a. 说明标识符的过程或函数名
b. 说明标识符的过程或函数的静态层次
c. 说明标识符的过程或函数的动态层次
d. 标识符的行号
(2) 在目标代码生成阶段，符号表用于 d 。
a. 目标代码生成
b. 语义检查
c. 语法检查
d. 地址分配
(3) 错误的局部化是指c。
a. 把错误理解成局部的错误
b. 对错误在局部范围内进行纠正
c. 当发现错误时，跳过错误所在的语法单位继续分析下去
d. 当发现错误时立即停止编译，待用户改正错误后再继续编译
【解答】(1) b (2) d (3) c
8.2 在编译过程中为什么要建立符号表？
答：在编译过程中始终要涉及到对一些语法符号的处理，这就需要用到语法符号的相关属性。
为了在需要时能找到这些语法成分及其相关属性，就必须使用一些表格来保存这些语法成分及其属性，这些表格就是符号表。
8.3 对出现在各个分程序中的标识符，扫描时是如何处理的？
答：对扫描到各分程序中的标识符的处理方法如下：
(1) 当在一个分程序首部某说明中扫描到一个标识符时，就以此标识符查找相应于本层分程序的符号表。
如果符号表中已有此名字的登记项，则表明此标识符已被重复说明(定义)，应按语法错误进行处理；否则，在符号表中新登记一项并将此标识符及有关信息(种属、类型、所分配的内存单元地址等)填入。
(2) 当在一分程序的语句中扫描到一个标识符时，首先在该层分程序的符号表中查找此标识符；若查不到，则继续在其外层分程序的符号表中查找。
如此下去，一旦在某一外层分程序的符号表中找到标识符，则从表中取出有关的信息并作相应的处理；如果查遍所有外层分程序的符号表都无法找到此标识符，则表明程序中使用了一个未经说明(定义)的标识符，此时可按语法错误予以处理。
8.4 对下列程序，当编译程序编译到箭头所指位置时，画出其层次表(分程序索引表)和符号表：
program stack(output);
var m, n:integer;
r:real;
procedure setup(ns:integer, check:real);
var k, l:integer;
function total(var at:integer, nt:integer):integer;
var i, sum:integer;
begin
for i:=1 to nt do sum:=sum+at[i]; total:=sum; end; begin
l:=27+total(a,ns); <----------------- end; begin n:=4; setup(n,5.75)
end.
答： 编译程序编译到箭头所指位置时，其层次表(分程序索引表)和符号表如图8-1所示。
图8-1 分程序索引表和符号表示意图
8.5 已知文法G[S]: S →while (e) S S →{L}
S →a /*a 代表赋值句*/ L →S;L L →S
构造该文法的LR 型的错误校正分析程序。
答：首先将文法G[S]拓广为G[S ′]：(0) S ′→S (1) S →while e do S (2) S →begin L end (3) S →a (4) L →S
1110987654321
符号表
表
(5) L →S ；L
则文法G[S ′]的LR(0)项目集示范族为 I0：S ′→·S I4：S →a· I10：L →S ；·L S →·while e do S I5：S →while e· do s L →·S S →·begin L end I6：S →begin L·end L →·S ；L S →·a I7：L →S·
S →·while e do S
I1：S ′→S· L →S· ；L S →·begin L end I2：S →while·e do s I8：S →while e do·S S →·a I3：S →begin·L end S →· while e do s I 11：S →while e do S· L →·S S →·begin L end I12：L →S ；L·
L →·S ；L S →·a S →·while e do s I9：S →begin L end· S →·begin L end
S →·a 将这些项目集的转换函数G O 表示为如图8-2所示的DFA 。
图8-2 习题8.5中文法G[S ′]的DFA
在LR(0)项目集规范族中，只有I7含有“移进”/“归约”冲突，且该冲突可用SLR(1)方法解决。
为此计算文法G[S ′]中每个非终结符的FOLLOW 集如下： FOLLOW(S ′)={#}
FOLLOW(S)={end,;,#} FOLLOW(L)={end}
由此构造出包括错误校正处理子程序的SLR(1)分析表如表8-1所示。
a
表8-1 习题8.5的SLR(1)分析表
由表中可以看出，在状态7面对输入符号为“；”时移进，而面对输入符号为“end”时为归约。
表中ei(i=1～7)代表不同的错误处理子程序，其含义和功能分别如下：
(1) 输出符号错处理程序e0：删除当前输入符号，显示出错信息“输入符号错”。
(2) 输入不匹配错误处理程序e1：去除栈顶状态和栈顶符号，显示出错信息“输入不匹配”。
(3) 缺语句错误处理程序e2：将假想符号a与状态4压栈，显示出错信息“缺少语句”。
(4) while语句缺少布尔量处理程序e3：将假想符号e与状态5压栈，显示出错信息“缺布尔量”。
(5) 缺少分号错误处理程序e4：将分号“；”插入未扫描的输入串首，显示出错信息“缺少分号”。
(6) while语句缺少do处理程序e5：将符号“do”与状态8压栈，显示出错信息“缺少do”。
(7) begin与end不配对，缺少end处理程序e6：将符号“end”与状态9压栈，显示出错信息“缺少end”。
(8) 缺少语句错误处理e7：将假想符号a插入未扫描的输入串首，显示出错信息“缺少语句”。
