编译原理王力红著习题答案 2 1Word下载.docx
《编译原理王力红著习题答案 2 1Word下载.docx》由会员分享，可在线阅读，更多相关《编译原理王力红著习题答案 2 1Word下载.docx（38页珍藏版）》请在冰点文库上搜索。
最右推导：
T*i=>
F*i=>
最左归约：
i*i=>
F*i=>
T*i=>
T*F=>
T=>
E
最右归约：
i*F=>
F*F=>
2-4设有文法G[A]：
A→bA|cc
判断符号串bbc，bbbcc，bbA，bbAc是否是G[A]的句型或句子。
解答：
∵A=>
bA=>
bbA=>
bbbA=>
bbbcc
∴bbA是G[A]的句型,bbbcc是G[A]的句子，
bbAc不是G[A]的句型,bbc不是G[A]的句子。
2-5分别求下列文法所描述的语言：
①G1[S]：
S→aaSbb|ε
∵S=>
aaSbb=>
aaaaSbbbb=>
…
∴L（G1[S]）={a2nb2n|n≥0}
②G2[S]：
S→10S0|aA
A→bA|a
基本的求解方法：
语言的定义
解:
10S0=>
1010S00=>
…=>
（10）mS0m=>
（10）maA0m
A=>
bnA=>
bna
∴S=>
（10）maA0m=>
（10）mabna0m
L（G2[S]）={（10）mabna0m|m≥0,n≥0}
③G3[S]：
S→SS|1A0
A→1A0|ε
SS=>
SSm=>
1A0（1A0）m
1A0=>
11A00=>
1mA0m=>
1mA0m=>
1m0m
∴S=>
1A0（1A0）m=>
11m0m0（11m0m0）n
L（G2[S]）={（1m0m）n|m≥1,n≥1}
2-6分别对下列语言构造相应的文法：
1可以以0开头的所有正偶数的集合;
参考答案：
e=（0|1|2|…|9）*（0|2|4|6|8）
G[S]:
S→（0|1|2|…|9）S|0|2|4|6|8
2不以0开头的所有奇数的集合；
e=（1|3|5|7|9）|（1|2|3|4|5|6|7|8|9）（0|1|2||3|4|5|6|7|8|9）*（1|3|5|7|9）
S→BA|C
A→DA|C
B→1|2|3|4|5|6|7|8|9
C→1|3|5|7|9
D→0|B
3能被5整除的所有整数的集合；
e=（0|1|2|…|9）*（0|5）
S→0S|1S|2S|…|9S|0|5
4以a开头、b结尾的∑={a,b}上的任意符号串的集合；
e=a（a|b）*b
S→aA
A→aA|bA|b
5{an#bn|n≥0}∪{cn#dn|n≥0}；
S→A|B
A→aAb|#
B→cBd|#
6{1n0m1m0n|m,n≥0}；
S→1S0|A
A→0A1|ε
7{w#wr#|w∈{0,1}*,wr表示将w中的符号按逆序排列所得的符号串}；
S→A#
A→0A0|1A1|#
2-7已知算术表达式文法G[E]（见题2-3），根据定义求句型E+i*i的短语、简单短语和句柄。
E+T=>
E+T*F=>
E+F*F=>
E+i*F=>
E+i*i
E+F*i=>
E+T*i=>
E+F*i=>
短语：
i*i，E+i*i
简单短语：
i，
句柄：
i
2-8分别写出一个描述如下语言的非左递归文法和非右递归文法：
{s;
，s;
s;
，…}
并分别给出句子s;
的最左推导、最右推导和相应的语法树。
非左递归文法：
S→s;
S|s;
S=>
相应的语法树：
非右递归文法：
S→Ss;
|s;
Ss;
=>
2-9已知算术表达式文法G[E]（见题2-3），根据语法树求句型E+i*i的短语、简单短语和句柄。
求语法树：
根据语法树：
i，i*i，E+i*i
2-10设有文法G[A]：
A→#B#
B→B+C|C
C→C*a|a
1至少采用两种EBNF表示法改写该文法；
B→（B+|ε）C
C→（C*|ε）a
2用语法图表示该文法。
习题3
3-1画出下列有限自动机的状态转换图，并说明它所识别或接受的语言是什么？
1M＝（{S，A，B，C}，{0，1}，f，S，{S}），其转换函数为：
f（S，0）=Bf（B，0）=S
f（S，1）=Af（B，1）=C
f（A，0）=Cf（C，0）=A
f（A，1）=Sf（C，1）=B
有限自动机的状态转换图
它所识别或接受的语言是：
L（M）={ε,00,11,0101,0110,1001,1010,0011,0000,1111,…,}
由偶数个0或偶数个1组成的二进制串。
2M＝（{0，1，2}，{a，b}，f，0，{2}），其状态转移矩阵为：
符号
状态
a
b
{1,2}
{0}
1
{0,1}
φ
2
{0,2}
{1}
有限自动机M的状态转换图：
有限自动机M所识别或接受的语言是：
L（M）={a,aaa,abaa,ba,baaa,babaa,…}
3-2设计字母表∑={a,b}上的确定有限自动机，使它能识别或接受下列语言：
1以aa为首的所有符号串集合；
正则式e=aa（a|b）*
NFA：
DFA：
2,3,4
3,4
最小化：
3
2，3等价，合并。
2以aa结尾的所有符号串集合；
e=（a|b）*aa
I
Ia
Ib
X
X,A
X,A,Y
重命名：
{X}为0
{X,A}为1
{X,A,Y}为2
3含有相继两个a或相继两个b的所有符号串集合。
e=（a|b）*（aa|bb）（a|b）*
3-3试把下述NFA变换为DFA。
最基本的方法是子集法：
-
{1，2}
{0}为0，{1}为1，{1，2}为2，包含原终态2的{1，2}为新终态，
于是所求DFA为：
最基本的方法：
子集法：
3-5试把下列FA确定化（若需要的话）和最小化。
2,4状态是死状态，应删除。
只有一个状态的FA肯定是确定化的和最小化的。
此FA是DFA，不需要确定化。
首先按终态与非终态划分：
{0，1}，{2，3，4，5}；
然后计算：
4
对于输入a，b，{0，1}后继都属于同一集合，故0，1等价。
5
对于输入a，{2，4}后继属于同一集合{0，1}，{3，5}后继属于同一集合{3，5}，故可继续划分为：
{2，4}，{3，5}。
进一步计算：
2，4等价。
3，5等价。
合并等价状态，最小化为：
习题4
4-1假定符号表采用栈结构组织，请给出下列C程序段执行过程中符号表的变化情况。
inti,j;
intfun（intn）
{
chari,t;
floatj;
}
char*j;
习题5
5-3请识别下列PASCAL程序段中的单词符号并给出单词的内部编码。
functionmax（i:
integer;
j:
integer）:
（*returnmaximumofintegersiandj*）
begin
ifi＞jthenmax:
=i
elsemax:
=j
end;
function保留字
max标识符
（分隔符
i标识符
:
分隔符
integer标识符
;
j标识符
）分隔符
begin保留字
if保留字
＞特殊符
then保留字
=特殊符
else保留字
end保留字
习题6
6-1设有文法G[S]：
S→a|^|（T）
T→T,S|S
1求符号串S和T,S的FIRST集；
2求非终结符S和T的FOLLOW集；
3求各产生式的SELECT集；
4求非终结符S和T的FIRSTVT集和LASTVT集。
非终结符号的FIRST集合：
FIRST（S）={a,^,（}
FIRST（T）={a,^,（}
1符号串的FIRST集：
FIRST（T,S）=FIRST（T）={a,^,（}
2非终结符号的FOLLOW集合：
FOLLOW（S）={#,）,,}
FOLLOW（T）={）,,}
3各产生式的SELECT集合：
SELECT（S→a）=FIRST（a）={a}
SELECT（S→^）=FIRST（^）={^}
SELECT（S→（T））=FIRST（（T））={（}
SELECT（T→T,S）=FIRST（T,S）={a,^,（}
SELECT（T→S）=FIRST（S）={a,^,（}
4非终结符的FIRSTVT集和LASTVT集：
FIRSTVT（S）={a,^,（}
FIRSTVT（T）={,}∪FIRSTVT（S）={,}∪{a,^,（}={,,a,^,（}
LASTVT（S）={a,^,）}
LASTVT（T）={,}∪LASTVT（S）={,}∪{a,^,）}={,,a,^,）}
6-2判断题6-1的文法能否进行确定的自顶向下分析，为什么?
如不能，则改造之，然后
写出句子（a,^,a）的最左推导过程（采用表6.1的格式）。
∵对于T：
SELECT（T→T,S）∩SELECT（T→S）={a,^,（}≠φ
∴题6-1的文法不能进行确定的自顶向下分析。
消除直接左递归，得：
G’[S]：
T→ST’
T’→,ST’|ε
FIRST（T’）={,,ε}
非终结符号的FOLLOW集合：
FOLLOW（S）={#,,,）}
FOLLOW（T）={）}
FOLLOW（T’）={）}
各产生式的SELECT集合：
SELECT（S->
a）={a}
^）={^}
（T））={（}
SELECT（T->
ST’）={a,^,（}
SELECT（T’->
ST’）={,}
ε）={）}
当前句型
输入符号
余留符号
下一步选用产生式
S
（
a,^,a）
S->
（T）,∵（∈SELECT（S->
（T））
（T）
^,a）
T->
ST’,∵a∈SELECT（T->
ST’）
（ST’）
a,∵a∈SELECT（S->
a）
（aT’）
^,a）
T’->
ST’,∵,∈SELECT（T’->
ST’）
（a,ST’）
^
a）
^,∵^∈SELECT（S->
^）
（a,^T’）
a）
ST’,∵,∈SELECT（T’->
ST’）
（a,^,ST’）
）
a,∵a∈SELECT（S->
（a,^,aT’）
ε,∵）∈SELECT（T’->
ε）
（a,^,a）
6-3假定对题6-1的文法采用规范归约的自底向上分析，给出符号中（（^）,a）#的移进-归约过程，并指出句柄及归约所采用的产生式（采用表6.2的格式）。
步骤
符号栈
输入符号串
句柄
下一步动作
产生式
#
（（^）,a）#
移进
#（
（^）,a）#
#（（
^）,a）#
#（（^
）,a）#
归约
#（（S
#（（T
#（（T）
a）#
#（S
#（T
#（T,
a）#
#（T,a
）#
#（T,S
T,S
XX文库-让每个人平等地提升自我
#（T）
#S
接受
6-4设有文法G[S]：
S→aAb
A→BdA|B
B→eIε
改造该文法，使其能进行确定的自顶向下分析。
然后对改造后的文法
1写出其递归子程序；
2构造其LL
（1）分析表。
并分别用递归子程序法和LL
（1）分析法分析句子aedb#。
改造该文法，使其能进行确定的自顶向下分析：
用EBNF表示法的（）提取公共左因子：
文法G’[S]：
A→BA’
A’→dA|ε
1写出其递归子程序
FIRST（S）={a}
FIRST（A）={ε,e,d}
FIRST（A’）={d,ε}
FIRST（B）={e,ε}
FOLLOW（S）={#}
FOLLOW（A）={b}
FOLLOW（A’）={b}
FOLLOW（B）={d,b}
aAb）={a}
SELECT（A->
BA’）={e,d,b}
SELECT（A’->
dA）={d}
ε）={b}
SELECT（B->
e）={e}
ε）={d,b}
递归子程序；
voidS（）
if（token==’a’）
gettoken（）;
A（）;
if（token==’b’）
elseerror（）;
elseif（token==’#’）;
/////////////////////////////////////////////////
voidA（）
if（token==’b’||token==’d’||token==’e’）
B（）;
A’（）;
///////////////////////////////////////////
voidA’（）
if（token==’d’）
///////////////////////////////////////
voidB（）
if（token==’e’）
gettoken（）;
elseif（token==’b’||token==’d’）
elseerror（）;
2构造其LL
（1）分析表：
d
e
A
A’
A’→ε
A’→dA
B
B→ε
B→e
用递归子程序法分析句子aedb#：
LL
（1）分析过程：
输入串
所用生成式
aedb#
#bAa
aAb
#bA
edb#
#bA’B
A->
BA’
#bA’e
B->
#bA’
db#
6
#bAd
A’->
dA
7
b#
8
9
ε
10
#b
11
分析完成，输入的字符串是预定文法的句子。
编译技术-王力红，p.149，第7章语法分析
（2）——LR（K）分析方法
习题7
7-1请对文法
S→AS|b
A→SA|a
1构造文法的LR（0）项目集规范族；
2构造相应的SLR分析表；
3对输入串bab写出LR分析过程；
4构造相应的LR
（1）分析表和LALR分析表。
1首先拓广文法：
（1）S’→S
（2）S→AS
（3）S→b
（4）A→SA
（5）A→a
然后用ε-CLOSURE法构造文法的LR（0）项目集规范族：
I0:
S’→.S
S→.AS
S→.b
A→.SA
A→.a
I1:
S’→S.
A→S.A
I2:
S→A.S
升级会员 