平时作业
1 对于下列语言分别写出它们的正规表达式。
(1) 英文字母组成的所有符号串,要求符号串中顺序包含五个元音。
(1) 英文字母组成的所有符号串,要求符号串中顺序包含五个元音。
答: 令Letter表示除这五个元音外的其它字母。
((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*
(2) 英文字母组成的所有符号串,要求符号串中的字母依照词典顺序排列。
答: A*B*....Z*
(3) Σ={0,1}上的含偶数个1的所有串。
答: (0|10*1)*
(4) Σ={0,1}上的含奇数个1的所有串。
答:(0|10*1)*1
(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。
答:设S是符合要求的串,|S|=2k+1 (k≥0)。
则 S→S10|S21,|S1|=2k (k>0),|S2|=2k (k≥0)。
且S1是{0,1}上的串,含有奇数个0和奇数个1。
S2是{0,1}上的串,含有偶数个0和偶数个1。
考虑有一个自动机M1接受S1,那么自动机M1如下:
和L(M1)等价的正规表达式,即S1为:
((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*
类似的考虑有一个自动机M2接受S2,那么自动机M2如下:
和L(M2)等价的正规表达式,即S2为:
((00|11)|(01|10)(00|11)*(01|10))*
因此,S为:
((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|
((00|11)|(01|10)(00|11)*(01|10))*1
(6) 不包含子串011的由0和1组成的符号串的全体。
答:1*|1*0(0|10)*(1|ε)
(7) 由0和1组成的符号串,把它看成二进制数,能被3整除的符号串的全体。
答: 假设w的自动机如下:
对应的正规表达式:(1(01*0)1|0)*
2 给出接受下列在字母表{0,1}上的语言的DFA。
(1) 所有以00结束的符号串的集合。
(2) 所有具有3个0的符号串的集合。
(1) 所有以00结束的符号串的集合。
(2) 所有具有3个0的符号串的集合。
答:
(1) DFA M=({0,1},{q0,q1,q2},q0,{q2},δ) 其中δ定义如下: δ(q0,0)=q1 δ(q0,1)=q0 δ(q1,0)=q2 δ(q1,1)=q0 δ(q2,0)=q2 δ(q2,1)=q0 (2)正则表达式: 1*01*01*01* DFA M=({0,1},{q0,q1,q2,q3},q0,{q3},δ) 其中δ定义如下: δ(q0,0)=q1 δ(q0,1)=q0 δ(q1,0)=q2 δ(q1,1)=q1c语言编译器怎么用文件格式提交作业 δ(q2,0)=q3 δ(q2,1)=q2 δ(q3,1)=q3 |
3 下面是用正规式表示的变量声明:
( int | float ) id (, id )* ;
请改用上下文无关文法表示,也就是写一个上下文无关文法,它和该正规式等价。
答:D T L ;
T int | float
L L, id | id
4 试分析下面给出的if-then-else语句的文法,它的提出原本是为了矫正dangling-else (悬而未决的-else)文法的二义性:
stmt → if expr then stmt
|matched-stmt
matched-stmt→ if expr then matched-stmt else stmt
|other
试说明此文法仍然是二义性的。
stmt → if expr then stmt
|matched-stmt
matched-stmt→ if expr then matched-stmt else stmt
|other
试说明此文法仍然是二义性的。
答:考虑句子if e then if e then other else if e then other else other 它具有如下所示的两种分析树 stmt expr then e if stmt if matched-stmt expr then matched-stmt e other if esle stmt matched-stmt expr then matched-stmt e other esle stmt matched-stmt other stmt matched-stmt if expr then matched-stmt e if esle stmt esle stmt matched-stmt expr then e stmt other expr then matched-stmt e other if matched-stmt other
则上面给出的if-then-else文法仍是二义性的。
5 证明下面文法是SLR(1)文法,并构造其SLR分析表。
E→E+T|T
T→TF|F
F→F*|a|b
E→E+T|T
T→TF|F
F→F*|a|b
答:该文法的拓广文法G'为
(0) E' → E | (1) E → E+T |
(2) E → T | (3) T → TF |
(4) T → F | (5) F → F* |
(6) F → a | (7) F → b |
其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}
I1 = {E'→E·, E→E·+T}I2 = {E→T·, T→T·F, F→·F*, F→·a, F→·b}
I3 = {T→F·, F→F·*} I4 = {F→a·} I5 = {F→b·}
I6 = {E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I7 = {T→TF·, F→F·*} I8 = {F→F*·}
I9 = {E→E+T·, T→T·F, F→·F*, F→·a, F→·b}
求FOLLOW集: FOLLOW(E)={+, $} FOLLOW(T)={+, $, a, b}
FOLLOW(F)={+, $, a, b, *}
构造的SLR分析表如下:
显然,此分析表无多重定义入口,所以此文法是SLR文法。
6 为下面的文法构造LALR(1)分析表
S→E
E→E+T|T
T→(E)|a
E→E+T|T
T→(E)|a
答:其拓广文法G':
(0) S' → S | (1) S → E |
(2) E → E+T | (3) E → T |
(4) T → (E) | (5) T → a |
构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0 = {[S’→·S, $], [S→·E, $], [E→·E+T, $/+], [E→·T, $/+], [T→·(E), $/+], [T→·a, $/+]}
I1 = {[S’→S·, $]} I2 = {[S→E·, $], [E→E·+T, $/+]} I3 = {[E→T·, $/+]}
I4 = {[T→(·E), $/+], [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I5 = {[T→a·, $/+]} I6 = {[E→E+·T, $/+], [T→·(E), $/+], [T→·a, $/+]}
I7 = {[T→(E·), $/+], [E→E·+T, )/+]} I8 = {[E→T·, )/+]}
I9 = {[T→(·E), )/+}, [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I10 = {[T→a·, )/+]} I11 = {[E→E+T·, $/+]} I12 = {[T→(E)·, $/+]}
I13 = {[E→E+·T, )/+], [T→·(E), )/+], [T→·a, )/+]} I14 = {[T→(E·), )/+], [E→E·+T, )/+]}
I15 = {[E→E+T·, )/+]} I16 = {[T→(E)·, )/+]}
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论