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