admin 管理员组文章数量: 1086019
2024年4月26日发(作者：mysql学习步骤)
第三章 词法分析及词法分析程序
正规表达式相关作业
3．1画出用来识别如下三个关键字的状态转移图。
STEP STRING SWITCH
解：
3．2试构造一右线性文法（右递归），使得它与如下的文法等价
S→AB
A→UT
U→a|aU
T→b|bT
B→c|cB
并根据所得的右线性文法，构造出相应的状态转换图。
解：根据文法知其产生的语言是
L={a
m
b
n
c
i
| m,n,i≧1}
可以构造如下的文法VN={S,A,B,C}, VT={a,b,c}
P={ S →aA, A→aA, A→bB, B→bB, B→cC, C→cC, C→c}
其状态转换图如下:
3．3对于下面所给的文法：
G1=({S,A,B,C,D}, {a,b,c,d},P1,S)
P1由如下产生式组成：
S→aA S→B A→abS
A→bB B→b B→cC
C→D D→d D→bB
以及G2=({S,A,B,C,D},{a,b,c,d},P2,S)
P2由如下产生式组成：
S→Aa S→B A→Cc
A→Bb B→Bb B→a
C→D C→Bab D→d
(1) 试分别对G1和G2构造相应的状态转换图 (提示：对于右线性文法，可将形如C→D的
产生式视为C→εD；而对左线性文法，则可将它视为C→Dε)。
(2) 对于G1，构造一等价的左线性文法G1′；对于G2构造一等价的右线性文法G2′。
(3) 对于G1和G1′，分别给出如下符号串的推导序列：
abbaababbbcdcbb
对于G2和G2′分别给出如下符号串的推导序列：
aabaaabcadca
(4) 试给出若干个不能由G1或G2产生的符号串，并验证它们同样不能用G1′和G2′产生。
解：（1）G1的状态转换图：
ab
G2的状态转换图：
(2) G1等价的左线性文法：
S→Bb,S→Dd,D→C,B→Db,C→Bc,B→Ab,B→ε,A→a
G2等价的右线性文法：
S→dD,S→aB,D→C,B→abC,B→bB,B→bA,B→ε,C→cA,A→a
（3）对G1文法,abb的推导序列是：
S=>aA=>abB=>abb
对G1’文法，abb的推导序列是：
S=>Bb=>Abb=>abb
对G2文法，aabca的推导序列是：
S=>Aa=>Cca=>Babca=>aabca
对G2’文法，aabca的推导序列是：
S=>aB=>aabC=>aabcA=>aabca
（4）对串acbd来说，G1,G1’文法都不能产生。
3．4设r,s等为任意的正规式，试证明下列的关系式成立：
(1) r*=(ε|r)*=ε|rr*=(r*)*
(2) (rs)*r=r(sr)*
(3) (r|s)*=(r*s*)*=(r*|s*)*
解：(1) r*表示的正规式集是{ε,r,rr,rrr,…}
(ε|r)*表示的正规式集是{ε, εε,…}∪{r,rr,rrr,…}={ε,r,rr,rrr,…}
ε|rr*表示的正规式集是{ε,r,rr,rrr,…}
(r*)*=r*={ε,r,rr,rrr,…}
所以四者是等价的。
(2)（rs）*r表示的正规式集是{ε,rs,rsrs,rsrsrs,…}r ={r,rsr,rsrsr,rsrsrsr,…}
r(sr)* 表示的正规式集是r{ε,sr,srsr,srsrsr,…} ={ r,rsr,rsrsr,rsrsrsr,…}
所以两者等价。
（3）类同上
3．5设有如下的文法G［〈标号说明〉］：
〈标号说明〉→′LABEL′〈标号表〉
〈标号表〉→d〈标号段〉
〈标号段〉→d〈标号段〉|,〈标号〉|；
〈标号〉→d〈标号段〉
其中′LABEL′,′d′,′,′,′;′等为终结符号。
试求出描述此文法所产生语言的正规式；
解：识别此语言的正规式是S=’LABEL’d(d|,d)*;
版权声明：本文标题：第三章词法分析及词法分析程序 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1714102590a665781.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论