1)把用汇编语言或高级语言写成的程序转换成机器语言的程序，被称为翻译程序。
汇编语言的翻译程序称为汇编程序
把高级语言的翻译程序称为编译程序。
可以采用边翻译边执行的解释执行方式，这种处理程序称为解释程序。解释程序的结果是源程序的执行结果。
2)编译有哪些部分组成？
每个部分的作用？
词法分析：输入源程序，对构成源程序的字符串进行扫描和分析，识别出一个个的单词（符号）如关键字，标识符，常数，算符，界符。
语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号分解成各类语法单位（如短语、句子等），并构造一棵能够正确反映该结构的语法树。
作用：通过语法分析确定整个输入是否构成语法上正确的“程序”。
注意：词法分析是种线性分析，而语法分析是一种层次分析。
中间代码生成：任务：语义分析的基础上按语言的语义规则进行初步的翻译（产生中间代码）中间代码：是一种含义明确、便于处理的记号系统，它通常独立具体的硬件；
表示形式：四元式、三元式、间接三元式等
中间代码优化：任务：对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。
目标代码生成：任务：把中间代码变换成特定机器上的低级语言代码（目标代码）
目标代码形式：绝对指令代码、可重定位指令代码、汇编指令代码
表格管理：
错误处理：
3)编译前后端的划分？
前端：此法分析、语法分析、中间代码生成、中间代码优化。
后端：目标代码生成及和硬件有关的工作。
4)符号和符号串的概念
1、字母表:它是非空有穷集。
例如：∑={a,b,c}或∑={1,2,3}
2、符号：字母表中的元素称为符号。
3、符号串：符号的有穷序列，符号串也称为字。用ε来表示空符号串。
例如：a,ab,abc,dsfsd
4、长度：符号串的长度是指该串所包含的符号个数。用|x|表示符号串x的长度。
例如：|a|=1，|abn|=3
5、连结：设x和y为符号串，则称xy 为他们的连结。
例如：x=aa,y=bb,则XY=aabb
6、空集：不含任何元素的集合,记为Φ。
7、乘积：设A和B是符号串集，则用AB表示A和B的乘积。
例如：X={a,b},Y={c,d},则XY={ac,ad,bc,bd}
8、方幂：设A为符号串集，则定义
A0={ε}
A1=A
A n=A n-1 A
例如：A={a,b} 则有：
A0={ε} A1={a,b}
A2={aa,ab,ba,bb}
9、正闭包：设A为符号串集，则用A+表示A的正闭包，其具体定义如下：
A+=A1∪A2∪A3∪?…
例如：A={a},A+={a,aa,aaa,……}
10、星闭包：设A为一集合，则定义A的星闭包为A*，其具体定义如下A*=A0∪A+例如：A={a},A*={ε,a,aa,aaa,……}
5)巴克斯范式（EBNF），能够写出巴克斯范式
带<>的叫非终止符,不带<>的叫终止符。例如：<逻辑值>→True|False
6)文法定义：文法是一个四元组G(V N，V T，P，Z)。非终极符集记为V N(大写字母)、
终极符集记为V T(小写字母)、产生式集记为P、初始符记为Z。
7)名词：
1、直接推导：设x和y是符号串，若用一次产生式可从x导出y，则称y为x的直接推导，并记为x?y。例子：x=Ab,y=ab,A→a,Ab?ab
2、推导：若用若干次产生式可从x串导出y
为x
的推导，并记为x y。
例子：x=AB,A→a,B→b AB?aB?ab 即：。
8) 语法树
定义：设G=(V N,V T,P,S)是给定文法,则称满足下面条件
的树为G的一棵语法树。
?每个结点都标有G的一个文法符号,且根结点标
有初始符S,非叶结点标有非终极符。
?如果一个非叶结点A有n个儿子结点(从左到
右)B1,B2,…,B n,则A→B1B2…,B n一定是G的一个产生
式。
如果每步都是最右非终极字符，则也称该规范推导为
最右推导。
例子：G[S]：S→AB
A→Aa|bB
B→a|Sb
S?AB?bBB?baB(最左推导)
S?AB?ASb?AABb?AAab?AbBab (最右推导)
S?AB?ASb?bBSb?baSb(非左非右)
定义：如果一个文法G 存在某个句子,使得它有两棵语法树,则称G 为二义性文法。 例子：证明 G:E →E+E|E*E|(E)|i 则G 是二义性文法。
因为句子i+i*i 具有两棵语法树分别如图所示。
1、设有文法G[N]:
N →D |ND
D →0|1|2|…|9
(1)试写出021和4321的最右推导和
最左推导。
(2)试举出三个无最右推导的句型。 解:(1)021的最左推导：
N ?ND ?NDD ?DDD ?0DD ?02D ? 021
021的最右推导： N ?ND ?N1?ND1?N21 ?D21?021 解:4321的最左推导：
N ?ND ?NDD ?NDDD ?DDDD ?4DDD ?43DD ?432D ?4321 4321的最右推导：
N ?ND ?N1?ND1?N21
?ND21?N321?D321?4321 (2)无最右推导的句型 N ?ND ?N1?ND1?DD1?4D1
定理 1、每个句型都有一棵语法树，每个语法树的叶组成一句型。 2、每棵子树的叶组成短语，每棵简单子树的叶组成简单短语，最左简单子树的叶组成句柄。 3、用语法树可证明每个句子都有一规范推导。 3、设有文法G[E]: E →T |E+T |E-T
T →F |T*F |T /F
F →i|(E)
解：(1) i*i /(i+i*i)的语法树
(3)最右推导:E ?T ?T*F ?T*(E)?T*(E+T) ?T*(E+F)?T*(E+i)?T*(T+i)? T*F*(T+i)
2、证明下列文法G[S] 是二义性文法： S →if E then S else S | if E then S 解：设有if E 1 then if E 2 then S 1 else S 2 ,则有两棵语法树:
短语：第一个F,F+i,i, 第二个F,i, F*i(F+i),(F*i), T*(F*i),(F+i)-T*(F*i) 简单短语：第一个F,i, 第二个Fi
句柄：第一个F
4、设有文法：求bBABb和baabaab的全部短语、简单短语、句柄
S→AB
A→Aa
A→bB
B→a
B→Sb
例子：
定理
使得L(G2 (去除ε)
解：B
∴则有β短语：第一个a,ba,baa,
第二个ba,baa,baab,
第三a,第四个a,baabaab 简单短语：第一个a，第三个a，
第四个a
句柄：第一个a
第四章
1) 定义 正则表达式
设Σ为给定字母表,RE 表示Σ上正则表达式之集,则定义： 1.Λ,ε∈RE
2.若a ∈Σ,则a ∈RE
3.若e 1,e 2∈RE,则(e 1|e 2)∈RE,(e 1?e 2)∈RE,(e 1)*∈RE
2) 定义 设e ∈RE,则定义函数L(e)
L(Λ)= Φ L(ε)= {ε} L(a)={a} L(e *)= L(e)*
L(e 1|e 2)= L(e 1)∪L(e 2) L(e 1? e 2)= L(e 1)L(e 2)
3) 确定自动机：
例子：Σ={a,b}
L(a *)=｛ε,a,aa …｝ L(ba *)=｛b,ba,baa …｝ L(a|ba *)=｛a,b,ba …｝
L(aa|bb|ab|ba)={aa,bb,ab,ba} 1、写出非负整数的正则表达式。 例子：1234或0或1023 0123或－123 非法 <非负整数>→<数字>|<非0数字><整数> <整数>→<数字>|<整数><数字> <数字>→0|1|2|…|9 <非0数字>→1|2|…|9
2、写出以非5数字为开头的所有非负整数之集的正则表达式。例子：1234或0或1023
0123或5123 非法
解：D=1|2|…|9
E=1|2|3|4|6|7|8|9
L=0|E(0|D)*
总结：
① 对于简单的ε自动机，利用构造算法 消除ε边，然后进行确定化。② 对于复杂 的ε自动机，利用ε闭包的算法进行处理。
1、构造下列正则式相应的DA: (1)1(0|1)*101
(2)1(1010*|1(010)*1)*0 (3)a((a|b)*|ab *a)b (4)b((ab)*|bb)*ab
2、已知NDA=({x,y,z},{0,1},M,{x},{z}), 其中:M(x,0)={z},M(y,0)={x,y},
M(z,0)={x,z}, M(x,1)={x},
M(y,1)=Φ,M(z,1)={y},
构造相应的DA。
例子：
求first(X)其中X→aBc
first(X)=｛a｝
求follow(B)其中X→aBc
follow(B)=｛c｝
求select(A→aBc)其中X→aBc select(A→aBc)= first(X)=｛a｝
1、设有文法G：
S→AaB|a
A→AB|ε
B→bB| ε
试消除空产生式。
解:β={A,B} 消除ε产生式得：(1) S→AaB|a (2) A→AB (3) B→bB
再扩充下列产生式：
(4) S→aB (5) S→Aa (6) A→B (7) B→b
例子: 考虑文法,分别求first,follow，select集G[E]:E→TE'
E'→+TE'|ε
T→FT'
T'→*FT'|ε
F→i|(E)
first(E)=first(T)=first(F)={i,( }
first(E‘)=｛+,ε｝
first(T')=｛*,ε｝
follow(E)={)，#}
follow(E')= follow(E)=｛),#｝
follow(T)=first(E')~ε∪follow(E)
=｛+, ε}~ε∪{ ),#｝
={+,),#}
follow(T')=follow(T)=｛+,),#｝
follow(F)= first(T')~ε∪follow(T)
=｛*,ε}~ε∪{ +,),#｝
={*,+,),#}
select(E→TE')=first(T)=｛i,(｝
select(E'→+TE')=｛+｝
select(E‘→ε)=follow(E’)=｛),#｝
select(T→FT')=first(F)=｛),#｝
select(T'→*FT')=｛*｝
select(T'→ε)=follow(T')
=｛+,),#｝
select(F→i)=｛i｝
select(F→(E))=｛(｝
3、试判断下列文法是否为LL(1)文法：
G1：A→aBC,B→a,C→a
G2: A→aABe,B→Bb,B→b
G3: A→aABe,A→Ba,B→dB,B→
解:(1) 对A,B,C都只有一个产生式
所以,G1为LL(1)文法。1、
定义LL(1)文法：如果对任一非终极符B都有select(B,βi)∩select (B,βj)=Ф,(i≠j)。
2、非LL(1)文法的等价变换
一、提取左公因式
将产生式A→αβ|αγ等价转换为
A→αA’
A’→β|γ
这样产生式右部的frist集相交不为空。
例子：X→aB X→ab
B→bc B→ba
提取公因式有：
X→a(B|b)
B→b(c|a)
改写：
X→aX’X’→(B|b)
B→bB’B’→(c|a)
例子：X→aB X→Bb
B→ac B→ba
改写：
X→aB X→acb X→bab
B→ac B→ba
提取公因式有：
X→a(B|cb)
B→…
二、消除左递归
A→Aβ|γ? A→γA’
A’→βA’|ε
一般而言：
A→Aβ1|Aβ2|...|Aβn|γ1|γ2|…|γm
则有: A→γ1A’|γ2A’|…|γm A’
A’→β1A’|β2A’|…|βn A’|ε
LL矩阵的构造算法：处理P，N,R操作：
①当遇到小写字母时进行N操作，删除小写字母。
②当遇到大写字母时进行P操作，保留源大写字母。
③将符号串进行逆序转换。
4、设有文法G：
Z→bMb
M→a|(L
L→Ma）
(1) 试写出文法G的LL矩阵。
(2)试写出b(aa)b的LL分析过程。解：select(Z→bMb)={b}
select(M→a|(L)={a,(}
select(L→Ma))=first(M)={a,(}
例子：G(E): E→E+E
E→E*E
E→(E)|i
1.构造LL矩阵
2.符号串i+i*i#的LL分析过程
解：首先此文法有二义性应该去除。
G(E): E→E+T|T
T→T*E|F
F→(E)|I
其次此文法有左递归应该去除。
G(E): E→TE’
E’→+TE’|ε
T→FT’
T’→*FT’|ε
F→(E)|i
各产生式的SELECT集合为：
select(E→TE')=first(T)=｛i,(｝
select(E'→+TE')=｛+｝
select(E'→ε)=follow(E')=｛),#｝
select(T→FT')=first(F)=｛),#｝
select(T'→*FT')=｛*｝
select(T'→ε)=follow(T')=｛+,),#｝
select(F→i)=｛i｝
select(F→(E))=｛(｝
5、对下面的文法G: E →TE ’ E ’→+E|ε T →FT ’ T ’→T|ε F →PF ’ F ’→*F ’|ε P →(E)|A|B|∧ A →a B →b
(1) 计算这个文法的每个非终极符
的First 集和follow 集。 (2)证明这个文法是LL(1)的 (3)构造他的转换矩阵。 解：first(E)=first(T)=first(F)
=first(P)={(,a,b,∧} first(E ’)={+,ε}
first(T ’)=first(T)∪{ε} ={(,a,b,∧,ε} first(F ’)= {*,ε}
follow(E)=follow(E ’)∪{ }}∪{#}={),#} follow(E ’)= follow(E)= {),#} follow(T)
= first(E ’)-ε∪follow(E)∪follow(T ’) ={+,),#}
follow(T ’)=follow(T)={+, ), #}
follow(F)=first(T ’)- ε∪follow(T) ={(,a,b,∧,+,),#} follow(F ’)=follow(F)
={(,a,b,∧,+,),#} follow(P)=first(F ’) -ε∪follow(F) ={*,(,a,b,∧
,+, ),#}
select(E →TE ’)=first(T)={(,a,b,∧} select(E ’→+E)={+}
select(E ’→ε)=follow(E ’)={),#} select(T →FT ’)=first(F)={(,a,b,∧} select(T ’→T)=first(T)={(,a,b,∧} select(T ’→ε)=follow(T ’)={+,),#} select(F →PF ’)=first(P)={(,a,b,∧} select(F ’→F ’)={*}
select(F ’→ε)=follow(F ’) ={(,a,b,∧,+,),#} select(P →(E))={(} select(P →a)={a} select(P →b)={b} select(P →∧)={∧}
相同字符选择集的交集为φ.所以为LL(1)文法。
第六章
1、简单优先算法
定义： 满足下面两个条件的文法称为
简单优先文法。
1.任意两个符号至多成立一种关系
2.任意两个产生式具有不同右部
下面文法均不为简单优先文法
1、写出下列文法的的优先关系矩阵。 Z →aAAa A →bF ’b F ’→F F →cF|c
2、算符优先
第七章（LR0、SLR1） LR0：
二义性结点：可归前缀图的一个结点包含多个归约项目或同时包含移进项目和归约项目。 LR(0)文法：文法的可归前缀图不包含二义性结点(可用于判是否LR(0)文法)。
2、设有文法G[S]： S →V V →T|ViT T →F|T+F F →)V*|(
是否为优先文法，若是给出(+(i(的分析过程。
1、试问下一文法是不是LR(0)文法
S→aA
A→Ab|b
拓展文法：S→aA
A→Ab
A→b
改写文法：S→aA
A→bA‘
A’→bA‘|ε
A→b
去ε边：S→aA
S→ab
A→bA‘
A’→b
A→b (P49)
作出前缀图进行判断。
第2步：可归前缀图
31步LR(0)矩阵s表示状态
r表示归约
第4步分析栈
SLR(1)方法:是只在LR(0)可归前缀图的二义性状态下向前看一符。当有I={x→α●bβ A→r●B→δ●}
FOLLOW(A)∩FOLLOW(B)=φ,
FOLLOW(A)∩b=φ；
FOLLOW(B)∩b=φ
则称该冲突可以解决。
满足上述条件则可利用SLR(1)方法。
例子：S→Aa.bBc
A→d
B→e
FOLLOW(A)=a，FOLLOW(B)＝c
所以：FOLLOW(A)∩FOLLOW(B)=φ,
FOLLOW(A)∩b=φ；
FOLLOW(B)∩b=φ
所以本文法是SLR(1)文法。
3、已知文法A→aAd|aAb|ε,判断该文法
是否为SLR(1)
并对输入串
ab#给出分析过程。
解：把A?ε项目为A?。为SLR(1)文法。
设：A’?A[0]
A?aAd[1]
A?aAb[2]
A?ε[3]
常见的中间代码形式有逆波兰式，三元式，四元式，树等。 一、逆波兰式
运算符跟在所有运算对象的后面的表示法写出的式子称为后缀法或逆波兰法。表示：ab+。
a*(b+c/d) abcd/+*的推导。
二、三元式的一般形式：i:(ω,OPR1,OPR2)
i 是三元式编号，不同三元式不能有相同编号。 ω是运算符部分。OPR1和OPR2是运算对象部分 例子： a:=b*c+b*d 的相应三元组
三、树 二目运算对应二叉树，多目运算对应多叉树。三元式可以用二叉树表示。 例子： (a+b*(c-d))-e/f 的树。
该树的根后序为：abcd-*+ef/-,为该式的逆波兰式。
五、程序语句的四元式表示 下面是语句四元式的形式定义:
二、过程语句的四元式结构
(1) 简述规范归约的基本思想。（第五章课件第5张） 用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。 (2) 阐述编译程序各个组成部分主要完成的工作。（课本P2~P4） 词法分析的任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。 语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。 语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。 优化：在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。 目标代码生成：把中间代码变换成特定机器上的低级语言代码。 (3) 什么是编译器的前端和后端，这样划分有何意义？（课本P7） 编译器粗略分为 词法分析，语法分析，类型检查，中间代码生成， 代码优化，目标代码生成，目标代码优化。 把中间代码生成及之前阶段划分问编译器的前端，那么后端与前端是独立的。后端只需要一种中间代码表示，可以是三地址代码或四元式等，而这些都与前端生成的方式无关。也就是不论你前端是用fortran 还是c/c++,只要生成了中间代码表示就可以了，后端是不管你是用哪种语言生成的。 (4) 乔姆斯基把文法分为哪几种类型？对这几种类型文法作简要说明。（课本P34） 把文法分成四种类型：0，1，2，3型。与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。 0型(短语文法，图灵机)：产生式形如：α→β其中：∈α (VT ? VN)*且至少含有一个非终结符；∈β (VT ? VN)* 1型(上下文有关文法，线性界限自动机)：产生式形如：α→β其中：|α| ≤ |β|。仅Sε→例外，但此时S不得出现在任何产生式的右部。 2型(上下文无关文法，非确定下推自动机)：产生式形如： A →β其中：A∈ VN；∈β (VT ? VN)*。 3型(正规文法，有限自动机)：产生式形如：A → aB 或A → a其中：a∈ VT ? {ε}；A，B∈VN产生式形如： A → Ba 或 A → a 其中：a∈ VT ? {ε}；A，B∈VN。 (5) 简述编译过程中遍的概念以及遍数的多少对编译器设计的影响。（参考课本P7） 遍的概念：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 遍可以和阶段相应，也可无关——遍中通常含有若干个阶段。实际上，根据语言的不同，编译器可以是一遍（onepass）——所有的阶段由一遍完成，其结果是编译得很好，但（通常）代码却不太有效。Pascal 语言和C语言均允许单遍编译。（Modula-2语言的结构则要求编译器至少有两遍）。大多数带有优化的编译器都需要超过一遍：典型的安排是将一遍用于扫描和分析，将另一遍用于语义分析和源代码层优化，第3遍用于代码生成和目标层的优化。更深层的优化则可能需要更多的遍： 5遍、6遍、甚至8遍都是可能的。 备注：由于最后一道没有找到比较好的答案，欢迎大家补充。 1) 什么是句子？什么是语言?
<编译原理>历年试题及答案 一．（每项选择 2 分，共 20 分）选择题 1．将编译程序分成若干个“遍”是为了_b__。 a.提高程序的执行效率 b.使程序的结构更加清 晰 c.利用有限的机器内存并提高机器的执行效 率 d.利用有限的机器内存但降低了机器的执行 效率 2．构造编译程序应掌握__d__。 a.源程序 b.目标语言 c.编译 方法 d.以上三项都是 3．变 量应当 c＿。 a.持有左值 b.持有右值 c.既持有左值又持有右值 d. 既不持有左值也不持有右值 4．编译程序绝大多数时间 花在_d___上。 a.出错处理 b.词法分析 c.目标代 码生成 d.管理表格 5．词法分析器 的输出结果是_c___。 a.单词的种别编码 b.单词在符号表中的位置 c. 单词的种别编码和自身值 d.单词自身值 6．正规式 MI 和 M2 等价是指__c__。 a. MI 和 M2 的状态数相等 b.Ml 和 M2 的有向弧条数相等。 C.M1 和 M2 所识别的语言集相等d. Ml 和 M2 状态数和有向弧条数相等 7．中间代码生成时所依据的是—c。 a．语法规则 b．词法规则c．语义规则 d．等价变换规则8．后缀式 ab+cd+/可用表达式__b_来表示。 a． a+b/c+d b． (a+b)/(c+d) c． a+b/(c+d) d． a+b+c/d 9．程序所需的数据空间在程序运行前就可确定，称为____c_＿管理技术。 a.动态存储 b.栈式存储 c.静态存储 d.堆式存储 10. 堆式动态分配申请和释放存储空间遵守___d____＿原则。 a.先请先放 b.先请后放 c.后请先放 d.任意 二（每小题 10 分，共 80 分）简答题 1.画出编译程序 的总体结构图，简述各部分的主要功能。 2. 已知文法 G[E]: E→ET+|T T→TF* | F F→F^ | a 试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄. 3．为正规式(a|b) *a(a|b)构造一个确定的有限自动机。 4．设文法 G(S)：
一、简答题 1.什么是编译程序 答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义 答：一个文法G抽象地表示为四元组 G=（Vn,Vt,P,S） –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么 答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术 答：优化技术1—删除公共子表达式 优化技术2—复写传播 优化技术3—删除无用代码 优化技术4—对程序进行代数恒等变换（降低运算强度） 优化技术5—代码外提 优化技术6—强度削弱 优化技术7—删除归纳变量 优化技术简介——对程序进行代数恒等变换（代数简化） 优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段 答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 6. 什么是文法 答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么 答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)； 并对静态语义进行审查。 8.代码优化须遵循哪些原则 答：等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么 答：
天津理工大学考试试卷 ～2010学年度第二学期 《编译原理》期末考试试卷 课程代码： 0660116 试卷编号： 1-A 命题日期： 2010 年 6 月 15 日 答题时限： 120 分钟考试形式：闭卷笔试 大题号 一二三四 总分 一、单项选择题（请从4个备选答案中选择最适合的一项，每小题2分， 得 分 1 2 3 4 5 6 7 8 9 10 D C B D D B C B D C 1. 编译程序是对（） A. 汇编程序的翻译 B. 高级语言程序的解释执行 C. 机器语言的执行 D. 高级语言的翻译 2. 词法分析器的输出结果是（） A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 3. 在规范规约中，用（）来刻画可规约串。 A．直接短语 B．句柄 C．最左素短语 D．素短语 4. 与正规式(a* | b) * (c | d)等价的正规式是（） A．a* (c | d) | b(c | d) B．a* (c | d) * | b(c | d) * C．a* (c | d)| b* (c | d) D．(a | b) * c| (a | b) * d 含有Aα·，则在状态K时，仅当面临输入符号a∈FOLLOW(A)时，才采 5. 若项目集I K 取Aα·动作的一定是（） A．LALR文法 B．LR(0) 文法C．LR(1)文法 D．SLR(1)文法 6. 四元式之间的联系是通过（）实现的。
A. 指示器 B. 临时变量 C. 符号表 D. 程序变量 7．文法G ：S x Sx | y 所识别的语言是（ ） A ．xyx B ．(xyx) * C ．x n yx n (n ≥0) D ．x * yx * 8. 有一语法制导翻译如下所示： S b Ab {print “1”} A (B {print “2”} A a {print “3”} B Aa) {print “4”} 若输入序列为b(((aa)a)a)b ，且采用自下而上的分析方法，则输出序列为（ ） A ．32224441 B. 34242421 C ．12424243 D. 34442212 9．关于必经结点的二元关系，下列叙述不正确的是（ ） A ．满足自反性 B ．满足传递性 C ．满足反对称型 D ．满足对称性 10．错误的局部化是指（ ）。 A ．把错误理解成局部的错误 B ．对错误在局部范围内进行纠正 C ．当发现错误时，跳过错误所在的语法单位继续分析下去 D ．当发现错误时立即停止编译，待用户改正错误后再继续编译 二、判断题（每小题1分，共5分） 得 分 1. 文法G 的一个句子对应于多个推导，则G 是二义性的。（× ） 2. 动态的存储分配是指在运行阶段为源程序中的数据对象分配存储单元。（√ ） 3. 算符优先文法采用“移进－规约”技术，其规约过程是规范的。（ × ） 4. 删除归纳变量是在强度削弱以后进行。（ √ ） 5. 在目标代码生成阶段，符号表用于目标代码生成。（ × ） 5分，共15分） 得 分 1. 构造正规式(0∣1)* 00相应的正规式并化简。（共5分） （1）根据正规式，画出相应的NFA M （2分） I I 0 I 1 {x,1,2} {1,2,3} {1,2} {1,2,3} {1,2,3,4} {1,2} {1,2} {1,2,3} {1,2 } {1,2,3, {1,2,3,4} {1,2 } X 12 3 4 01
编译原理复习题 一、填空题 1.编译程序的工作过程一般可以划分为词法分析，语法分析，语义分析，中间代码优化，代码优化等几个基本阶段。 2.若源程序是用高级语言编写的，目标程序是汇编程序或机器语言程序，则其翻译程序称为编译程序. 3.编译方式与解释方式的根本区别在于是否生成目标代码. 5.对编译程序而言，输入数据是源程序，输出结果是目标程序. 7.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 8.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格管理和出错处理。其中，词法分析器用于识别单词。 10.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 12.产生式是用于定义语法成分的一种书写规则。 13.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)={x|Sx，x∈VT*}。 14.设G是一个给定的文法，S是文法的开始符号，如果S * ?x（其中x∈V*），则称x是 文法的一个句型。 15.设G是一个给定的文法，S是文法的开始符号，如果S * ?x(其中x∈V T*)，则称x是文 法的一个句子。 16.扫描器的任务是从源程序中识别出一个个单词符号。 17.语法分析最常用的两类方法是自顶向下和自底向上分析法。 18.语法分析的任务是识别给定的终结符串是否为给定文法的句子。 19.递归下降法不允许任一非终结符是直接左递归的。 20.自顶向下的语法分析方法的关键是如何选择候选式的问题。 21.递归下降分析法是自顶向下分析方法。 22.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 23.自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 24.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地 向上进行直接归约，力求归约到文法的开始符号。 26.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最左归约， 0 的含义是向右查看输入串符号的个数为0。 31.终结符只有，它们由词法分析器提供。 32.在使用高级语言编程时，首先可通过编译程序发现源程序的全部语法错误和语义部分错误. 34．一个句型中的最左简单短语称为该句型的句柄。 36．从功能上说，程序语言的语句大体可分为执行性语句和说明性语句两大类。
编译原理课程设计心得体会范文（单片机）经过一个星期的编译原理课程设计，本人在刘贞老师的指导下，顺利完成该课程设计。通过该课程设计，收获颇多。 一、对实验原理有更深的理解 通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、构造工具及其相关的技术对课本上的知识有了更深的理解，课本上的知识师机械的，表面的。通过把该算法的内容，算法的执行顺序在计算机上实现，把原来以为很深奥的书本知识变的更为简单，对实验原理有更深的理解。 二、对该理论在实践中的应用有深刻的理解 通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。 三、激发了学习的积极性 通过该课程设计，全面系统的理解了编译原理程序构造的一般原理和基本实现方法。把死板的课本知识变得生动有趣，激发了学习的积极性。把学过的计算机编译原理的知识强化，能够把课堂上学的知识通过自己设计的程序表示出来，加深了对理论知识的理解。以前对与计算机操 作系统的认识是模糊的，概念上的，现在通过自己动手做实验，
从实践上认识了操作系统是如何处理命令的，如何协调计算机内部各个部件运行，对计算机编译原理的认识更加深刻。课程设计中程序比较复杂，在调试时应该仔细，在程序调试时，注意指针，将不必要的命令去除。 在这次课程设计中，我就是按照实验指导的思想来完成。加深了理解文件系统的内部功能及内部实现，培养实践动手能力和程序开发能力的目的。 四、理解了该知识点以及学科之间的融合渗透 本次课程设计程序部分是用c语言编写的，把《计算机操作系统》，《编译原理》，《算法分析与设计》《c语言》四门学科联系起来，把 各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体的认识更加深刻。使我加深了对《计算机操作系统》，《编译原理》，《算法分析与设计》《c语言》四门课程的认识。 嵌入式课程设计心得体会 本学期为期一周的嵌入式课程设计在不知不觉中结束了，虽说这次课程设计时间不是很长，但是感觉自己收获颇丰，不仅学习到了一些新知识，回顾了以前的一些快要遗忘的知识点，而且使自己的学习目标更加明确，学习方法更加完善，也体会到软件开发的趣味，更加清楚地认识到了自己在软件开发及学习上的一些不足之处。下面就来详细写一下我关于此次课程设计的心得体会： 此次课程设计的实训的是由上海杰普公司的楚老师带我们完成的。楚老师看上去比较年轻，给我们很有亲和力，技术上也很强，而
1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 答案： S→ AB|B A→ a|aA B→ bBc|bc 2．给出下面语言的相应文法 L1={a n b n c m d m| m,n≥1，n为奇数，m为偶数}。 答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 3、构造一个DFA，它接受={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化） (一)相应的正规式为(a|b)*ab(a|b)* (二)①与此正规式对应的NFA为 答案；在自己写的纸上 4、对下面的文法G: E→TE’ E’→+E|ε T→FT’ T’→T|ε F→PF’ F’→*F’|ε P→(E)|a|b|∧（1）证明这个文法是LL(1)的。 考虑下列产生式: E’->E|ε T’->T|ε F’->*F’ |ε P->(E) |∧a|b FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ
FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. 计算这个文法的每个非终结符的FIRST和FOLLOW。（8分） 答案：FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#} FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} （3）构造它的预测分析表。（6分） 答案；在手机上 写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。 答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2)
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x 3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4．语法分析时必须先消除文法中的左递归。X
编译原理复习题及答案 一、选择题 1．一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3．下面说法正确的是(A) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A) A 必要条件 B 充分必要条件 5．下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．(A)是一种典型的解释型语言。
A．BASIC B．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序 B．目标程序C．连接程序D．解释程序 14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理 17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba
《编译原理》总复习-07级 第一章编译程序的概述 （一）内容 本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。 （二）本章重点 编译（程序），解释（程序），编译程序的逻辑结构。 （三）本章难点 编译程序的生成。 （四）本章考点 全部基本概念。 编译程序的逻辑结构。 （五）学习指导 引论部分主要是解释什么是编译程序以及编译的总体过程。因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。 第三章文法和语言课外训练 （一）内容 本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。 （二）本章重点 上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。（三）本章难点 上下文无关文法，语法分析树，文法的分类。 （四）本章考点 上下文无关文法的定义。 符号串的推导。 语法分析树的构造。 （五）学习指导 要构造编译程序，就要把源语言用某种方式进行定义和描述。学习高级语言的语法描述是学习编译原理的基础。上下文无关文法及语法树是本章学习的重点。语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。 附训练试题：
编译原理学习心得 编译原理学习心得1 编译程序在计算机科学与技术的发展历史中发挥了巨大作用，是计算机系统的核心支撑软件。而“编译原理”这门课程一直以来是国内外大学计算机相关专业的重要课程。因为它的知识结构贯穿程序设计语言、系统环境以及体系结构，能以相对的视角体现从软件到硬件以及软硬件协同的整机概念。其理论基础又涉及形式语言与自动机、数据结构与算法等计算机学科的许多重要方面，为联系计算机科学理论和计算机系统的典范。 虽然编译原理这门课程在大多数的人里认为枯燥无味，学起来就像看天书一样。然而学习这门课程还是有一定的好处的。比如可以更加容易的理解在一个语言种哪些写法是等价的，哪些是有差异的，可以更加客观的比较不同语言的差异，并且学习新的语言的效率也会更加高，语言转换也会更加游刃有余。 不学“编译原理”这门课程的话，自己的编程思想会很浅显。而且编程也只仅仅停留在编程上，无法深入理解其中的原理。 学习编译原理的话，从文法、正规式、NFA与DFA的定义，下手，要用心动脑去体会 编译原理学习心得2
从联系最紧密的操作系统来说吧，你写多线程/多进程的程序就得和操作系统的知识打交道。写多线程得加锁吧，临界区、死锁的四个条件之类的标准的操作系统的内容吧(不得不吐槽一下，某国内一线电商干了三年的程序猿，写多线程居然不知道加锁，也是醉了)。进程间通信的几种方式什么管道、socket、共享内存等，这也是操作系统的内容吧。文件系统，这也是经常要打交道的东西。还有内存什么的，你做Android 开发，这些里边有很多东西都在系统层面被封装好了，但是你要是不知道原理，一旦出了错根本无从调试，况且你该不会打算写一辈子写Android 就是填逻辑吧。 然后，是编译原理，普通的程序猿是接触不到编译器或者虚拟机的开发的。但是这并不意味着编译原理就用不到。说个最常见的读取配置文件，只要你的配置文件有自定义的语法，你就要用编译原理的东西。还有类似于自动生成代码啦、正则表达式啦这些都算是编译原理的内容。你既然是写Java 的不了解虚拟机怎么可以，最基本的字节码总是需要能看懂的吧，分析一些疑难杂症的时候字节码还是很有用的。 最后，是计算机原理，如果只是做应用开发的话计算机原理其实不必要掌握的多深入，但是一些基本的概念还是要清楚的。比如寄存器、缓存、中断什么的，关键的时候可以帮助你调试。在一些对性能要求非常高的场合，也是很有作用的。此外，学了
第八节习题一、单项选择题 1、将编译程序分成若干个“遍”是为了 b 。 a．提高程序的执行效率 b．使程序的结构更加清晰 c．利用有限的机器内存并提高机器的执行效率 d．利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握 d 。 a．源程序b．目标语言 c．编译方法d．以上三项都是 3、变量应当 c 。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在 b 上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、 d 不可能是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用 a 可以定义一个程序的意义。 a．语义规则b．词法规则 c．产生规则d．词法规则 7、词法分析器的输入是 a 。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- d 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对 d 。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循 b 。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 解答 1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。 2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。 3、对编译而言，变量既持有左值又持有右值，故选c。 4、编译程序打交道最多的就是各种表格，因此选d。 5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。 6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。 7、b 8、c 9、d 10、c 二、多项选择题
第3章文法和语言 第1题 文法G＝({A,B,S},{a,b,c},P,S)其中P为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 答案： L(G[S])={abc} 第 11题 令文法 G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明 E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=>E+T=>E+T*F，所 以E+T*F句型 此句型相对于E的短语有:E+T*F；相对于 T的短语 有 T*F 直接短语为：T*F 句柄为：T*F 第 13题 一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合 P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 A S a S B B B A S a
《编译原理》课后习题答案第三章 答案： (1)串abbaa最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b abbaa aaabbaa ? 可能元素有：ε aa ab (3)该句子的短语有： a是相对 A的短语 ε是相对 S的短语 b是相对 B的短语 εbb是相对 B的短语 aa是相对 S的短语 aεbbaa是相对 S的短语 直接短语有：a ε b 句柄是：a
编译原理课程设计心得体会 假期期间我参加了由高平市教育局组织的构建高效课堂的培训，课题是三环节问题导学课课堂教学模式，张艳红老师论述了课堂是教学的主要阵地之一，是教师传授知识、学生学习知识的场所，教师和学生交往互动的空间，是教师引导学生发展、探究知识的主渠道，也是实现高效教学的主战场。要提高英语教学质量，就必须重视英语课堂教学，实现有效课堂教学。教师如何优化课堂教学，激发学生学习英语的兴趣，培养学生良好的英语学习习惯，通过这次理论学习和培训,使我对课堂有效教学有了更深刻的认知： 经过一个星期的编译原理课程设计，本人在老师的指导下，顺利完成该课程设计。通过该课程设计，收获颇多。 一、对实验原理有更深的理解 通过该课程设计，掌握了什么是编译程序，编译程序工作的基本过程及其各阶段的基本任务，熟悉了编译程序总流程框图，了解了编译程序的生成过程、构造工具及其相关的技术对课本上的知识有了更深的理解，课本上的知识师机械的，表面的。通过把该算法的内容，算法的执行顺序在计算机上实现，把原来以为很深奥的书本知识变的更为简单，对实验原理有更深的理解。 二、对该理论在实践中的应用有深刻的理解 要养成注释程序的好习惯，一个程序的完美与否不仅仅是实现功能，而应该让人一看就能明白你的思路，这样也为资料的保存和交流提供了方便;在设计课程过程中遇到问题是很正常德，但我们应该将每次遇到的问题记录下来，并分析清楚，以免下次再碰到同样的问题的课程设计结束了，但是从中学到的知识会让我受益终身。 通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。 自1987年就和程永革一起共事的歌舞话剧团演唱队队长骆汉泉含泪说道：“永革是我的好兄弟，这么多年，我们一起排练、演出，他的敬业精神一直留在我的脑海中，他的艺术才华和人品都给我们留下了深刻的印象。作为艺术人才，他尽职尽责，用自己的生命演绎出人生的追求。虽然他已经离我们而去，但是他难能可贵的责任担当和执着敬业的奉献精神一直感染着我们，我们也将在今后的工作中，以他为榜样，演好戏、做好人。” 月27日，全县《科学》教研会在城内小学召开。与其它学科教研会不同的是，《科学》教研会不是对新课标进行培训，而是科学课高效课堂的培训。原因是新拟定的《科学课程标准》还没有正式颁布。这次会议，全县专兼职老师一共100多人，观摩了三节高效课堂教学，聆听了龚主任所作的“构建自主探究式的高效课堂”专题讲座。
说明 1.这份资料的最初来源是王金伟老师给大家发的复习提纲，我在下面会给大家附一份原版，后面的21面资料是在那个的基础上整理和细化得到的。最初做这份资料的目的是我本人作为班长为了帮助我们班的同学顺利通过考试而整理的。听王老师说有想法留给学弟学妹们用，我放假后又对一些内容进行了修正和改进，得到了大家看到的这个版本 2.这份资料加入了很多我个人的理解。与原提纲相比，我增删了一些内容，并对某些内容进行了调序与合并。 3.这份资料融入了老师平时上课的以及最后复习课给的，更重要的是我个人的理解和猜测。大家或许都有感受，觉得编译原理书上或者上说的句子根本看不懂。针对这个问题，我把很多晦涩难懂的形式化的算法通过我的理解后用比较形象易懂的话表述了 出来，表述得可能并不科学严谨，但我的目的是为了能帮助大家做题和考试 4.里面的每一个考点我都在最后用括号加了注释，方便不同起点不同准备时间的同学进行选择，这里简单说明 “了解”：代表这一部分的内容被老师列在提纲内，但其实并不太影响大家对大题的计算；并且据我的分析也并不太可能出小题所以时间很紧的同学可以略看就好，当然看看还是有好处的。
“小题”一类的字样代表这一块的知识点值得出填空选择，大家 1 / 47 有时间应该理解性的记忆下来（在2012年的期末考试上，选择 为1分*10题；填空为1分*10题，判断改错为2分*5题，小题总计30分） “简答”：老师在最后复习课上说过编译原理是有简答题的，简 答不同于计算，很可能是让你默写一些步骤。所以这一块内容大家需要背诵，即使不理解也要背下来（在2012年的期末考试上，简答题的分值为5分*4题=20分 “铺垫”“大题步骤”等代表这一块的内容对于综合大题的做题 是必须了解的，或者其实就是做大题的分解步骤，这些块的内容是所有人必须看懂并且记下来的 “实际大题”：总共列出的有4道，应该每年考察的都会是这4 中题型，每一道的分值都在12~15分左右，是所有人想通过考试所必须攻克的。这里通常我会标出他需要用到之前的哪些哪些知识点（2012年期末考试4道题的总分值为50分） 5.如果大家想去打印，最好在装有2007及以上的机器上打印，否则有些符号可能会显示不出来。建议大家去生活广场找机器打，不要去景元鸿 6.由于时间仓促，这份资料做的并不完善和严谨，难免有错漏之处，希望大家谅解。大家可以一边看我的这份资料，一边看老师
《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．计算机高级语言翻译成低级语言只有解释一种方式。() ×2．在编译中进行语法检查的目的是为了发现程序中所有错误。() √3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 () ×4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 () √5．每个文法都能改写为 LL(1) 文法。 () √6．递归下降法允许任一非终极符是直接左递归的。 () ×7．算符优先关系表不一定存在对应的优先函数。 () ×8．自底而上语法分析方法的主要问题是候选式的选择。 () ×9．LR 法是自顶向下语法分析方法。 () ×10．简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空1分，共10分) 1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。 表格管理出错处理_ 2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。 _目标程序_编译程序 3．编译方式与解释方式的根本区别在于__ __。 是否生成目标代码_ 4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。 _源程序目标程序
5．产生式是用于定义__ __的一种书写规则。 _语法成分 6．语法分析最常用的两类方法是___ __和__ __分析法。 自上而下_自下而上 四、简答题（20分） 1. 什么是句子？什么是语言 ? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。
选择： 1.编译程序绝大多数时间花在 D 上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 3.如果文法G是无二义的，则它的任何句子α A 。 a. 最左推导和最右推导对应的语法树必定相同 b. 最左推导和最右推导对应的语法树可能不同 c. 最左推导和最右推导必定相同 d. 可能存在两个不同的最左推导，但它们对应的语法树相同 4.在规范归约中，用 B 来刻画可归约串。 a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语 5.若a为终结符，则A→α·aβ为 B 项目 a.归约 b.移进 c.接受 d.待约 6.间接三元式表示法的优点为（A） A.采用间接码表，便于优化处理 B.节省存储空间，不便于表的修改 C.便于优化处理，节省存储空间 D.节省存储空间，不便于优化处理 7.下列C优化方法不是针对循优化进行的。 a．强度削弱b．删除归纳变量c．删除多余运算d．代码外提 8.过程P1调用P2时，连接数据不包含 A 。 a. 嵌套层次显示表 b. 老SP c. 返回地址 d. 全局DISPLAY地址 9.如果活动记录中没有DISPLAY表，则说明b。 a. 程序中不允许有递归定义的过程 b. 程序中不允许有嵌套定义的过程 c. 程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程 d. 程序中允许有递归定义的过程，也允许有嵌套定义的过程 10.关于必经结点的二元关系，下列叙述中不正确的是 D 。 a．满足自反性b．满足传递性c．满足反对称性d．满足对称性11.构造编译程序应掌握 D 。 a．源程序b．目标语言 c．编译方法d．以上三项都是 12.词法分析器的输出结果是__C___。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 13.文法G：S→xSx|y所识别的语言是 C 。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 14.同心集的合并有可能产生新的归约/归约冲突 15.四元式之间的联系是通过 B 实现的。 a.指示器 b.临时变量 c.符号表 d.程序变量 16.优化可生成_____的目标代码。 A. 运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小