编译原理陈意云 课后答案2.ppt

编译原理陈意云_课后答案2编译原理****题课(2)
栾俊
******@.
8/20/2017
8/20/2017
1
******@.

考虑文法 S -> (L)|a L -> L,S|S(a) 建立句子(a,(a,a))和(a,((a,a),(a,a)))的分析树(b) 为(a)的两个句子构造最左推导(c) 为(a)的两个句子构造最右推导(d) 这个文法产生的语言是什么
8/20/2017
2
******@.
(续) - (a,(a,a))
S =>(L)
=>(L,S)
=>(S,S)
=>(a,S)
=>(a,(L))
=>(a,(L,S))
=>(a,(S,S))=>(a,(a,S))
=>(a,(a,a))
S
( L )
L , S
S
a
( L )
L , S
S
a
a
S =>(L)
=>(L,S)
=>(L,(L))
=>(L,(L,S))
=>(L,(L,a))
=>(L,(S,a))
=>(L,(a,a))=>(S,(a,a))
=>(a,(a,a))
8/20/2017
3
******@.
(续) - (a,((a,a),(a,a)))
S
( L )
L , S
S
a
S =>(L)
=>(L,S)
=>(S,S)
=>(a,S)
=>(a,(L))
=>(a,(L,S))
=>(a,(S,S))=>(a,((L),S))
=>(a,((L,S),S))
=>(a,((S,S),S))
=>(a,((a,S),S))
=>(a,((a,a),S))
=>(a,((a,a),(L)))
=>(a,((a,a),(L,S)))
=>(a,((a,a),(S,S)))
=>(a,((a,a),(a,S)))
=>(a,((a,a),(a,a)))
( L )
L , S
( L )
L , S
S
a
a
( L )
L , S
S
a
a
S
S =>(L)
=>(L,S)
=>(L,(L))
=>(L,(L,S))
=>(L,(L,(L)))
=>(L,(L,(L,S)))
=>(L,(L,(L,a)))
=>(L,(L,(S,a)))
=>(L,(L,(a,a)))
=>(L,(S,(a,a)))
=>(L,((L),(a,a)))
=>(L,((L,S),(a,a)))
=>(L,((L,a),(a,a)))
=>(L,((S,a),(a,a)))
=>(L,((a,a),(a,a)))
=>(S,((a,a),(a,a)))
=>(a,((a,a),(a,a)))
8/20/2017
4
******@.
(续)
描述的语言: 括号匹配的串,串中的各项由”,”隔开,项可以是括号匹配的子串或a
8/20/2017
5
******@.

考虑文法 S -> aSbS|bSaS|ε(a) 为句子abab构造两个不同的最左推导,以说明此文法二义(b) 为abab构造对应的最右推导(c) 为abab构造对应的分析树(d) 这个文法产生的语言是什么
8/20/2017
6
******@.
(续)
(1) S=>aSbS=>abS=>abaSbS=>ababS=>abab(2) S=>aSbS=>abSaSbS=>abaSbS=>ababS=>abab
S=>aSbS=>aSb=>abSaSb=> abSab =>abab (2)
S
a S b S
ε
a S b S
ε
ε
S
a S b S
b S a S
ε
ε
ε
(1)
(2)
描述的语言是a,b数目相等的串
8/20/2017
7
******@.

文法 R->R’|’R | RR | R* | (R) | a | b产生字母表(a, b)上所有不含ε的正规式该文法是二义的(a) 证明该文法产生字母表{a,b}上的所有正规式(b) 为该文法写一个等价的非二义文法。(c) 按照上面的两个文法构造ab|b*a的分析树
8/20/2017
8
******@.
(续)
证明该文法产生字母表{a,b}上的所有正规式证明:1)该文法产生的串是字母表{a,b}上的正规式R->a和R->b产生a,b,而a,b是{a,b}上的符号,因此是正规式。若R1,R