编译原理 第05章_算符优先分析法.ppt

《编译原理 第05章_算符优先分析法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、自下而上分析法思想从输入串出发，反复利用产生式进行规范归约，如果最后能得到文法的开始符号，则输入串是合法句子，否则输入串有语法错误。核心寻找句型中的归约串进行归约,用不同的方法寻找归约串，就可获得不同的分析方法1、自下而上分析事例：设文法G为(1)SaAcBe(2)Ab(3)AAb(4)Bd试判断语句abbcde是否是该文法的合法句子？怎样实现归约过程：借鉴LL(1)分析法的体系结构步骤栈内输入串动作0#abbcde#1#abbcde#移进2#abbcde#移进3#aAbcde#归约4#aAbcde#移进5#aAcde#归约6#aAcde#移

2、进7#aAcde#移进8#aAcBe#归约9#aAcBe#移进10#S#归约11识别成功2、自下而上分析法的核心问题：1)存在移进--归约冲突;2)存在归约--归约冲突;核心问题是寻找句型中的归约串进行归约。自下而上分析法一、算符优先分析法：1、算符优先分析法的思想：对于文法G:EE+E

3、E-E

4、E*E

5、E/E

6、(E)

7、i，分析i+i-i*(i+i)规范推导：EE*EE*(E)E*(E+E)E*(E+i)E*(i+i)E+E*(i+i)E+E-E*(i+i)E+E-i*(i+i)E+i-i*(i+i)i+i-i*(i+i)第5章

8、优先分析法逆过程是规范归约另外一种推导：EE-EE-E*EE-E*(E)E-E*(E+E)E-E*(E+i)E-E*(i+i)E-i*(i+i)E+E-i*(i+i)E+i-i*(i+i)i+i-i*(i+i)第5章优先分析法算符优先分析法的基本思想：定义终结符之间的优先关系，借助终结符之间的优先关系确定归约对象，进行自下而上分析。比较相邻的2个算符的优先级2种推导过程对于8+7-5*(3+2)的计算结果2、算符优先分析技术的引进：必须给出文法中两个可能在句子中相继出现的终结符之间的优先关系。(1)相继出现：在句子中若有“…ab…

9、”或“…aQb…”.(a,b∈ＶT,Q∈ＶN),则称a，b相继出现。(2)终结符号对优先关系的存储：优先关系表是一个矩阵M(a,b),a∈ＶT,b∈ＶT,矩阵行数、列数都为

10、Σ

11、+1。如:对于文法G:EE+E

12、E-E

13、E*E

14、E/E

15、(E)

16、i,对应的优先矩阵为：①矩阵元素M(a,b)表示a在前,b在后时,a与b之间的优先关系。②矩阵元素M(a,b)的取值:≮,≯,≡。i+i-i*(i+i)E+E-E对文法E→E+E

17、E-E

18、E*E

19、E/E

20、(E)

21、i+-*/()i#+≯≯≮≮≮≯≮≯-≯≯≮≮≮≯≮≯*≯≯≯≯≮≯≮≯/≯≯≯≯≮≯≮≯(≮≮≮≮

22、≮≡≮)≯≯≯≯≯≯i≯≯≯≯≯≯#≮≮≮≮≮≮如何获得一般的文法的优先分析表？#优先级低于其右部符号源程序中不会出现…)(…的情形如何获得一般的文法的优先分析表？3、优先表的构造方法：算符文法：给定上下文无关文法G=（VN，VT，P，S）中不存在形如A…BC…的产生式，则称之为算符文法(OG—OperatorGrammar)(其中A,B,C∈ＶN)即：如果文法Ｇ中不存在具有相邻非终结符的产生式，则称为算符文法。算符优先文法:设文法G是一个不包含有空串产生式的算符文法,如果该文法中的任何终结符号对a,b之间,在三种关系中最多只有一种成立,则称该文法

23、为算符优先文法。(1)求文法中每个非终结符P的首终结符集合FIRSTVT(P)①定义：FIRSTVT(P)={a

24、P+a…或者P+Qa…,a∈ＶT,P,Q∈ＶN}复习：FIRST(α)={a

25、α*a…，a∈ＶT}②构造FIRSTVT(P)的算法：1)若有产生式Pa…或者PQa…,则a∈FIRSTVT(P)2)若有产生式PQ…,则FIRSTVT(Q)∈FIRSTVT(P)例如：下述文法①S’#S#②SD(R)③RR;P

26、P④PS

27、i⑤Di求其每个非终结符P的FIRSTVT(P)FIRSTVT(S’)={#}FIRSTVT(S)=F

28、IRSTVT(R)=FIRSTVT(P)={(,i}FIRSTVT(D)={i}{(}∪FIRSTVT(D)={(,i}{;}∪FIRSTVT(P)={;,(,i}(2)求文法中每个非终结符P的尾终结符集合LASTVT(P)①定义：LASTVT(P)={a

29、p+…a或者P+…aQ,a∈ＶT,P,Q∈ＶN}复习：FOLLOW(A)={a

30、S*…Aa…，a∈ＶT}②构造LASTVT(P)的算法：1)若有产生式P…a或者P…aQ,则a∈LASTVT(P)2)若有产生式P…Q,则LASTVT(Q)∈LASTVT(P)例如：下述文法①S’#S#②

31、SD(R)③RR;P

32、P④PS

33、i⑤Di求其每个非终结符P的LASTVT(P)LASTVT(S’)=