编译.docx
《编译.docx》由会员分享,可在线阅读,更多相关《编译.docx(25页珍藏版)》请在冰点文库上搜索。
编译
文法和语言
(1)
L(G)={an|n≥0}
解答:
G:
S→aS|ε
L(G)={an|n≥1}
解答:
G:
S→aS|a
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbm|n≥1,m≥1}
解答:
G1:
S→AB
A→aA|a
B→bB|b
G2:
S→aA
A→aA|B
B→bB|b
L(G)={anbm|n≥0,m≥0}
解答:
G1:
S→AB
A→aA|ε
B→bB|ε
G2:
A→aA|B
B→bB|ε
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbmck|n,m,k≥0}
解答:
G:
S→aS|B
B→bB|C
C→cC|ε
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbn|n≥0}
解答:
G:
S→aSb|ε
L(G)={anbn|n≥1}
解答:
G:
S→aSb|ab
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anban|n≥0}
解答:
G:
S→aSa|b
L(G)={anban|n≥1}
解答:
G1:
S→aSa|aba
G2:
S→aAa
A→aAa|b
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbmcm|n≥0,m≥1}
解答:
G[S]:
S→AB
A→aA|ε
B→bBc|bc
L(G)={anbmcm|n≥1,m≥0}
解答:
G1[S]:
S→AB
A→aA|a
B→bBc|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbnambm|n≥0,m≥0}
解答:
G2:
S→AB
A→aAb|ε
B→aBb|ε
G1:
S→AA
A→aAb|ε
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={1n0m1m0n|n,m≥0}
解答:
G:
S→1S0|A
A→0A1|ε
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={WaWr|W∈{0|a}*,Wr表示W的逆序}
解答:
G:
S→0S0
S→aSa
S→a
文法和语言
(2)
L(G)={an|n≥1,n为奇数}
解答:
G:
S→aaS|a
L(G)={an|n≥0,n为非负偶数}
解答:
G:
S→aaS|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbn|n≥1,n为奇数}
解答:
G:
S→aaSbb|ab
L(G)={anbn|n≥0,n为非负偶数}
解答:
G:
S→aaSbb|
L(G)={ambncn|m为奇数,n为非负偶数}
解答:
G:
S→AB
A→aaA|a
B→bbBcc|
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={ambn|n>m≥1}
解答1:
G:
S→AB
A→aAb|ab
B→bB|b
解答2:
G:
S→Sb|Ab
A→aAb|ab
提示:
b的个数比a多ambn=ambmbn-m(m≥1,n-m≥1)
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbm|2n>m≥n≥1}
解答:
G:
S→aSb|ab
S→aSbb
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbm|2n≥m≥n≥1}
解答:
G:
S→aSb|ab
S→aSbb|abb
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
L(G)={anbm|2n>m>n≥1}
解答:
G:
S→aSb|aabbb
S→aSbb
词法分析–正规式/自动机自测题及解答
一、单项选择题
1.文法G产生的___C_____的全体是该文法描述的语言。
【A】句型【B】终结符号【C】句子【D】非终结符号
2.确定的有限自动机能识别____B_____
【A】上下文有关文法产生的语言【B】正规语言
【C】上下文无关文法产生的语言【D】以上三种语言都不能识别
二、简答题
1.Σ={a,b},正规式(a|b)a(a|b)*a表示的语言有什么特点。
【解答】第2个符号是a,且以a结尾
2.Σ={a,b},正规式(ba|a)*表示的语言有什么特点。
【解答】每个b都有a跟在后面
3.设L{0,1}*,L中的符号串以‘0’开头并且以‘1’结尾;
(1)写出定义集合L的正规式。
(2)构造识别集合L的DFA。
【解答】定义集合L的正规式:
0(0|1)*1
4.设L{a,b,c}*,L是满足下述条件的符号串构成的语言:
(1)若出现a,则其后至少紧跟两个c;
(2)若出现b,则其后至少紧跟一个c。
试写出定义语言L的正规式
【解答】(acc|bc|c)*
文法和语言自测题及解答
一、单项选择题
1.给定文法G:
A→bA|cc,则以下符号串中,是文法句子的是____D_____
【A】bcbc【B】bcbcc【C】bccbcc【D】bbbcc
2.____B_____正规文法G能产生语言L(G)={anbn|n≥1}
【A】存在一个【B】不存在任何【C】可能存在也可能不存在【D】bbbcc
二、简答题
1.写一个文法G,使得L(G)={anbman|n,m≥0}
【解答】G:
S→aSa|B
B→bB|ε
2.写一个三型文法G,使得L(G)={anbmck|n,m,k≥1}
【解答】G:
S→aS|aB
B→bB|bC
C→cC|c
3.描述由下列文法所产生的语言的特点
G:
S→SS|1A0
A→1A0|ε
【解答】
该语言的特点是产生的句子中,0和1的个数相同,
并且若干相邻的1后面必然紧跟数量相同的连续的0
4.化简以下文法:
G:
S→aS|W|U
U→a
V→bV|ac
W→aW
【解答】化简后的文法G’:
S→aS|U
U→a
5.证明下述文法G是二义的。
G:
S→Ac|aB
A→ab
B→bc
【解答】请尝试画出句子abc的两棵不同语法树
6.证明下述文法G是二义的。
G:
S→S(S)S|ε
【解答】请尝试画出句子()()的两棵不同语法树
文法、正规式、自动机、正规语言
课上练习
1.构造DFA,可以识别a,b,c组成的串,但是所含a的个数不超过1.
(即可以含一个a或不含a)
2.构造DFA,可以识别a,b,c组成的串,串中只含一个a
3.构造DFA,可以识别a,b,c组成的串,串中至少含一个a
4.构造识别标识符的自动机l(l|d)*
5.={a,b},不以a开头,但以aa结尾的字符串集合的正规式和自动机
b(a|b)*aa
6.构造自动机,识别a,b,c组成的串,每个a后面至少紧随两个b,
并写出等价的正规式
(b|abb)*
课下练习1
1.给语言L={an|n≥0},写3型文法,并构造自动机
可以构造出L的自动机如下:
再将自动机转换成3型文法,
G:
SaS|ε
2.给语言L={anbm|n,m≥1},写3型文法,并构造自动机
可以构造出L的自动机如下:
再将自动机转换成3型文法,
G:
S→aA
A→aA|bB
B→bB|
3.构造自动机L={a2n+1b2ma2p+1|n≥0,m≥1,p≥0}
4.给语言L(G)={anbmck|n,m,k≥0},写3型文法,并构造自动机
a*b*c*
G:
S→aS|B
B→bB|C
C→cC|ε
将DFA1和DFA2确定化最小化,得到结果相同:
课下练习2
5.构造自动机,识别能被3整除的二进制数
状态0:
被3整除
状态1:
被3除余1
状态2:
被3除余2
6.构造自动机,识别含奇数个0且奇数个1的二进制数串
S:
偶数个0,偶数个1
A:
奇数个0,偶数个1
B:
奇数个0,奇数个1
C:
偶数个0,奇数个1
7.构造文法,产生含有偶数个1的二进制数串,={0,1}
解法一:
G:
S0S|1A|
A0A|1S
解法二:
S:
偶数个0,偶数个1
A:
奇数个0,偶数个1
B:
奇数个0,奇数个1
C:
偶数个0,奇数个1
确定化,最小化,则得到解法一中的DFA
单元测试2
8.构造自动机,识别满足以下条件的符号串:
至少含有两个1,又在任何两个1之间有偶数个0
9.写出下图所示自动机所描述的语言
100*|100*11*0|111*0
化简得:
10*1*0
L={10m1n0|m≥0,n≥0}
10.证明题:
正规集的子集不一定是正规集
证明如下:
a*b*是正规集,L1={anbn|n≥0}是它的子集,但是L1不是正规集,
因为找不到一个3型文法描述L1,即只能用2型文法描述L1
G:
SaSb|
语法分析–自下而上分析自测题与解答
一、简答题
1.为什么LR
(1)分析器的分析能力要强于SLR
(1)分析器?
2.同心集的合并是否会产生新的移进-归约冲突,请说明原因。
二、综合题
1.文法G:
S→SaS|ε
证明文法G是否为下列文法,并说明理由。
(1)LL
(1)文法
(2)SLR
(1)文法
(3)LR
(1)文法
【解答】
存在句型SaSaS对应两棵不同语法树,文法G是二义文法,
所以文法G不是LL
(1)文法,也不是任何LR类文法。
(1)LL
(1)判别
FIRST集
FOLLOW集
S
a,ε
#,a
SELECT集
S→SaS
FIRST(SaS)
a
S→ε
FOLLOW(S)
#,a
(2)SLR判别
拓广文法G’:
(0)S’→S
(1)S→SaS
(2)S→ε
FOLLOW(S)∩{a}={#,a}∩{a}={a}≠Φ
I1,I3中的冲突无法用SLR方法解决,所以文法G不是SLR文法
(3)LR判别
I1,I3中的冲突无法用LR方法解决,所以文法G不是LR文法
2.写出文法G的LR
(1)项目集规范族中的I0,I1,I2,I3,I4,I5
G:
S→S;B|B
B→BaA|A
A→b(S)|a
【解答】
3.写出文法G的LR
(1)项目集规范族中的I0
G:
S→S;M|M
M→MbD|D
D→D(S)|ε
【解答】
语法分析–自下而上分析自测题与解答
一、简答题
1.什么是活前缀?
为什么引入活前缀这个概念?
2.简述自下而上语法分析过程中面临的问题是什么?
二、综合题
1.文法G及其LR分析表如下,请给出对串baba#的分析过程。
G:
(1)S→DbB
(2)D→d
(3)D→ε
(4)B→a
(5)B→Bba
(6)B→ε
状态
ACTION
GOTO
b
d
a
#
S
B
D
0
r3
S3
1
2
1
acc
2
S4
3
r2
4
r6
S5
r6
6
5
r4
6
S7
r1
7
S8
8
r5
r5
2.已知文法G:
A→aABe|Ba
B→dB|ε
(1)构造LL
(1)分析表,并判断该文法是否为LL
(1)文法?
(2)构造LR(0)项目集规范族,并判断该文法是否为LR(0)文法?
(3)按照SLR
(1)方法构造分析表,并判断该文法是否为SLR
(1)文法?
【解答】
(1)LL
(1)判别--不是LL
(1)文法
可推出ε
FIRST集
FOLLOW集
A
N
a,FIRST(B)/{ε},a
a,d
#,FIRST(Be)/{ε}
#,d,e
B
Y
d,ε
d,ε
e,a
e,a
SELECT集
A→aABe
a
a
A→Ba
FIRST(Ba)
d,a
B→dB
d
d
B→ε
FOLLOW(B)
e,a
a
e
d
#
A
→aABe
→Ba
→Ba
B
B→ε
B→ε
B→dB
(2)构造LR(0)项目集规范族
拓广文法G’:
(0)S’→A
(1)A→aABe
(2)A→Ba(3)B→dB(4)B→ε
存在冲突,不是LR(0)文法。
(3)构造SLR分析表FOLLOW(B)={e,a}FOLLOW(A)={#,d,e}
Action
Goto
a
d
e
#
A
B
0
S2/r4
S4
r4
1
3
1
Acc
2
S2/r4
S4
r4
5
3
3
S6
4
r4
S4
r4
7
5
r4
S4
r4
8
6
r2
r2
r2
7
r3
r3
8
S9
9
r1
r1
r1
I0,I2:
FOLLOW(B)∩{a,d}={e,a}∩{a,d}={a}≠Φ
无法用FOLLOW集解决冲突,所以不是SLR文法。
或者SLR分析表含多重定义入口,所以不是SLR文法。
语法分析–自上而下分析自测题及解答
一、简答题
1.简述语法分析的任务。
2.简述自上而下语法分析过程中面临的问题是什么?
【解答】参考教材和课件中的叙述
二、综合题
1.已知文法G:
A→aABl|a
B→Bb|d
(1).试写出与文法G等价的LL
(1)文法G'。
(2).构造G'的预测分析表。
(3).对输入串aade#进行LL
(1)分析。
【解答】
(1)G':
A→aT
T→ABl|ε
B→dB'
预测分析表
B'→bB'|ε
(2)
FIRST集
FOLLOW集
A
a
#,d
T
a,ε
#,d
B
d
l
B'
b,ε
l
a
l
d
b
#
A
A→aT
T
T→ABl
T→ε
T→ε
B
B→dB'
B'
B'→ε
B'→bB'
(3)预测分析过程略……
2.给出定义语言L={1na0n1ma0m|n≥1,m≥0}的LL
(1)文法G。
并说明G为LL
(1)文法的理由。
【解答】
G:
S→AB
A→1A0|1a0
B→1B0|a
文法G存在左公因子,所以不是LL
(1)文法,可进行变换提取左公因子,得到G'
G':
S→AB
A→1C
C→A0|a0
B→1B0|a
文法G'中不含空产生式,所以只需求出FIRST集合进行LL
(1)判别.
FIRST(S)={1}
FIRST(A)={1}
FIRST(C)={1,a}
FIRST(D)={1,a}
构造G'的预测分析表,不含多重定义入口,所以G'是LL
(1)文法。
(也可以按照LL
(1)判别条件进行判别)
词法分析自测题及解答
一、判断对错
【对】1.对任何正规表达式,都存在一个等价的NFA。
【错】2.存在一个正规表达式,无法找到与其等价的DFA。
【错】3.DFA的状态转换图中包含有限个状态,其中最多有一个初态,最多有一个终态。
二、综合题
1.构造自动机,识别含奇数个0且偶数个1的二进制数串。
【解答】
S:
偶数个0,偶数个1
A:
奇数个0,偶数个1
B:
奇数个0,奇数个1
C:
偶数个0,奇数个1
2.已知正规式b(a|b)*bab,完成以下题目:
(1)试构造等价的NFA,并将其确定化、最小化。
(2)试构造等价的正规文法。
【解答】
确定化:
a
b
0:
A
B1
1:
B
B1
B,C2
2:
B,C
B,D3
B,C2
3:
B,D
B1
B,C,E4
4:
B,C,E
B,D3
B,C2
确定化:
已经最小化考试时还需要画出状态转换图,此处略……
(2).按教材中自动机到正规文法的转换规则写出即可。
(p52)
3.
已知文法G,完成以下题目:
G:
S→dAB
A→aA|a
B→Bb|ε
(1)文法G是否为正规文法?
(2)文法G产生的语言是什么?
(3)写出与文法G等价的正规文法(右线性文法)。
【解答】
(1).不是
(2).L(G)={danbm|n≥1,m≥0}
(3).G':
S→dA
A→aA|aB|a
B→Bb|b
G'':
S→dA
A→aA|aB
B→Bb|ε
以上两个文法都正确
词法分析-自动机自测题及解答
1.将下图所示自动机确定化
【解答】
a
b
c
S:
0,1,2,3
S:
0,1,2,3
A:
1,3
B:
2,3
A:
1,3
A:
1,3
B:
2,3
B:
2,3
a
b
c
S
S
A
B
A
A
B
B
2.将文法G转换为等价的自动机
G:
S→0S|1S|1A|0B
A→1C|1
B→0C|0
C→0C|1C|0|1
【解答】
3.写出下图所示自动机所描述的语言
(可以用正规式表示,也可以写成集合形式,也可用文字说明)
【解答】
100*|100*11*0|111*0
化简得:
10*1*0
L={10m1n0|m≥0,n≥0}
4.构造自动机,识别满足以下条件的符号串:
至少含有两个1,又在任何两个1之间有偶数个0
【解答】
5.将下图所示自动机最小化
【解答】
Π0:
{0,1,2,3,5}{4,6,7}
Π1:
{0,1,3}{2,5}{4,6,7}
Π2:
{0,1}{3}{2,5}{4,7}{6}