资源描述：
《编译原理第五章 语法分析_习题课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、G(S)：S->a
2、∧
3、(T)T->T,S
4、S【习题:】给定文法如下：Ⅲ.递归子程序法；IV.LL(1)分析法；※试分别用下述分析法，对给定的符号串进行语法分析：V.LR(0)(或SLR（1）)分析法；设给定的符号串为：α=((a,∧),a)VI.简单优先（或算符优先）分析法；Ⅱ.找出这个句子的短语，简单短语，句柄；Ⅰ.证明符号串是文法的一个合法的句子；第5章习题解答:∴((a,∧),a)是文法的一个句子。S=>(T)=>(T,S)=>(S,S)=>((T),S)=>((T,S),S)=>((S,S),S)=>((a,S),S)=>((a,∧)
5、,S=>((a,∧),a)Ⅰ.证明符号串是文法的一个合法的句子；G(S)：S->a
6、∧
7、(T)T->T,S
8、SⅡ.找出这个句子的短语，简单短语，句柄；S(T)T,SS(T)T,SSa∧a短语：((a,∧),a)；(a,∧),a；(a,∧)；a,∧；a；∧；简单短语：a；∧；句柄：aG(S)：S->a①
9、∧②
10、(T)③T->T,S④
11、S⑤Ⅲ.构造递归子程序法：⒈证明G(S)是LL(1)文法：select(①)=first(a)={a}※求选择集合：select(②)=first(∧)={∧}select(③)=first((T))={(}sele
12、ct(④)=first(T,S)={a,(,∧}select(⑤)=first(S)={a,(,∧}⑴⑵∵选择集合⑴不相交,⑵相交，∴G（S）不是LL(1)文法！必须进行文法变换！G’(S)：S->a①
13、∧②
14、(T)③T->S{,S}④变换后的文法G’(S)S子程序主程序⒉构造递归子程序(框图)：入口,NEXT(w)出口nyST子程序(NEXT(w)yn#NEXT(w)结束nyS开始err0入口出口aerr2NEXT(w)nnyT)NEXT(w)y∧nyNEXT(w)G’(S)：S->a①
15、∧②
16、(T)③T->S{,S}④Serr1select
17、(⑥)=follow(T’)={)}IV.LL(1)分析法：⒈证明G’’(S)是LL(1)文法：select(①)=first(a)={a}※求选择集合：select(②)=first(∧)={∧}select(③)=first((T))={(}select(④)=first(ST’)={a,∧,(}select(⑤)=first(,ST’)={,}⑴⑵∵两组选择集合⑴,⑵皆不相交，∴G’’（S）是LL(1)文法！即LL(1)分析法可用！！G(S)：S->a①
18、∧②
19、(T)③T->T,S④
20、S⑤G’’(S)：S->a①
21、∧②
22、(T)③T->ST
23、’④T’->,ST’⑤
24、ε⑥变换后的文法G’’(S)2.构造LL(1)分析表：LL(1)分析表：※带有选择集合的文法：⑤①④⑥③②G’’(S)：S->a{a}①
25、∧{∧}②
26、(T){(}③T->ST’{a,∧,(}④T’->,ST’{,}⑤
27、ε{)}⑥a∧(),#STT’④④V.LR(0)(SLR(1))分析法：⒈扩展文法，编码：G(S)：S`->S10S->a2①
28、∧3②
29、(4T5)6③T->T7,8S9④
30、S10⑤⒉构造可规约前缀图：0+S①-OKa②-r(1)③∧-r(2)(④T⑤)⑥-r(3)⑦T,⑧S⑨-r(4)S10-r(5)a∧(
31、a∧(是一个非确定有限自动机，需要转换为确定机！V.LR(0)(SLR(1))分析法：G(S)：S`->S10S->a2①
32、∧3②
33、(4T5)6③T->T7,8S9④
34、S10⑤3.构造确定的有限自动机的变换表：10#S15,7049），6832T（∧ar(5)r(5)r(5)r(5)r(5)9101OK43242r(4)r(4)r(2)r(1)r(3)r(2)r⑴r(3)r(3)4325,7r(2)r(2)r(2)r(1)r⑴r(1)386r(4)r(4)r(4)r(3)r(3)V.LR(0)(SLR(1))分析法：G(S)：S`->S10S-
35、>a2①
36、∧3②
37、(4T5)6③T->T5,8S9④
38、S10⑤4.构造确定的可规约前缀图：0+S①-OKa②-r(1)③∧-r(2)(④T⑤)⑥-r(3),⑧S⑨-r(4)S10-r(5)a∧(a∧(VI.简单优先（算符优先）分析法G(S)：S->a①
39、∧②
40、(T)③T->T,S④
41、S⑤⒈证明G(S)是简单优先文法：※求FIRSTVT和LASTVT：STFIRSTVTLASTVTa,∧,(a,∧,)T,S,a,∧,(S,a,∧,)VI.简单优先（算符优先）分析法G(S)：S->a
42、∧
43、(T)T->T,S
44、S※求简单优先关系：STFIRSTVTL
45、ASTVTa,∧,(a,∧,)T,S,a,∧,(S,a,∧,)STa∧(),STa∧(),∵优先关系不唯一；∴G(S)文法不是简单优先文法！====<
