编译原理课后答案
- 格式：doc
- 大小：829.00 KB
- 文档页数：32
第二章 高级语言及其语法描述
4．令+、*和↑代表加，乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1+1*2↑2*1↑2的值：
（1） 优先顺序（从高至低）为+，*和↑，同级优先采用左结合。
（2） 优先顺序为↑，+，*，同级优先采用右结合。
解：（1）1+1*2↑2*1↑2=2*2↑1*1↑2=4↑1↑2=4↑2=16
（2）1+1*2↑2*1↑2=1+1*2*1=2*2*1=2*2=4
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）L（G6）=｛a|a∈∑+,∑=﹛0,1,2,3,4,5,6,7,8,9｝｝
（2）N ＝＞ND＝＞ NDD＝＞ NDDD＝＞ DDDD＝＞ 0DDD＝＞ 01DD＝＞ 012D＝＞ 0127
N＝＞ ND＝＞ N7＝＞ ND7＝＞ N27＝＞ ND27＝＞ N127＝＞ D127＝＞ 0127
N＝＞ ND＝＞ DD＝＞ 3D＝＞ 34
N＝＞ ND＝＞ N4＝＞ D4 ＝＞34
N＝＞ ND＝＞ NDD＝＞ DDD＝＞ 5DD＝＞ 56D＝＞ 568
N＝＞ ND＝＞ N8＝＞ ND8＝＞ N68＝＞ D68＝＞ 568
7．写一个文法，使其语言是奇数集，且每个奇数不以0开头。
解：A→SN, S→+|-|∑, N→D|MD
D→1|3|5|7|9, M→MB|1|2|3|4|5|6|7|8|9 B→0|1|2|3|4|5|6|7|8|9
8. 文法：
ETETETTFTFTFFEi|||*|/()|
最左推导:
EETTTFTiTiTFiFFiiFiiiETTFFFiFiEiETiTTiFTiiTiiFiii********()*()*()*()*()*()*()
最右推导:
EETETFETiEFiEiiTiiFiiiiiETFTFFFEFETFEFFEiFTiFFiFiiiii**********()*()*()*()*()*()*()*()
语法树：/********************************
EEFTE+TFFT+iiiEEFTE-TFFT-iiiEEFT+TFFTiii*i+i+ii-i-ii+i*i
*****************/
9．证明下面的文法是二义的：
S→ iSeS|iS|I
解：因为iiiiei有两种最左推导，所以此文法是二义的。
10．把下面文法改写为无二义的：
S→SS|(S)|()
解：S→ ST|T, T→ (S)|()
11．给出下面语言的相应文法
L1=｛anbnci|n≥1,i≥0｝
L2=｛aibncn|n≥1,i≥0｝
L3=｛anbnambm|n,m≥0｝
L4=｛1n0m1m0n|n,m≥0｝
解：（1）S→ AB|A
A→ aAb|ab
B→ c|cB
(2) S→ AB|B
A→ a|aA
B→ bBc|bc
(3) S→ AB|A|B|∑
A→ aAb|ab
B→ aBb|ab
(4) S→ 1S0|0A1
A→ 0A1|01
第三章 词法分析
7.构造下列正规式的相应的DFA
1(0|1)*101
1(1010*|1(010)*1)*0
0*10*10*10*
(00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
解答：
（1）1(0|1)*101
I I0 I1
{X} Ф {A,B,C}
{A,B,C} { B,C} { B,C,D}
{B,C} { B,C} { B,C,D}
{B,C,D} { B,C,E} { B,C,D}
{B,C,E} { B,C} {B,C,D,y}
{B,C,D,y} {B,C,E} { B,C,D}
S 0 1
A B
B C D
C C D
D E D
E C F
F E D
(2) 1(1010*|1(010)*1)*0
I I0 I1
{X} Ф {A,B,C}
{A,B,C} {y} {D,H,I,L}
{y} Ф Ф
{D,H,I,L} {E,J} {B,C}
{E,J} Ф {B,C,F,G,K}
{B,C} {y} {D,H,I,L}
{B,C,F,G,K} {B,C,G,I,L,y} {D,H,I,L}
{B,C,G,I,L,y} {B,C,G,J,y} {B,C,D,H,I,L }
{B,C,G,J,y} {B,C,G, y} {D,H,I,L}
{D,H,I,K,L} {E,I,J,L} {B,C}
{E,J,y} Ф {B,C,F,G,K }
{E,I,J,L} {J} {B,C,F,G,K }
{J} Ф {K}
{K} {I,L} Ф
{I,L} {J} {B,C}
8.给出下面正规表达式
（1）以01结尾的二进制数串
（2）能被5整除的十进制整数
（3）包含奇数个1或者奇数个0的二进制数串
（4）英文字母组成的所有符号串，要求符号串中的字母按照字典序排列。
（7）不包含子串abb的由a和b组成的符号串的全体。
解答：
（1） （0|1）*01
（2） (1|2|…|9)(0|1|2|…|9)*(0|5)|0|5
（3） 0*1(0*10*10*)*
（4） A*B*…Z*
(7) b*(a|ab)*
9.对下面的情况给出DFA以及正规表达式。
（1）{0，1}上的含有子串010的所有串。
（2）{0，1}上不含子串010的所有串。
解答：
（1）（0|1）*010（0|1）*
（2）1*(0|1*|1)*1*
12 将图3.8的（a）和(b)分别确定化和最少化。
解：1 确定化
a b
｛0｝ ｛0,1｝ ｛1｝
｛0,1｝ ｛0,1｝ ｛1｝
｛1｝ ｛0｝ __
令A=｛0｝ B=｛0，1｝ C=｛1｝
则状态转换图为：
2 最少化
首先，所有状态可分为 终态集{A B} 非终态集{C}
其次，考察{A B}，由于{A B}由a到{B}，由b到{C}，所以不可分，令A={A B}
则最少化后的状态转换图为：
14 构造一个DFA，它接受∑＝｛0,1｝上所有满足下列条件的字符串，每个1都有0直接跟在右边。
解：1 正规式为： （0|10）﹡
2 由正规式转化为NFA：
3 由NFA到DFA：
0 1
{X} {X} {b}
{b} {X} __
令A={X} B={b}
则状态转换图为：
4 最少化
终态集{A} 非终态集{B}
显然不可再划分，则最简的DFA即为：
15 给定右线性文法G：
S→0S|1S|1A|0B
A→1C|1
B→0C|0
C→0C|1C|1|0
求出一个与G等价的左线性文法。
解：1 由右线性文法构造NFA：
2 从NFA中构造左线性文法：
F→A1|B0|C0|C1
A→S1|1
B→S0|0
C→C0|C1|A1|B0
S→S0|S1|1|0
第四章 语法分析－自上而下分析
1. 考虑下面文法 G1:
S→a|∧|(T)
T→T,S|S
(1)消去G1的左递归，然后对每个非终结符写出不带回溯的递归子程序。
(2)经过改写的文法是否是LL（1）的？给出它的预测分析表。
解答：
（1）消去G1的左递归：S→a|∧|(T)
T→ST’
T’ →,ST’|ε
递归子程序：
PROCEDURE S;
IF sym=’a’ THEN ADVANCE
ELSE IF sym=’ ∧’ THEN ADVANCE
ELSE IF sym=’ (’ THEN
BEGIN
ADVANCE
T;
IF sym=’ )’ THEN ADVANCE
ELSE ERROR
END
ELSE ERROR;
PROCEDURE T;
BEGIN
S;T’
END;
PROCEDURE S;
IF sym=’ ,’ THEN
BEGIN
ADVANCE
S;T’
END;
（2）是LL（1）文法。
FIRST(S)={ a,∧,( } FIRST(T)={ a,∧,( } FIRST(T’)={ ,,ε }
FOLLOW(S)={ #, , , ε, ) } FOLLOW(T)={ ) } FOLLOW(T’)={ ) }
预测分析表如下：
