编译原理陈意云_课后答案2[1]

编译原理陈意云_课后答案2[1]

ID:5459047

大小:181.00 KB

页数:30页

时间:2017-11-27

编译原理陈意云_课后答案2[1]_第1页
编译原理陈意云_课后答案2[1]_第2页
编译原理陈意云_课后答案2[1]_第3页
编译原理陈意云_课后答案2[1]_第4页
编译原理陈意云_课后答案2[1]_第5页
资源描述:

《编译原理陈意云_课后答案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、T T-

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。