资源描述:
《编译原理陈意云_课后答案2[1]》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、编译原理习题课(2)栾俊luanj@mail.ustc.edu.cn6/12/20213.1考虑文法S->(L)
2、aL->L,S
3、S(a)建立句子(a,(a,a))和(a,((a,a),(a,a)))的分析树(b)为(a)的两个句子构造最左推导(c)为(a)的两个句子构造最右推导(d)这个文法产生的语言是什么6/12/20212luanj@mail.ustc.edu.cn3.1(续)-(a,(a,a))S=>(L)=>(L,S)=>(S,S)=>(a,S)=>(a,(L))=>(a,(L,S))=>(a,(S,S))=>(a,(
4、a,S))=>(a,(a,a))S(L)L,SSa(L)L,SSaaS=>(L)=>(L,S)=>(L,(L))=>(L,(L,S))=>(L,(L,a))=>(L,(S,a))=>(L,(a,a))=>(S,(a,a))=>(a,(a,a))6/12/20213luanj@mail.ustc.edu.cn3.1(续)-(a,((a,a),(a,a)))S(L)L,SSaS=>(L)=>(L,S)=>(S,S)=>(a,S)=>(a,(L))=>(a,(L,S))=>(a,(S,S))=>(a,((L),S))=>(a,((L,
5、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,SSaa(L)L,SSaaSS=>(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,(
6、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)))6/12/20214luanj@mail.ustc.edu.cn3.1(续)描述的语言:括号匹配的串,串中的各项由”,”隔开,项可以是括号匹配的子串或a6/12/20215luanj@mail.ustc.edu.cn3.2考虑文法S
7、->aSbS
8、bSaS
9、ε(a)为句子abab构造两个不同的最左推导,以说明此文法二义(b)为abab构造对应的最右推导(c)为abab构造对应的分析树(d)这个文法产生的语言是什么6/12/20216luanj@mail.ustc.edu.cn3.2(续)(1)S=>aSbS=>abS=>abaSbS=>ababS=>abab(2)S=>aSbS=>abSaSbS=>abaSbS=>ababS=>ababS=>aSbS=>aSb=>abSaSb=>abSab=>abab(2)SaSbSεaSbSεεSaSbSbSaSεεε(1)(
10、2)描述的语言是a,b数目相等的串6/12/20217luanj@mail.ustc.edu.cn3.4文法R->R’
11、’R
12、RR
13、R*
14、(R)
15、a
16、b产生字母表(a,b)上所有不含ε的正规式该文法是二义的(a)证明该文法产生字母表{a,b}上的所有正规式(b)为该文法写一个等价的非二义文法。(c)按照上面的两个文法构造ab
17、b*a的分析树6/12/20218luanj@mail.ustc.edu.cn3.4(续)证明该文法产生字母表{a,b}上的所有正规式证明:1)该文法产生的串是字母表{a,b}上的正规式R->a和R->b产
18、生a,b,而a,b是{a,b}上的符号,因此是正规式。若R1,R2产生正规式α,β则:R->R1R2产生正规式αβR->R1
19、R2产生正规式α
20、βR->R1*产生正规式α*R->(R1)产生正规式(α)2)字母表{a,b}上的所有正规式都可由此文法产生字母表{a,b}上的任一正规式(其中α,β为正规式)必为以下形式之一:αβ,可由R->RR产生α
21、β,可由R->R
22、R产生α*,可由R->R*产生(α),可由R->(R)产生a,可由R->a产生b,可由R->b产生因而,该文法产生字母表{a,b}上的所有正规式6/12/20219l
23、uanj@mail.ustc.edu.cn3.4(续)该文法没有体现运算符
24、、*、()、并置的优先级,因而是二义的。R=>R
25、R=>a
26、R=>a
27、R*=>a
28、b*R=>R*=>R
29、R*=>a
30、R*=>a
31、b*E->E’
32、’T
33、TT-