1.构造正规式的DFA。（1）1(0|1)*101
状态转换表：
化简后得：
（2）(a|b)*(aa|bb)(a|b)*
化简后得；
2.将下图确定化和最小化。
a
a
0 1
解: 首先取A=ε-CLOSURE({0})={0},NFA确定化后的状态矩阵为:
Q’a b
A{0}{0,1}{1}
B{0,1}{0,1}{1}
C{1}{0}
NFA确定化后的DFA为：
a
A B
a
b b
C
将A,B 合并得:
a b
A C
a
3.构造一个DFA，它接受∑={0，1}上所有满足如下条件的字符串，
每个1都有0直接跟在后边。
解：按题意相应的正规表达式是0*(0 | 10)*0*
构造相应的DFA，首先构造NFA为
DFA为
4.给出NFA等价的正规式R。
方法一：首先将状态图转化为
得0,1
消去其余结点
NFA等价的正规式为（0|1）*11
方法二：NFA→右线性文法→正规式
A→0A|1A|1B
B→1C
C→ε
A=0A+1A+1B
B=1
A=0A+1A+11
A=(0+1)*11→(0|1)*11
5.试证明正规式（a|b ）*与正规式（a *|b *）*是等价的。
证明： (1)
正规式(a|b)*
的NFA 为
=>
其最简DFA 为
(2)正规式（a*|b*）*的 NFA 为： 其最简化DFA 为：
DFA
由于这两个正规式的最小DFA 相同，所以正规式(a|b)*等价于正规式(a*|b*)*。
6.设字母表∑={a,b},给出∑上的正规式R=b*ab(b|ab)*。
（1）试构造状态最小化的DFA M，使得L（M）=L（R）。
（2）求右线性文法G，使L（G）=L（M）。
解: (1)构造NFA:
(2)将其化为DFA,转换矩阵为:
再将其最小化得:
（2）对应的右线性文法G=（{X,W,Y},{a,b},P,X）P: X→aW|bX W→b Y|b y→a W|bY|b
文法G[〈单词〉]为：
〈单词〉-〉〈标识符〉|〈整数〉
〈标识符〉-〉〈标识符〉〈字母〉|〈标识符〉〈数字〉|〈字母〉
〈整数〉-〉〈数字〉|〈整数〉〈数字〉
〈字母〉-〉A|B|C
〈数字〉|->1|2|3
（1）改写文法G为G’，使L(G’)=L(G)。
（2）给出相应的有穷自动机。
解：（1）令D代表单词，I代表标识符，Z代表整数，有G’（D）：D→I | Z
I→A | B | C | IA | IB | IC | I1 | I2 | I3
Z→1 | 2 | 3 | Z1 | Z2 | Z3
(2) 左线性文法G’所对应的有穷自动机为：
M=({S,D,I,Z},{1,2,3,A,B,C},f,S,{D})
f: f(S,A)=I, f(S,B)=I, f(S,C)=I
f(S,1)=Z f(S,2)=Z f(S,3)=Z
f(I,A)=I f(I,B)=I f(I,C)=I
f(I,1)=I f(I,2)=I f(I,3)=I f(I, ε)=I
f(Z,1)=Z f(Z,2)=Z f(Z,3)=Z f(Z, ε)=D
给出下述文法所对应的正规式。
S→0A|1B
A→1S|1
B→0S|0
解: 相应的正规式方程组为：
S=0A+1B ①
A=1S+1 ②
B=0S+0 ③
将②，③代入①，得
S=01S+01+10S+10 ④
对④使用求解规则，得 (01|10)* （01|10）为所求。
给出文法G[S]，构造相应最小的DFA。
S->aS|bA|b
A-> aS
方法一：
S=aS+bA+b
A=aS
S=aS+baS+b S=(a+ba)*b
即：S=(a|ba)*b
正规式(a|ba)*b对应的NFA：
正规式(a|ba)*b对应的DFA：
b
化简后：
方法二：P43 右线性正规文法到有穷自动机的转换。
文法S->aS|bA|b
A-> aS
对应的NFA为：
M=({S,A,D},{a,b},f,{S},{D})
其中：f (S,a)=S, f(S,b)=A, f(S,b)=D, f(A,a)=S
其NFA图为：
a
S b A
a
b
D
NFA确定化后的状态矩阵为:
Q’a b
1{S}{S}{ A,D}
2{A,D }{S}φ
NFA确定化后的DFA为：
a b
1 2
a
给出下述文法所对应的正规式：
S->aA
A->bA+aB+b
B->aA
解：将文法改为：
S=aA ①
A=bA+aB+b ②
B=aA ③
将③代入②，得
A=bA+aaA+b ④将④用求解规则，得
A= (b|aa)*b ⑤,带入①得，S= a(b|aa)*b,
故文法所对应的正规式为R= a(b|aa)*b。
给出与下图等价的正规文法G。
a
A a
B b C
b a b
D
b
答: 该有穷自动机为:
M=({A,B,C,D},{a,b},f,{A},{C,D})
其中f(A,a)=B, f(A,b)=D, f(B,a)=φ, f(B,b)=C, f(C,a)=A, f(C,b)=D, f(D,a)=B, f(D,b)=D
根据其转换规则，与其等价的正规文法G为
G=（{A,B,C,D},{a,b},P,A）,其中
P : A→aB|bD B→bC C→aA|bD|ε D→aB|b D|ε
.解释下列术语和概念：
(1)确定有穷自动机
答：一个确定有穷自动机M是一个五元组M=（Q，Σ，f，S，Z），其中：
Q是一个有穷状态集合，每一个元素称为一个状态；
Σ是一个有穷输入字母表，每个元素称为一个输入字符；
f是一个从Q*Σ到Q的单值映射；
f（q
i ,a）=q
j
(q
i
,q
j
∈Q,a∈Σ)
表示当前状态为q
i ，输入字符为a时，自动机将转换到下一个状态q
j
,q
j
称为 q
i 的一个后继状态。我们说状态转换函数是单值函数，是指 f（q
i
,a）
惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。
S∈Q，是惟一的一个初态；
Z 真包含于Q，是一个终态集。
（2）非确定有穷自动机
一个非确定有穷自动机M是一个五元组M=（Q，Σ，f，S，Z），其中：Q是一个有穷状态集合，每一个元素称为一个状态；
Σ是一个有穷输入字母表，每个元素称为一个输入字符；
状态转换函数是一个多值函数。
f（q
i ,a）={某些状态的集合}(q
i
∈Q)，表示不能由当前状态、
当前输入字符惟一地确定下一个要转移的状态，即允许同一个状态对同一输入字符有不同的输出边。
S 包含于 A，是非空初态集。
Z 真包含于 Q，是一个终态集。
（3）正规式和正规集
有字母表Σ={a1,a2,…an}，在字母表Σ上的正规式和它所表示的正规集可用如下规则来定义：
（1）φ是Σ是的正规式，它所表示的正规集是φ，即空集{}。
（2）ε是Σ上的正规式，它所表示的正规集仅含一空符号串，即{ε} 。
（3）是Σ上的一个正规式，它所表示的正规集是由单个符号ai 所组成，即{ai}。
（4）e1和e2是Σ是的正规式，它们所表示的正规集分别为L(e1)和L(e2),则
①e1 | e2是Σ上的一个正规式，它所表示的正规集为
L(e1 | e2)=L(e1)∪L(e2).
②e1e2是Σ上的一个正规式，它所表示的正规集为
L(e1e2)=L(e1)L(e2).
③(e1)*是Σ上的一个正规式，它所表示的正规集为
L((e1)*)=L((e1))*.
3．1构造下列正规式相应的DFA。
(1)1 ( 0 | 1)*101
(2)( a | b )*( aa | bb )( a | b )*
(3)(( 0 | 1 )* | ( 11 ))*
(4)( 0 | 11*0 )*
3．2将下面图(a)和(b)分别确定化和最小化.
a
a
0 1
(a)
a
0 2 b 3
a
a a
a b b a
1 4 5
b
（b）
构造一个DFA，他接收∑={0，1}上所有满足如下条件的字符串，每个1都有0直接跟在右边。
给出文法G[S]，构造相应最小的DFA。
S aS | bA | b
A aS
给出下述文法所对应的正规式：
S->Aa
A->bA+aB+b
B->aA
给出与下图等价的正规文法G。
a
A a
B b C
b a b
给出与图中的NFA等价的正规式R。
文法G[〈单词〉]为：
〈单词〉〈标识符〉| 〈整数〉
〈标识符〉〈标识符〉〈字母〉| 〈标识符〉〈数字〉|〈字母〉〈整数〉〈数字〉|〈整数〉〈数字〉
〈字母〉 A | B | C
〈数字〉 1 | 2 | 3
（1）改写文法G为G’，使L(G’)=L(G).
（2）给出相应的有穷自动机。
试证明正规式（a|b）*与正规式（a*|b*）*是等价的。
3．10给出下述文法所对应的正规式：
S 0A | 1B
A 1S | 1
B 0S | 0
3．11设字母表Σ={a,b}，给出Σ上的正规式R=b*ab(b | ab)*.
(1)试构造状态最小化的DFA M，使得L（M）=L（R）。
(2) 求右线性文法G，使L（G）=L（M）。
3．12解释下列术语和概念。
（1）确定有穷自动机
（2）非确定有穷自动机
（3）正规式和正规集
第三章 N=>D=> {0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD L={a |a(0|1|3..|9)n且 n>=1} (0|1|3..|9)n且 n>=1 {ab,} a n b n n>=1 第6题. (1) <表达式> => <项> => <因子> => i (2) <表达式> => <项> => <因子> => (<表达式>) => (<项>) => (<因子>)=>(i) (3) <表达式> => <项> => <项>*<因子> => <因子>*<因子> =i*i (4) <表达式> => <表达式> + <项> => <项>+<项> => <项>*<因子>+<项> => <因子>*<因子>+<项> => <因子>*<因子>+<因子> = i*i+i (5) <表达式> => <表达式>+<项>=><项>+<项> => <因子>+<项>=i+<项> => i+<因子> => i+(<表达式>) => i+(<表达式>+<项>) => i+(<因子>+<因子>) => i+(i+i) (6) <表达式> => <表达式>+<项> => <项>+<项> => <因子>+<项> => i+<项> => i+<项>*<因子> => i+<因子>*<因子> = i+i*i 第7题
第9题 语法树 s s s* s s+a a a 推导: S=>SS*=>SS+S*=>aa+a* 11. 推导:E=>E+T=>E+T*F 语法树: E +T * 短语: T*F E+T*F 直接短语: T*F 句柄: T*F 12．
第2章习题 2-1 设有字母表A1 ={a,b,c,…,z}，A2 ={0,1,…,9}，试回答下列问题： (1) 字母表A1上长度为2的符号串有多少个？ (2) 集合A1A2含有多少个元素？ (3) 列出集合A1(A1∪A2)*中的全部长度不大于3的符号串。 2-2 试分别构造产生下列语言的文法： （1）{a n b n|n≥0}； （2）{a n b m c p|n,m,p≥0}； （3）{a n#b n|n≥0}∪{c n#d n|n≥0}； （4）{w#w r# | w∈{0,1}*,w r是w的逆序排列 }； （5）任何不是以0打头的所有奇整数所组成的集合； （6）所有由偶数个0和偶数个1所组成的符号串的集合。 2-3 试描述由下列文法所产生的语言的特点： （1）S→10S0S→aA A→bA A→a （2）S→SS S→1A0A→1A0A→ε （3）S→1A S→B0A→1A A→C B→B0B→C C→1C0C→ε （4）S→aSS S→a 2-4 试证明文法 S→AB|DC A→aA|a B→bBc|bc C→cC|c D→aDb|ab 为二义性文法。 2-5 对于下列的文法 S→AB|c A→bA|a B→aSb|c 试给出句子bbaacb的最右推导，并指出各步直接推导所得句型的句柄；指出句子的全部短语。
2-6 化简下列各个文法 (1) S→aABS|bCACd A→bAB|cSA|cCC B→bAB|cSB C→cS|c (2) S→aAB|E A→dDA|e B→bE|f C→c AB|dSD|a D→eA E→fA|g (3) S→ac|bA A→c BC B→SA C→bC|d 2-7 消除下列文法中的ε-产生式 (1) S→aAS|b A→cS|ε (2) S→aAA A→bAc|dAe|ε 2-8 消除下列文法中的无用产生式和单产生式 (1) S→aB|BC A→aA|c|aDb B→DB|C C→b D→B (2) S→SA|SB|A A→B|(S)|( ) B→[S]|[ ] (3) E→E+T|T T→T*F|F F→P↑F|P P→(E)|i 第2章习题答案 2-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-2 解： (1) 对应文法为G(S)=({S},{a,b},{ S→ε| aSb },S) (2) 对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε },S) (3)对应文法为G(S)=({S,X,Y},{a,b,c,d,#}, {S→X,S→Y,X→aXb|#, Y→cYd|# },S)
精品文档 第二章 P36-6 (1) L G ()1是0~9组成的数字串 (2) 最左推导: N ND NDD NDDD DDDD DDD DD D N ND DD D N ND NDD DDD DD D ??????????????????0010120127334 556568 最右推导: N ND N ND N ND N D N ND N D N ND N ND N D ??????????????????77272712712701274434 886868568 P36-7 G(S) O N O D N S O AO A AD N →→→→→1357924680||||||||||| P36-8 文法： E T E T E T T F T F T F F E i →+-→→|||*|/()| 最左推导: E E T T T F T i T i T F i F F i i F i i i E T T F F F i F i E i E T i T T i F T i i T i i F i i i ?+?+?+?+?+?+?+?+??????+?+?+?+?+?+********()*()*()*()*()*()*() 最右推导: E E T E T F E T i E F i E i i T i i F i i i i i E T F T F F F E F E T F E F F E i F T i F F i F i i i i i ?+?+?+?+?+?+?+?+?????+?+?+?+?+?+?+**********()*()*()*()*()*()*()*() 语法树：/********************************
第二章 3.何谓“标志符”，何谓“名字”，两者的区别是什么？ 答：标志符是一个没有意义的字符序列，而名字却有明确的意义和属性。 4.令+、*和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值。 （1）优先顺序（从高到低）为+、*和↑，同级优先采用左结合。 （2）优先顺序为↑、+、*，同级优先采用右结合。 答：（1）1+1*2↑2*1↑2=2*2↑2*1↑2=4↑2*1↑2=4↑2↑2=16↑2=256 （2）1+1*2↑2*1↑2=1+1*2↑2*1=1+1*4*1=2*4*1=2*4=8 6.令文法G6为 N-〉D|ND D-〉0|1|2|3|4|5|6|7|8|9 （1）G6的语言L（G6）是什么？ （2）给出句子0127、34、568的最左推导和最右推导。 （1）由0到9的数字所组成的长度至少为1的字符串。即：L（G6）={d n|n≧1,d∈{0,1,…,9}} 答： （2）0127的最左推导：N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 0127的最右推导：N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 （其他略） 7.写一个文法，使其语言是奇数集，且每个奇数不以0开头。 答：G（S）：S->+N|-N N->ABC|C C->1|3|5|7|9 A->C|2|4|6|8 B->BB|0|A|ε ［注］：可以有其他答案。 ［常见的错误］：N->2N+1 原因在于没有理解形式语言的表示法，而使用了数学表达式。 8.令文法为 E->T|E+T|E-T T->F|T*F|T/F F->(E)|i (1)给出i+i*i、i*(i+i)的最左推导和最右推导。 (2)给出i+i+i、i+i*i和i-i-i的语法树，并给出短语，简单短语和句柄。 答：(1) i*(i+i)的最左推导： E=>T=>T*F=>F*F=>i*F=>i*(E)=>i*(E+T)=>i*(T+T)=>i*(F+T)=>i*(i+T)=>i*(i+F)=> i*(i+i) i*(i+i)的最右推导： E=>T=>T*F=>T*(E) =>T*(E+T)=>T*(E+F)=>T*(E+i)=>T*(T+i)=>T*(F+i)=> T*(i+i)=> F*(i+i) => i*(i+i) （其他略） ［注］：要牢记每一步都是对最左（右）的一个非终结符号进行一步推导。 (2) i+i+i的语法树：
第一章习题解答 2．编译程序有哪些主要构成成分？各自的主要功能是什么？ 编译程序的主要构成成分有：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、表格管理程序及出错处理程序。 （1）词法分析程序：从左到右扫描源程序，识别单词及其有关属性； （2）语法分析程序：分析源程序的结构, 判别它是否为相应程序设计语言中的一个合法程序； （3）语义分析程序：审查源程序有无语义错误，为代码生成阶段收集类型信息； （4）中间代码生成程序：将源程序变成一种内部表示形式； （5）代码优化程序：对前阶段产生的中间代码进行变换或进行改造，使生成的目标代码更为高效； （6）目标代码生成程序：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码； （7）表格管理程序：保存编译过程中的各种信息； （8）出错处理程序：若编译过程中发现源程序存在错误，则报告错误的性质和错误发生的地点，有些还可以自动校正错误。 3．什么是解释程序？它与编译程序的主要不同是什么？ 解释程序接受某个语言的程序并立即运行这个源程序。它的工作模式是一个个的获取、分析并执行源程序语句，一旦第一个语句分析结束，源程序便开始运行并且生成结果，它特别适合程序员交互方式的工作情况。 而编译程序是一个语言处理程序，它把一个高级语言程序翻译成某个机器的汇编或二进制代码程序，这个二进制代码程序再机器上运行以生成结果。 它们的主要不同在于：解释程序是边解释边执行，解释程序运行结束即可得到该程序的运行结果，而编译程序只是把源程序翻译成汇编或者二进制程序，这个程序再执行才能得到程序的运行结果。（当然还有其他不同，比如存储组织方式不同）
第2章习题解答 1.文法G[S]为： S->Ac|aB A->ab B->bc 写出L(G[S])的全部元素。 [答案] S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc} ============================================== 2. 文法G[N]为： N->D|ND D->0|1|2|3|4|5|6|7|8|9 G[N]的语言是什么？ [答案] G[N]的语言是V+。V={0,1,2,3,4,5,6,7,8,9} N=>ND=>NDD.... =>NDDDD...D=>D......D =============================================== 3.已知文法G[S]： S→dAB A→aA|a B→ε|bB 问：相应的正规式是什么？G[S]能否改写成为等价的正规文法？[答案] 正规式是daa*b*；
相应的正规文法为(由自动机化简来)： G[S]:S→dA A→a|aB B→aB|a|b|bC C→bC|b 也可为(观察得来):G[S]:S→dA A→a|aA|aB B→bB|ε ===================================================================== ========== 4.已知文法G[Z]： Z->aZb|ab 写出L(G[Z])的全部元素。 [答案] Z=>aZb=>aaZbb=>aaa..Z...bbb=> aaa..ab...bbb L(G[Z])={a n b n|n>=1} ===================================================================== ========= 5.给出语言{a n b n c m|n>=1,m>=0}的上下文无关文法。 [分析] 本题难度不大，主要是考上下文无关文法的基本概念。上下文无关文法的基本定义是：A->β,A∈Vn，β∈（Vn∪Vt）*，注意关键问题是保证a n b n的成立，即“a与b的个数要相等”，为此，可以用一条形如A->aAb|ab的产生式即可解决。 [答案] 构造上下文无关文法如下： S->AB|A A->aAb|ab B->Bc|c [扩展]
第1章引论 第1题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1） 编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2） 源程序：源语言编写的程序称为源程序。 （3） 目标程序：目标语言书写的程序称为目标程序。 （4） 编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5） 后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6） 遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可以。如果搞不清楚，就回答八部分。 第3题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。 解释程序是解释、执行高级语言源程序的程序。解释方式一般分为两种：一种方式是，源程序功能的实现完全由解释程序承担和完成，即每读出源程序的一条语句的第一个单词，则依据这个单词把控制转移到实现这条语句功能的程序部分，该部分负责完成这条语句的功
编译原理课后题答案 第二章 P36-6 (1) L G () 1是0~9组成的数字串 (2) 最左推导: 最右推导: P36-7 G(S) P36-8 文法： 最左推导: 最右推导: 语法树：/******************************** *****************/ P36-9 句子iiiei有两个语法树： P36-10 /************** ***************/ P36-11 /*************** L1: L2: L3: L4: ***************/ 第三章习题参考答案P64–7 (1)
最小化： P64–8 (1) (2) (3) P64–12 (a) a a,b a 0
给状态编号： a a a b b b 最小化： a a b b a b (b) 已经确定化了, 进行最小化 最小化： P64 –14 (1) 0 1 0 (2): (|)*010 1 εε 0 0 0 Y Y
最小化： 0 1 1 1 0 0 第四章 P81–1 (1) 按照T,S 的顺序消除左递归 递归子程序： procedure S; begin if sym='a' or sym='^' then abvance else if sym='(' then begin advance;T; if sym=')' then advance; else error; end else error end; procedure T; begin S; T end;
procedure 'T; begin if sym=',' then begin advance; S;'T end end; 其中: sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序 (2) FIRST(S)={a,^,(} FIRST(T)={a,^,(} FIRST('T)={,,ε} FOLLOW(S)={),,,#} FOLLOW(T)={)} FOLLOW('T)={)} 预测分析表 是LL(1)文法 P81–2 文法： (1) 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,^,+,),#} (2)
第 1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。 第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
第四章语义分析和中间代码生成 4.1 完成下列选择题： (1) 四元式之间的联系是通过实现的。 a. 指示器 b. 临时变量 c. 符号表 d. 程序变量 (2) 间接三元式表示法的优点为。 a. 采用间接码表，便于优化处理 b. 节省存储空间，不便于表的修改 c. 便于优化处理，节省存储空间 d. 节省存储空间，不便于优化处理 (3) 表达式(┐A∨B)∧(C∨D)的逆波兰表示为。 a. ┐AB∨∧CD∨ b. A┐B∨CD∨∧ c. AB∨┐CD∨∧ d. A┐B∨∧CD∨ (4) 有一语法制导翻译如下所示： S→bAb {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 【解答】 (1) b (2) a (3) b (4) b 4.2 何谓“语法制导翻译”？试给出用语法制导翻译生成中间代码的要点，并用一简例予以说明。 【解答】语法制导翻译(SDTS)直观上说就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并且在语法分析的同时执行这些子程序。也即在语法分析过程中，当一个产生式获得匹配(对于自上而下分析)或用于归约(对于自下而上分析)时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。 用语法制导翻译(SDTS)生成中间代码的要点如下： (1) 按语法成分的实际处理顺序生成，即按语义要求生成中间代码。 (2) 注意地址返填问题。 (3) 不要遗漏必要的处理，如无条件跳转等。 例如下面的程序段： if (i>0) a=i+e-b*d; else a=0; 在生成中间代码时，条件“i>0”为假的转移地址无法确定，而要等到处理“else”时方可确定，这时就存在一个地址返填问题。此外，按语义要求，当处理完(i>0)后的语句(即“i>0”为真时执行的语句)时，则应转出当前的if语句，也即此时应加入一条无条件跳转指令，并且这个转移地址也需要待处理完else之后的语句后方可获得，就是说同样存在着地址返填问题。对于赋值语句a=i+e-b*d，其处理顺序(也即生成中间代码顺序)是先生成i+e的代码，再生成b*d的中间代码，最后才产生“-”运算的中间代码，这种顺序不能颠倒。 4.3 令S.val为文法G[S]生成的二进制数的值，例如对输入串101.101，则S.val= 5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则，G(S)如下： G[S]: S→L.L|L
《编译原理》课后习题答案第一章 第 1 章引论 第 1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶 段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符 号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。
第 2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程 序的总体结构图。 答案： 一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机表达形式。 语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式 的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的 各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源 程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误
第四章 习题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
第1章引言 1、解释下列各词 源语言:编写源程序的语言（基本符号，关键字），各种程序设计语言都可以作为源语言。 源程序: 用接近自然语言（数学语言）的源语言（基本符号，关键字）编写的程序，它是翻译程序处理的对象。 目标程序: 目标程序是源程序经过翻译程序加工最后得到的程序。目标程序 （结果程序）一般可由计算机直接执行。 低级语言：机器语言和汇编语言。 高级语言：是人们根据描述实际问题的需要而设计的一个记号系统。如同自然语言（接近数学语言和工程语言）一样，语言的基本单位是语句，由符号组和一组用来组织它们成为有确定意义的组合规则。 翻译程序: 能够把某一种语言程序（源语言程序）改变成另一种语言程序（目标语言程序），后者与前者在逻辑上是等价的。其中包括：编译程序，解释程序，汇编程序。 编译程序: 把输入的源程序翻译成等价的目标程序（汇编语言或机器语言）， 然后再执行目标程序（先编译后执行），执行翻译工作的程序称为编译程序。 解释程序: 以该语言写的源程序作为输入，但不产生目标程序。按源程序中语句动态顺序逐句的边解释边执行的过程，完成翻译工作的程序称为解释程序。 2、什么叫“遍”？ 指对源程序或源程序的中间形式（如单词，中间代码）从头到尾扫描一次，并作相应的加工处理，称为一遍。 3、简述编译程序的基本过程的任务。 编译程序的工作是指从输入源程序开始到输出目标程序为止的整个过程，整个过程可以划分5个阶段。 词法分析：输入源程序，进行词法分析，输出单词符号。 语法分析：在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位，并判断输入串是否构成语确的“程序”。 中间代码生成：按照语义规则把语法分析器归约（或推导）出的语法单位翻译成一定形式的中间代码。 优化：对中间代码进行优化处理。 目标代码生成：把中间代码翻译成目标语言程序。 4、编译程序与解释程序的区别？ 编译程序生成目标程序后，再执行目标程序；然而解释程序不生成目标程序，边解释边执行。 5、有人认为编译程序的五个组成部分缺一不可，这种看确吗？ 编译程序的5个阶段中，词法分析，语法分析，语义分析和代码生成生成是必须完成的。而中间代码生成和代码优化并不是必不可少的。优化的目的是为了提高目标程序的质量，没有这一部分工作，仍然能够得到目标代码。 6、编译程序的分类 目前基本分为：诊断编译程序，优化编译程序，交叉编译程序，可变目标编译程序。
第二章 文法和语言 p48 4、6（6）、11、 12（2）（6）、18（2） 4 证明文法G=（{E,O}，{(，)，+，*，v ，d}，P ，E ）是二义的,其中P 为 E → EOE | (E) | v | d O → + | * 证明： 因为E=〉 EOE =〉EOEOE =〉EOEOv =〉EOE+v =〉EOv+v =〉E*v+v =〉v*v+v ， 句子v*v+v 有两棵不同的语法树 所以文法G 是二义的。 问题：1）只有文字说明，比如v*v+v 有两棵语法树，但没有画出语法树或者最左（最右）推导过程 2）给出的是不同句子（v*v+d v+v*d ）的语法树 6、已知文法G ： E E E E O O v * v + v E E E E O O v + v * v
〈表达式〉∷=〈项〉|〈表达式〉+〈项〉 〈项〉∷=〈因子〉|〈项〉*〈因子〉 〈因子〉∷=（〈表达式〉）| i 试给出下述表达式的推导及语法树 （6）i+i*i 推导过程： 〈表达式〉=〉〈表达式〉+〈项〉E=〉E+T =〉〈表达式〉+〈项〉*〈因子〉=〉E+ T*F =〉〈表达式〉+〈项〉* i =〉E+ T*i =〉〈表达式〉+ 〈因子〉* i =〉E+F*i =〉〈表达式〉+ i* i =〉E+i*i =〉〈项〉+ i* i =〉T +i*i =〉〈因子〉+ i* i =〉F +i*i =〉i +i*i =〉i +i*i 共8步推导 语法树： 〈表达式〉 + 〈因子〉〈项〉 i 〈因子〉 i 〈项〉 〈项〉 〈因子〉 i *
11、一个上下文无关文法生成句子abbaa的推导树如下： （1）给出该句子相应的最左推导和最右推导 （2）该文法的产生式集合P可能有哪些元素？ （3）找出该句子的所有短语、简单短语、句柄。 （1）最左推导： S=〉ABS=〉aBS=〉aSBBS=〉aBBS =〉abBS=〉abbS =〉abbAa=〉abbaa 最右推导： S =〉ABS=〉ABAa=〉ABaa=〉ASBBaa =〉ASBbaa=〉ASbbaa=〉Abbaa=〉abbaa （2）该文法的产生式集合P可能有下列元素： S→ABS | Aa|εA→a B→SBB|b
第三章 1、L(G[S])={ abc } 2、L(G[N])={ n 位整数或空字符串 | n>0 } 3、G[E]：E —>E+D | E-D | D D —>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 4、L(G[Z])={ a n b n | n>0 } 5、(1) 考虑不包括“0”的情况 G[S]：S —>0S | ABC | 2 | 4| 6 | 8 A —>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B —>AB | 0B | ε C —>0 | 2 | 4 | 6 | 8 考虑包括“0”的情况： G[S]：S —>AB | C B —>AB | C A —>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C —>0 | 2 | 4 | 6 | 8 (2)方法1： G[S]：S —> ABC | 2 | 4 | 6 | 8 A —>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 B —>AB | 0B | ε C —>0 | 2 | 4 | 6 | 8 方法2： G[S]：S —>AB | C B —> AB | 0B | C | 0 A —> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C —>2 | 4 | 6 | 8 6、设<表达式>为E ，<项>为T ，<因子>为F ，注：推导过程不能省略，以下均为最左推导 (1) E => T => F => i (4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i (6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I 7、 <表达式> <表达式> * <表达式> <表达式> + <表达式> i i i <表达式> <表达式> + <表达式> i <表达式> * <表达式> i i
第二章 词法分析 2.1 完成下列选择题： (1) 词法分析器的输出结果是 。 a. 单词的种别编码 b. 单词在符号表中的位置 c. 单词的种别编码和自身值 d. 单词自身值 (2) 正规式M1和M2等价是指 。 a. M1和M2的状态数相等 b. M1和M2的有向边条数相等 c. M1和M2所识别的语言集相等 d. M1和M2状态数和有向边条数相等 (3) DFA M(见图2-1)接受的字集为 。 a. 以0开头的二进制数组成的集合 b. 以0结尾的二进制数组成的集合 c. 含奇数个0的二进制数组成的集合 d. 含偶数个0的二进制数组成的集合 【解答】 (1) c (2) c (3) d 图2-1 习题2.1的DFA M 2.2 什么是扫描器？扫描器的功能是什么？ 【解答】 扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。 2.3 设M=({x,y}, {a,b}, f, x, {y})为一非确定的有限自动机，其中f 定义如下： f(x,a)={x,y} f {x,b}={y} f(y,a)=Φ f{y,b}={x,y} 试构造相应的确定有限自动机M ′。 【解答】 对照自动机的定义M=(S,Σ,f,So,Z)，由f 的定义可知f(x,a)、f(y,b)均为多值函数，因此M 是一非确定有限自动机。 先画出NFA M 相应的状态图，如图2-2所示。 图2-2 习题2.3的NFA M 用子集法构造状态转换矩阵，如表 表2-1 状态转换矩阵 1b a
编译原理第二版课后答案张素琴 【篇一：清华大学编译原理第二版课后习答案】 ss=txt> 第1 章引论 第1 题 解释下列术语： （1）编译程序 （2）源程序 （3）目标程序 （4）编译程序的前端 （5）后端 （6）遍 答案： （1）编译程序：如果源语言为高级语言，目标语言为某台计算机 上的汇编语言或机器语言，则此翻译程序称为编译程序。 （2）源程序：源语言编写的程序称为源程序。 （3）目标程序：目标语言书写的程序称为目标程序。 （4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作 主要依赖于源语言而与目标机无关。通常前端包括词法分析、语法 分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。 （5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间 代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号 表操作。 （6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完 成规定任务的过程。第2 题 一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什 么？并画出编译程序的总体结构图。 答案： 一个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化 程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。
词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出 单词的机内表达形式。语法分析程序：检查源程序中存在的形式语 法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保 存到各类语义信息表中。 中间代码生成程序：按照语义规则，将语法分析程序分析出的语法 单位转换成一定形式的中间语言代码，如三元式或四元式。 《编译原理》课后习题答案第一章 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 表格管理程序：负责建立、填写和查找等一系列表格工作。表格的 作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每 个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需 要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。 当编译程序发现源程序中的错误时，错误处理程序负责报告出错的 位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 注意：如果问编译程序有哪些主要构成成分，只要回答六部分就可 以。如果搞不清楚，就回答八部分。 第3 题 何谓翻译程序、编译程序和解释程序？它们三者之间有何种关系？ 答案： 翻译程序是指将用某种语言编写的程序转换成另一种语言形式的程 序的程序，如编译程序和汇编程序等。 编译程序是把用高级语言编写的源程序转换（加工）成与之等价的 另一种用低级语言编写的目标程序的翻译程序。 《编译原理》课后习题答案第一章 是哪种方式，其加工结果都是源程序的执行结果。目前很多解释程 序采取上述两种方式的综合实现方案，即先把源程序翻译成较容易解释执行的某种中间代码程序，然后集中解释执行中间代码程序，最后得到运行结果。 广义上讲，编译程序和解释程序都属于翻译程序，但它们的翻译方 式不同，解释程序是边翻译（解释）边执行，不产生目标代码，输
1.2 计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？ 【解答】计算机执行用高级语言编写的程序主要有两种途径：解释和编译。在解释方式下，翻译程序事先并不采用将高级语言程序全部翻译成机器代码程序，然后执行这个机器代码程序的方法，而是每读入一条源程序的语句，就将其解释(翻译)成对应其功能的机器代码语句串并执行，而所翻译的机器代码语句串在该语句执行后并不保留，最后再读入下一条源程序语句，并解释执行。这种方法是按源程序中语句的动态执行顺序逐句解释(翻译)执行的，如果一语句处于一循环体中，则每次循环执行到该语句时，都要将其翻译成机器代码后再执行。在编译方式下，高级语言程序的执行是分两步进行的：第一步首先将高级语言程序全部翻译成机器代码程序，第二步才是执行这个机器代码程序。因此，编译对源程序的处理是先翻译，后执行。从执行速度上看，编译型的高级语言比解释型的高级语言要快，但解释方式下的人机界面比编译型好，便于程序调试。这两种途径的主要区别在于：解释方式下不生成目标代码程序，而编译方式下生成目标代码程序。 1.3 请画出编译程序的总框图。如果你是一个编译程序的总设计师，设计编译程序时应当考虑哪些问题？ 【解答】编译程序总框图如图所示。 作为一个编译程序的总设计师，首先要深刻理解被编 译的源语言其语法及语义；其次，要充分掌握目标指令的 功能及特点，如果目标语言是机器指令，还要搞清楚机器 的硬件结构以及操作系统的功能；第三，对编译的方法及 使用的软件工具也必须准确化。总之，总设计师在设计编 译程序时必须估量系统功能要求、硬件设备及软件工具等 诸因素对编译程序构造的影响等。 2.2 什么是扫描器？扫描器的功能是什么？ 【解答】扫描器就是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。通常是把词法分析器作为一个子程序，每当词法分析器需要一个单词符号时就调用这个子程序。每次调用时，词法分析器就从输入串中识别出一个单词符号交给语法分析器。