编译原理第4章 语法分析(自下而上分析)ppt课件.ppt

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

1、第四章语法分析1§4.6语法分析——自下而上分析一、基本思想：从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串中的相应子串，逐步归约成文法开始符号的一种方法。如果从语法树的角度看，自下而上分析的过程是输入符号串作为末端结点符号串，向着根结点的方向往上构造语法树，使识别符号正好是该语法树的根结点。2二、移进—归约法自下而上分析法的基本实现方法是移进—归约法。移进—归约法：从左到右把输入串的符号一一移进符号栈里，一旦发现栈顶形成一个可归约串时，就把这个串用相应的归约符号（在规范归约的情况下用相应

2、产生式的左部符号）代替。重复这个过程，直至最终形成如下格局：符号栈输入串#S#这种格局表示分析成功；若达不到这种格局，意味着输入串含有语法错误。3例：设文法G[S]:S→aAcBeA→b

3、AbB→d问abbcde是不是该文法的句子？步骤符号栈输入流动作0#abbcde#1#abbcde#移进2#abbcde#移进3#aAbcde#归约，用A→b4#aAbcde#移进5#aAcde#归约，用A→Ab6#aAcde#移进7#aAcde#移进8#aAcBe#归约，用B→d9#aAcBe#移进10#S#归约，用S→a

4、AcBe11#S#成功SaAcBeAbdb4三、关键问题1精确定义可归约串：不同的定义形式形成不同的归约法。在规范归约、LR分析法中，可归约串是句柄在算符优先分析法中，可归约串是最左素短语。2如何识别可归约串：=>不同的分析法LR分析法中：历史，现实，展望。算符优先分析法中：符号之间的优先关系。5§4.7算符优先分析法算符优先分析法是Floyd在1963年首先提出来的，Greis在1971年将它形式化。这是一种古典而又实用的方法，用这种方法分析程序设计语言中的各类表达式尤为有效。不少编译程序使用这种方法分析表

5、达式，而使用其它方法分析其余语言部分。这种方法简单直观，特别便于手工实现。62两个相邻终结符a,b之间的优先关系：aba的优先级高于b1算符优先分析法：就是仿照算术表达式的四则运算过程而设计的一种分析方法。这种方法首先规定运算符之间（终结符号之间）的优先关系和结合性质，然后，利用这种关系用比较相邻运算符之间的优先顺序来确定句型的可归约串并进行归约。一、概述...7注意：优先关系与符号出现的左右顺序有关数学中：a>b可以bb不能b

6、E

7、*E

8、(E)

9、i(<+但是+<(3逻辑结构图：....优先关系表算符优先分析程序符号栈产生式文法词法分析后单词串语法树8二、算符优先文法和优先表的构造1算符优先文法（OPG文法）（1）算符文法（OG文法）：设有一文法G，若G中没有形如S→…QR…产生式，（S,Q,R∈VN）则称文法G为算符文法。（2）定义优先关系：设文法G是一个OG文法，令a,b是任意两个终结符号，P,G,R是非终结符号，定义：①a=b当且仅当文法G中含有形如P→…ab…或P→…aQb…规则。②a

10、，其中：R=>b…或R=>Qb…。③a>b当且仅当文法G中含有形如P→…Rb…的规则，其中：R=>…a或R=>…aQ。两个非终结符相邻...9（3）OPG文法：设有一个OG文法，如果在任意两个终结符号之间，在>、<和=中最多只有一种优先关系成立，则该OG文法称为OPG文法。例如：表达式文法：E→E+E

11、E*E

12、(E)

13、iE→…+E且E=>E*…有+<*又E→E*…且E=>…+E有+>*∴它是OG文法，但它不是OPG文法。改写：E→E+T

14、TT→T*F

15、FF→(E)

16、i是OPG文法.....102优先关系表的构

17、造方法（1）为每一个非终结符P定义二个集合：FirstVT(P)={a

18、P=>a…或P=>Qa…,a∈VT,Q∈VN}非终结符P的首终结符的集合LastVT(P)={a

19、P=>…a或P=>…aQ,a∈VT,Q∈VN}非终结符P的尾终结符的集合例如：表达式文法：E→E+T

20、TT→T*F

21、FF→(E)

22、i++++11（2）构造优先关系表的算法：输入：算符文法G输出：关于G的优先关系表方法：①为每一个非终结符P计算FirstVT(P)和LastVT(P)②执行算法：for每个产生式P→x1x2…xndofori

23、=1ton-1dobeginifxi和xi-1都为终结符then置xi=xi-1;ifi≤n-2且xi和xi+2都为VT,但xi+1为VNthen置xi=xi+2;ifxi为VT而xi+1为VNthenforFirstVT(xi+1)中的每一个bdo置xixi+1;end;....12例如：E→E+T

24、TT→