编译原理第五章 语法分析课件.ppt

《编译原理第五章 语法分析课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ir(j),r(k)5.4.3LR(0)分析法的扩展LR()分析法的关键技术是句柄识别器的设计问题；如果句柄识别器发生了冲突：此时，LR(0)分析法失效!需要改进句柄识别器的构造方法，于是出现了各种不同的LR()分析法。【注】下面仅通过实例探讨LR(0)分析表的简单扩展问题---称为SLR(1)分析法。ikr(j)x移进/归约冲突归约/归约冲突或【例5.9】G(Z):Z->aAb；A->cd

2、⑴扩展文法，构造句柄识别器：Z`->Z1(0);Z->a2A3b4(1)A->c5d6(2)

3、7(3)G

4、`(Z`):※经确定化(消ε边)：※句柄识别器出现冲突：∵②:{c5,r(3),A3}∴称为移进/归约冲突！看到：{b}∩{c}=；解决办法：求：follow(A)={b}∴若w=c则c5;若w=b则r(3)。※通过查看‘当前单词’，是否可以解决？为此：r(3)0+ZaAbOKr(1)r(2)cr(3)①②③④⑤d⑥⑦-Z`->Z(0)Z->aAb(1)A->cd(2)->(3)SLR(1)分析表br(3)SLR(1)句柄识别器：⑵扩展句柄识别器，构造SLR(1)分析表dZA1504#632c

5、bar(2)d6r(1)Z1A3OKa2r(1)r(1)r(1)r(1)r(2)r(2)r(2)r(2)b4c5r(3)注意与LR(0)分析表的区别！0+ZaAbOKr(1)r(2)c①②③④⑤d⑥-※如此可以解决冲突的文法，称为SLR(1)文法。S`->S1(0)S->A2a3⑴

6、B4c5⑵A->d6⑶;B->d7⑷【例5.10】G(S):S->Aa

7、Bc；A->d;B->d;⑴扩展文法，构造句柄识别器：G`(S`):即若w=a则r(3);若w=c则r(4)。※求：follow(A)={a}；fo

8、llow(B)={c}0+SAacOKr(1)r(4)dr(3)r(2)B①②④⑤⑥③⑦d0+SAacOKr(1),r(4)dr(3)r(2)B①②④⑤⑥③⑥确定化∵:{r⑶,r⑷}∴称为归约/归约冲突！⑥非确定机S`->S1(0)S->A2a3⑴

9、B4c5⑵A->d6⑶;B->d6⑷⑵扩展句柄识别器，构造SLR(1)分析表#AB1504S632dcar(2)r(1)OKA2B4r(2)r(2)r(2)S1d6c5r(4)r(3)r(1)r(1)r(1)a3注意与LR(0)分析表的区别！SLR(1)

10、分析表※通过查看当前单词，解决冲突：0+SAacOKr(1)dr(2)B①②④⑤③,r(4)r(3)⑥⑥-SLR(1)句柄识别器ar⑶r⑷c5.5语法分析方法综合示例G(Z)：Z->dAZ

11、bAcA->aA

12、c

13、ε【例5.11】给定文法如下：Ⅰ.递归子程序法；Ⅱ.LL(1)分析法；※试分别用下述分析法，对给定的符号串进行语法分析：Ⅲ.LR(0)(或SLR（1）)分析法；设给定的符号串为：α=bac∵Z=>bAc=>baAc=>baεc=>bac∴bac是文法G(Z)的一个句子。注G(Z)：Z->dA

14、Z①

15、bAc②A->aA③

16、e④

17、ε⑤Ⅰ.构造递归子程序法：⒈证明G(Z)是LL(1)文法：select(①)=first(dAZ)={d}※求选择集合：select(②)=first(bAc)={b}select(③)=first(aA)={a}select(④)=first(c)={e}select(⑤)=follow(A)={d,b，c}⑴⑵∵两组选择集合⑴,⑵皆不相交，∴G（Z）是LL(1)文法！即递归子程序法可用！！Z子程序主程序⒉构造递归子程序(框图)：G(Z)：Z->dAZ①

18、bAc②

19、A->aA③

20、e④

21、ε⑤入口aNEXT(w)出口遇时nyAA子程序eNEXT(w)yn#NEXT(w)结束nyZ开始err0入口出口derr3NEXT(w)AnnyZAcNEXT(w)yberr2nyNEXT(w)⒊分析过程示意：入口aNEXT(w)出口遇时nyAA子程序eNEXT(w)yn主程序#NEXT(w)结束nyZ开始err0bac#设待分析的符号串：入口出口derr3NEXT(w)AZ子程序nnyZAcNEXT(w)yberr2nyNEXT(w)bbaacccc##▼■Ⅱ.LL(1)分

22、析法：G(Z)：Z->dAZ①

23、bAc②A->aA③

24、e④

25、ε⑤⒈证明G(Z)是LL(1)文法：select(①)=first(dAZ)={d}※求选择集合：select(②)=first(bAc)={b}select(③)=first(aA)={a}select(④)=first(c)={e}select(⑤)=follow(A)={b,c，d}⑴⑵∵两组选择集合⑴,⑵皆不相交，∴G（Z）是LL(1)文法！即LL(1)分析法可用！！2.构造LL(1)分析表：LL(1