编译原理课件

《编译原理课件》由会员分享，可在线阅读，更多相关《编译原理课件（175页珍藏版）》请在装配图网上搜索。

1、编译原理编译原理PPT课件课件编译原理第五章第五章 语法分析语法分析自下而上分析自下而上分析网上教学系统网上教学系统:070606302:编译原理编译原理http:/ 语法分析语法分析自下而上分析自下而上分析n自上而下分析法自上而下分析法(Top-down)(Top-down)n自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)编译原理编译原理PPT课件课件n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)自上而下分析法自上而下分析法(Top-down)(Top-down)n基本思想：它从文法的开始符号出发，反复基本

2、思想：它从文法的开始符号出发，反复使用各种产生式，寻找使用各种产生式，寻找 匹配匹配 的的推导推导。n递归下降分析法：对每一语法变量递归下降分析法：对每一语法变量(非终结非终结符符)构造一个相应的子程序，每个子程序识构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。馈和联合作用实现对输入串的识别。n预测分析程序预测分析程序F优点：直观、简单和宜于手工实现。优点：直观、简单和宜于手工实现。编译原理编译原理PPT课件课件n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(B

3、ottom-up)n基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归归约约”，直到文法的开始符号。即从树末端开，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。产生式规则，把产生式的右部替换成左部符号。n算符优先分析法：按照算符的优先关系和结合算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。性质进行语法分析。适合分析表达式。nLRLR分析法：规范归约分析法：规范归约编译原理编译原理PPT课件课件G(E)：E i|E+E|E-E|E*E|E/E|

4、(E)i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE编译原理编译原理PPT课件课件5.1.1 5.1.1 归约归约n采用采用“移进归约移进归约”思想进行自下而上分析。思想进行自下而上分析。n基本思想：用一个寄存符号的先进后出栈，基本思想：用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这形成某个产生式的候选式时，即把栈顶的这一部分替换成一部分替换成(归约归约为为)该产生式的左部符该产生式的左部符号。号。编译原理编译原理PPT课件课件n例：例：设文法设文法G(S)：(1)S a

5、AcBe (2)A b (3)A Ab (4)B d试对试对abbcdeabbcde进行进行“移进归约移进归约”分析。分析。a bbcdeba bcdeAa bcdebAa cdeAa cdecAa dedcAa eabbcdeeBcAa S BcAa e编译原理编译原理PPT课件课件步步骤骤:1 12 23 34 45 56 67 78 89 91 10 0动动作作:进进a a进进b b 归归(2 2)进进b b 归归(3 3)进进c c进进d d 归归(4 4)进进e e 归归(1 1)e ed dB BB Bb bc cc cc cc cb bA AA AA AA AA AA AA Aa

6、 aa aa aa aa aa aa aa aa aS S编译原理编译原理PPT课件课件bdbaceSABA分析树和语法树不一定一致。分析树和语法树不一定一致。自下而上分析过程：边输入单词符号，边自下而上分析过程：边输入单词符号，边归约。归约。核心问题：识别可归约串核心问题：识别可归约串编译原理编译原理PPT课件课件5.1.2 5.1.2 规范归约规范归约n定义：令定义：令G G是一个文法，是一个文法，S S是文法的开始符是文法的开始符号，假定号，假定是文法是文法G G的一个句型，如果有的一个句型，如果有 且且 AS*A则则 称是句型称是句型相对于非终结符相对于非终结符A A的的短语短语。特别

7、是，如果有特别是，如果有A A,则称则称 是句型是句型相对相对于规则于规则A A 的的直接短语直接短语。一个句型的最左。一个句型的最左直接短语称为该句型的直接短语称为该句型的句柄句柄。编译原理编译原理PPT课件课件考虑文法考虑文法G(E)：E T|E+T T F|T*F F (E)|i和句型和句型i1*i2+i3：E E+T E+F E+i3 T+i3 T*F+i3 T*i2+i3 F*i2+i3 i1*i2+i3n短语：短语：i1，i2，i3，i1*i2，i1*i2+i3n直接短语：直接短语：i1，i2，i3n句柄：句柄：i1编译原理编译原理PPT课件课件n在一个句型对应的在一个句型对应的语

8、法树中，以某非语法树中，以某非终结符为根的两代终结符为根的两代以上的子树的所有以上的子树的所有末端结点从左到右末端结点从左到右排列就是相对于该排列就是相对于该非终结符的一个短非终结符的一个短语，如果子树只有语，如果子树只有两代，则该短语就两代，则该短语就是直接短语。是直接短语。EFFTTTi1+*EFi3i2编译原理编译原理PPT课件课件n可用句柄来对句子进行归约可用句柄来对句子进行归约句型句型 归约规则归约规则abbcde (2)A baAbcde (3)A AbaAcde (4)B daAcBe (1)S aAcBe S编译原理编译原理PPT课件课件n定义：假定定义：假定 是文法是文法G的

9、一个句子，我们的一个句子，我们称序列称序列 n，n-1，0 是的一个是的一个规范归约规范归约，如果此序列满足：，如果此序列满足：1 n=2 0为文法的开始符号，即为文法的开始符号，即 0=S 3 对任何对任何i，0 i n，i-1是从是从 i经把句经把句柄替换成为相应产生式左部符号而得到柄替换成为相应产生式左部符号而得到的。的。编译原理编译原理PPT课件课件把上例倒过来写，则得到：把上例倒过来写，则得到：S S aAcBeaAcBe aAcde aAcde aAbcde aAbcde abbcde abbcde 显然这是一个最右推导。显然这是一个最右推导。规范归约规范归约是关于是一个是关于是一

10、个最右推导最右推导的逆过程的逆过程最左归约最左归约 规范推导规范推导由规范推导推出的句型称为由规范推导推出的句型称为规范句型规范句型。编译原理编译原理PPT课件课件bdbaceSABAdbaceSABAdaceSABaceSABS编译原理编译原理PPT课件课件5.1.3 符号栈的使用和分析树的表示符号栈的使用和分析树的表示n栈是语法分析的一种基本数据结构。栈是语法分析的一种基本数据结构。#作作为栈底符号为栈底符号n考虑文法考虑文法G(E)：E T|E+T T F|T*F F (E)|i输入串为输入串为i1*i2+i3，分析步骤为：，分析步骤为：编译原理编译原理PPT课件课件步骤步骤 符号栈符号

11、栈输入串输入串动作动作0#i1*i2+i3#预备预备1#i1*i2+i3#进进2#F*i2+i3#归，用归，用Fi3#T*i2+i3#归，用归，用TF4#T*i2+i3#进进nG(E)：E T|E+T T F|T*F F (E)|i编译原理编译原理PPT课件课件步骤步骤 符号栈符号栈输入串输入串动作动作4#T*i2+i3#进进5#T*i2+i3#进进6#T*F+i3#归，用归，用Fi7#T+i3#归，用归，用TT*F8#E+i3#归，用归，用ET9#E+i3#进进nG(E)：E T|E+T T F|T*F F (E)|i编译原理编译原理PPT课件课件步骤步骤 符号栈符号栈输入串输入串动作动作9

12、#E+i3#进进10#E+i3#进进11#E+F#归，用归，用Fi12#E+T#归，用归，用TF13#E#归，用归，用EE+T14#E#接受接受nG(E)：E T|E+T T F|T*F F (E)|i编译原理编译原理PPT课件课件n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归归约约”，直到文法的开始符号。即从树末端开始，直到文法的开始符号。即从树末端开始，构造语法树。所谓构造语法树。所谓 归约归约 ，是指根据文法的产，是指根据文法的产生式规则，把产生式的右部替换成左

13、部符号。生式规则，把产生式的右部替换成左部符号。回顾回顾编译原理编译原理PPT课件课件归约归约n采用采用“移进归约移进归约”思想进行自下而上分析。思想进行自下而上分析。n基本思想：用一个寄存符号的先进后出基本思想：用一个寄存符号的先进后出栈栈，把输，把输入符号一个一个地移进到栈里，当栈顶形成某个入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成产生式的候选式时，即把栈顶的这一部分替换成(归约归约为为)该产生式的左部符号。该产生式的左部符号。编译原理编译原理PPT课件课件规范归约规范归约n定义：令定义：令G G是一个文法，是一个文法，S S是文法的开始符是文法的

14、开始符号，假定号，假定是文法是文法G G的一个句型，如果有的一个句型，如果有 且且 AS*A则则 称是句型称是句型相对于非终结符相对于非终结符A A的的短语短语。特别是，如果有特别是，如果有A A,则称则称 是句型是句型相对相对于规则于规则A A 的的直接短语直接短语。一个句型的最左。一个句型的最左直接短语称为该句型的直接短语称为该句型的句柄句柄。编译原理编译原理PPT课件课件n定义：假定定义：假定 是文法是文法G的一个句子，我们的一个句子，我们称序列称序列 n，n-1，0 是的一个是的一个规范归约规范归约，如果此序列满足：，如果此序列满足：1 n=2 0为文法的开始符号，即为文法的开始符号，

15、即 0=S 3 对任何对任何i，0 i n，i-1是从是从 i经把经把句句柄柄替换成为相应产生式左部符号而得到替换成为相应产生式左部符号而得到的。的。编译原理编译原理PPT课件课件步骤步骤 符号栈符号栈输入串输入串动作动作0#i1*i2+i3#预备预备1#i1*i2+i3#进进2#F*i2+i3#归，用归，用Fi3#T*i2+i3#归，用归，用TF4#T*i2+i3#进进nG(E)：E T|E+T T F|T*F F (E)|i编译原理编译原理PPT课件课件步骤步骤 符号栈符号栈输入串输入串动作动作4#T*i2+i3#进进5#T*i2+i3#进进6#T*F+i3#归，用归，用Fi7#T+i3#

16、归，用归，用TT*F8#E+i3#归，用归，用ET9#E+i3#进进nG(E)：E T|E+T T F|T*F F (E)|i编译原理编译原理PPT课件课件步骤步骤 符号栈符号栈输入串输入串动作动作9#E+i3#进进10#E+i3#进进11#E+F#归，用归，用Fi12#E+T#归，用归，用TF13#E#归，用归，用EE+T14#E#接受接受nG(E)：E T|E+T T F|T*F F (E)|i编译原理编译原理PPT课件课件5.2 5.2 算符优先分析算符优先分析n四则运算的优先规则：四则运算的优先规则：先乘除后加减，同级从左到右先乘除后加减，同级从左到右n考虑二义文法文法考虑二义文法文法

17、G(E)：G(E)：E i|E+E|E-E|E*E|E/E|(E)n它的句子有几种它的句子有几种不同的规范规约不同的规范规约。n归约即计算表达式的值。归约顺序不同，归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。则计算的顺序也不同，结果也不一样。n如果规定算符的优先次序，并按这种规定如果规定算符的优先次序，并按这种规定进行归约，则归约过程是进行归约，则归约过程是唯一唯一的。的。编译原理编译原理PPT课件课件例如：句子例如：句子i+i-ii+i-i*(i+i)(i+i)Ei()i*EiEE+EEE-ii+EEE编译原理编译原理PPT课件课件Ei()i*EiEE+EEE-ii

18、+EEE返回编译原理编译原理PPT课件课件句子句子i+i-i*(i+i)的归约过程是：的归约过程是：(1)i+i-i*(i+i)(2)E+i-i*(i+i)(3)E+E-i*(i+i)(4)E-i*(i+i)(5)E-E*(i+i)(6)E-E*(E+i)(7)E-E*(E+E)(8)E-E*(E)(9)E-E*E(10)E-E(11)E编译原理编译原理PPT课件课件n起决定作用的是相邻的两个起决定作用的是相邻的两个算符算符之间的之间的优优先关系先关系。n所谓所谓算符优先分析法算符优先分析法就是定义算符之间的就是定义算符之间的某种优先关系，借助于这种关系寻找某种优先关系，借助于这种关系寻找“可

19、可归约串归约串”和进行归约。和进行归约。编译原理编译原理PPT课件课件n首先必须定义任何两个可能相继出现的终结首先必须定义任何两个可能相继出现的终结符符a a与与b b的优先关系的优先关系 三种关系三种关系a a b ab a的优先级低于的优先级低于b ba a b ab a的优先级等于的优先级等于b ba a b ab a的优先级高于的优先级高于b bn注意：与数学上的注意：与数学上的=不同不同+a a b b并不意味着并不意味着b b a a，如，如 (+和和 +(编译原理编译原理PPT课件课件5.2.1 算符优先文法及优先表构造算符优先文法及优先表构造n一个文法，如果它的任一产生式的右部

20、都一个文法，如果它的任一产生式的右部都不含两个相继不含两个相继(并列并列)的非终结符，即不含的非终结符，即不含如下形式的产生式右部：如下形式的产生式右部：QR 则我们称该文法为则我们称该文法为算符文法算符文法。n约定：约定：a、b代表任意终结符；代表任意终结符；P、Q、R代表任意非终结符；代表任意非终结符；代表由终结符和非终结符组成的任意序代表由终结符和非终结符组成的任意序列，包括空字。列，包括空字。编译原理编译原理PPT课件课件n假定假定G是一个不含是一个不含-产生式的算符文法。产生式的算符文法。对于任何一对终结符对于任何一对终结符a、b，我们说：，我们说：1.ab 当且仅当文法当且仅当文法

21、G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；n如果一个算符文法如果一个算符文法G中的任何终结符对中的任何终结符对(a，b)至多只满足下述三关系之一：至多只满足下述三关系之一：ab，ab，ab 则称则称G是一个算符优先文法。是一个算符优先文法。2.ab 当且仅当当且仅当G中含有形如中含有形如PaR的产生式，的产生式，而而R b或或R Qb；3.ab 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。编译原理编译原理PPT课件课件n例例:考虑下面的文法考虑下面的文法G(E)：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P

22、(E)|in由第由第(4)条规则，有条规则，有()；n由规则由规则EET和和TT*F，有有*；n由由(2)TT*F 和和(3)FP F，可得，可得*；n由由(1)EET和和E E+T，可得，可得+；n由由(3)FP F和和F P F，可得，可得。n由由(4)P(E)和和 EE+TT+TT*F+TF*F+TPF*F+TiF*F+T 有有(+、(*、(和和(i。编译原理编译原理PPT课件课件n 优先关系表优先关系表+*i()#+*i()#编译原理编译原理PPT课件课件n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n通过检查通过检查G的每个产生式的每个候选式，可的每个产

23、生式的每个候选式，可找出所有满足找出所有满足ab的终结符对。的终结符对。2.ab 当且仅当当且仅当G中含有形如中含有形如PaR的产生式，的产生式，而而R b或或R Qb；3.ab 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。n确定满足关系确定满足关系和和的所有终结符对：的所有终结符对：1.ab当且仅当文法当且仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；编译原理编译原理PPT课件课件n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n通过检查通过检查G的每个产生式的每个候选式，可的每个产生式的每个候选

24、式，可找出所有满足找出所有满足ab的终结符对。的终结符对。n确定满足关系确定满足关系和和的所有终结符对：的所有终结符对：首先需要对首先需要对G的每个非终结符的每个非终结符P构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P)：ab当且仅当当且仅当G中含有形如中含有形如PaR的产生式，的产生式，而而R b或或R Qb；编译原理编译原理PPT课件课件n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n通过检查通过检查G的每个产生式的每个候选式，可的每个产生式的每个候选式，可找出所有满足找出所有满足ab的终结符对。的终结符对。n确定满足关系确定满足关系和和的所

25、有终结符对：的所有终结符对：首先需要对首先需要对G的每个非终结符的每个非终结符P构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P)：,|)(NTVQVaaQPaPaPLASTVT而或3.ab 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。编译原理编译原理PPT课件课件n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n通过检查通过检查G的每个产生式的每个候选式，可的每个产生式的每个候选式，可找出所有满足找出所有满足ab的终结符对。的终结符对。n确定满足关系确定满足关系和和的所有终结符对：的所有终结符对：首先需

26、要对首先需要对G的每个非终结符的每个非终结符P构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P)：,|)(NTVQVaaQPaPaPLASTVT而或.,|=)(*TVaaaFIRST比较.,.|)(*TVaAaSaAFOLLOW比较编译原理编译原理PPT课件课件q有了这两个集合之后，就可以通过检查每有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系个产生式的候选式确定满足关系和和的的所有终结符对。所有终结符对。假定有个产生式的一个候选形为假定有个产生式的一个候选形为aP 那么，对任何那么，对任何b FIRSTVT(P)，有，有 ab。假定有个产生式的一个候选形为假

27、定有个产生式的一个候选形为Pb 那么，对任何那么，对任何a LASTVT(P)，有，有 ab。编译原理编译原理PPT课件课件n首先讨论构造集合首先讨论构造集合FIRSTVT(P)的算法。的算法。n按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式若有产生式Pa或或PQa，则，则a FIRSTVT(P)；2.若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则则a FIRSTVT(P)。编译原理编译原理PPT课件课件n数据结构：数据结构：布尔数组布尔数组FP，a，使得，使得FP，a为真的条件是，为真的条件是，当且仅当当且仅当a F

28、IRSTVT(P)。开始时，按上述的。开始时，按上述的规则规则(1)对每个数组元素对每个数组元素FP，a赋初值。赋初值。栈栈STACK，把所有初值为真的数组元素，把所有初值为真的数组元素FP，a的符号对的符号对(P，a)全都放在全都放在STACK之中。之中。编译原理编译原理PPT课件课件n运算：运算：如果栈如果栈STACK不空，就将顶项逐出，记此不空，就将顶项逐出，记此项为项为(Q，a)。对于每个形如。对于每个形如PQ 的产生式，若的产生式，若FP，a为假，则变其值为真为假，则变其值为真且将且将(P，a)推进推进STACK栈。栈。上述过程必须一直重复，直至栈上述过程必须一直重复，直至栈STAC

29、K拆拆空为止。空为止。编译原理编译原理PPT课件课件n如果把这个算法稍为形式化一点，我们如果把这个算法稍为形式化一点，我们可得如下所示的一个程序可得如下所示的一个程序(包括一个过程包括一个过程和主程序和主程序)：PROCEDURE INSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE；把把(P，a)下推进下推进STACK栈栈 END；编译原理编译原理PPT课件课件主程序：主程序：BEGIN FOR 每个非终结符每个非终结符P和终结符和终结符a DO FP，a:=FALSE；FOR 每个形如每个形如Pa或或PQa的产生式的产生式 DO INSERT(P，a)；

30、WHILE STACK 非空非空 DOBEGIN 把把STACK的顶项，记为的顶项，记为(Q，a)，上托出去；，上托出去；FOR 每条形如每条形如PQ的产生式的产生式 DOINSERT(P，a)；END OF WHILE；END编译原理编译原理PPT课件课件n这个算法的工作结果得到一个二维数组这个算法的工作结果得到一个二维数组F，从它可得任何非终结符从它可得任何非终结符P的的FIRSTVT。FIRSTVT(P)a|FP，a=TRUEn同理，可构造计算同理，可构造计算LASTVT的算法。的算法。编译原理编译原理PPT课件课件n构造集合构造集合LASTVT(P)的算法。的算法。n按其定义，可用下面

31、两条规则来构造集合按其定义，可用下面两条规则来构造集合LASTVT(P)：1.若有产生式若有产生式P a或或P aQ，则，则a LASTVT(P)；2.若若a LASTVT(Q)，且有产生式，且有产生式P Q，则则a LASTVT(P)。,|)(NTVQVaaQPaPaPLASTVT而或编译原理编译原理PPT课件课件n使用每个非终结符使用每个非终结符P的的FIRSTVT(P)和和LASTVT(P)，就能够构造文法，就能够构造文法G的优先的优先表。构造优先表的算法是：表。构造优先表的算法是：编译原理编译原理PPT课件课件FOR 每条产生式每条产生式PX1X2Xn DO FOR i:=1 TO n

32、-1 DOBEGIN IF Xi和和Xi+1均为终结符均为终结符 THEN 置置XiXi+1 IF i n-2且且Xi和和Xi+2都为终结符都为终结符 但但Xi+1为非终结符为非终结符 THEN 置置XiXi+2；IF Xi为终结符而为终结符而Xi+1为非终结符为非终结符 THENFOR FIRSTVT(Xi+1)中的每个中的每个a DO 置置 Xia；IF Xi为非终结符而为非终结符而Xi+1为终结符为终结符 THEN FOR LASTVT(Xi)中的每个中的每个a DO 置置 aXi+1 END编译原理编译原理PPT课件课件n例例:考虑下面的文法考虑下面的文法G(E)：(1)EE+T|T

33、(2)TT*F|F (3)FP F|P (4)P(E)|i1.计算文法计算文法G的的FIRSTVT和和LASTVT;2.构造优先关系表构造优先关系表;3.G是算符优先文法吗是算符优先文法吗?编译原理编译原理PPT课件课件+*()iE TFP(,)(,*,)(,)(,*,)(iPFIRSTVTiEFIRSTVTiFFIRSTVTiTFIRSTVT+*()iE T F P),)(),*,)(),)(),*,)(iPLASTVTiELASTVTiFLASTVTiTLASTVT编译原理编译原理PPT课件课件+*()i i+*()i iG结论结论:G是算符优先文法是算符优先文法q G的算符优先关系表的算

34、符优先关系表编译原理编译原理PPT课件课件回顾n定义任何两个可能相继出现的终结符定义任何两个可能相继出现的终结符a a与与b b的优先关系的优先关系 三种关系三种关系a a b ab a的优先级低于的优先级低于b ba a b ab a的优先级等于的优先级等于b ba a b ab a的优先级高于的优先级高于b bn注意：与数学上的注意：与数学上的=不同，不同，a a b b并不意并不意味着味着b b a a编译原理编译原理PPT课件课件n假定假定G是一个不含是一个不含-产生式的算符文法。产生式的算符文法。对于任何一对终结符对于任何一对终结符a、b，我们说：，我们说：1.ab 当且仅当文法当且

35、仅当文法G中含有形如中含有形如Pab或或PaQb的产生式；的产生式；n如果一个算符文法如果一个算符文法G中的任何终结符对中的任何终结符对(a，b)至多只满足下述三关系之一：至多只满足下述三关系之一：ab，ab，ab 则称则称G是一个是一个算符优先文法算符优先文法。2.ab 当且仅当当且仅当G中含有形如中含有形如PaR的产生式，的产生式，而而R b或或R Qb；3.ab 当且仅当当且仅当G中含有形如中含有形如PRb的产生式，而的产生式，而 R a或或R aQ。编译原理编译原理PPT课件课件n从算符优先文法从算符优先文法G构造优先关系表的算法。构造优先关系表的算法。n通过检查通过检查G的每个产生式

36、的每个候选式，可的每个产生式的每个候选式，可找出所有满足找出所有满足ab的终结符对。的终结符对。n确定满足关系确定满足关系和和的所有终结符对：的所有终结符对：首先需要对首先需要对G的每个非终结符的每个非终结符P构造两个集合构造两个集合FIRSTVT(P)和和LASTVT(P)：,|)(NTVQVaaQPaPaPLASTVT而或.,|=)(*TVaaaFIRST比较.,.|)(*TVaAaSaAFOLLOW比较编译原理编译原理PPT课件课件q有了这两个集合之后，就可以通过检查每有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系个产生式的候选式确定满足关系和和的的所有终结符对。所有终

37、结符对。假定有个产生式的一个候选形为假定有个产生式的一个候选形为aP 那么，对任何那么，对任何b FIRSTVT(P)，有，有 ab。假定有个产生式的一个候选形为假定有个产生式的一个候选形为Pb 那么，对任何那么，对任何a LASTVT(P)，有，有 ab。编译原理编译原理PPT课件课件n首先讨论构造集合首先讨论构造集合FIRSTVT(P)的算法。的算法。n按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式若有产生式Pa或或PQa，则，则a FIRSTVT(P)；2.若若a FIRSTVT(Q)，且有产生式，且有产生式PQ，则则a FI

38、RSTVT(P)。编译原理编译原理PPT课件课件n构造集合构造集合LASTVT(P)的算法。的算法。n按其定义，可用下面两条规则来构造集合按其定义，可用下面两条规则来构造集合LASTVT(P)：1.若有产生式若有产生式P a或或P aQ，则，则a LASTVT(P)；2.若若a LASTVT(Q)，且有产生式，且有产生式P Q，则则a LASTVT(P)。,|)(NTVQVaaQPaPaPLASTVT而或编译原理编译原理PPT课件课件n使用每个非终结符使用每个非终结符P的的FIRSTVT(P)和和LASTVT(P)，就能够构造文法，就能够构造文法G的优先的优先表。构造优先表的算法是：表。构造优

39、先表的算法是：编译原理编译原理PPT课件课件FOR 每条产生式每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DOBEGIN IF Xi和和Xi+1均为终结符均为终结符 THEN 置置XiXi+1 IF i n-2且且Xi和和Xi+2都为终结符都为终结符 但但Xi+1为非终结符为非终结符 THEN 置置XiXi+2；IF Xi为终结符而为终结符而Xi+1为非终结符为非终结符 THENFOR FIRSTVT(Xi+1)中的每个中的每个a DO 置置 Xia；IF Xi为非终结符而为非终结符而Xi+1为终结符为终结符 THEN FOR LASTVT(Xi)中的每个中的每个a DO

40、置置 aXi+1 END编译原理编译原理PPT课件课件5.2.2 算符优先分析算法算符优先分析算法n可归约串，句型，短语，直接短语，句柄，可归约串，句型，短语，直接短语，句柄，规范归约。规范归约。n一个文法一个文法G G的句型的的句型的素短语素短语是指这样一个短是指这样一个短语，它至少含有一个终结符，并且，除它语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。自身之外不再含任何更小的素短语。n最左素短语最左素短语是指处于句型最左边的那个素是指处于句型最左边的那个素短语。短语。编译原理编译原理PPT课件课件n考虑下面的文法考虑下面的文法G(E)：(1)EE+T|T (2)TT*

41、F|F (3)FP F|P (4)P(E)|iEEF+*TiFTFTP+ETP句型：句型：T+F*P+i短语：短语：直接短语：直接短语：句柄：句柄：素短语：素短语：最左素短语：最左素短语：,T+F*P+iT,F,P,F*P,iT+F*PT,F,P,iTF*P,iF*P编译原理编译原理PPT课件课件n算符优先文法句型算符优先文法句型(括在两个之间括在两个之间)的一般的一般形式写成：形式写成：#N1a1N2a2NnanNn+1#其中，每个其中，每个ai都是终结符，都是终结符，Ni是可有可无的非是可有可无的非终结符。终结符。n定理：一个算符优先文法定理：一个算符优先文法G的任何句型的最的任何句型的最

42、左素短语是满足如下条件的最左子串左素短语是满足如下条件的最左子串 NjajNiaiNi+1，aj-1aj aj aj+1，ai-1ai aiai+1编译原理编译原理PPT课件课件n算符优先分析算法算符优先分析算法n使用一个符号栈使用一个符号栈S，用它寄存终结符和非终结，用它寄存终结符和非终结符，符，k代表符号栈代表符号栈S的使用深度。的使用深度。编译原理编译原理PPT课件课件k:=1;Sk:=#;REPEAT 把下一个输入符号读进把下一个输入符号读进a中；中；IF Sk VT THEN j:=k ELSE j:=k-1;WHILE Sja DOBEGIN REPEAT Q:=Sj;IF Sj-

43、1 VT THEN j:=j-1 ELSE j:=j-2 UNTIL SjQ;把把Sj+1Sk归约为某个归约为某个N；k:=j+1;Sk:=N END OF WHILE;IF Sja OR Sja THEN BEGIN k:=k+1;Sk:=a END ELSE ERROR/*调用出错诊察程序调用出错诊察程序*/UNTIL a=#自左至右，终结符对终结符，非自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符对非终结符，而且对应的终结符相同。终结符相同。N X1 X2 Xk-j Sj+1 Sj+2 Sk编译原理编译原理PPT课件课件n在算法的工作过程中，若出现在算法的工作过程中，若出

44、现j减减1后的值后的值小于等于小于等于0时，则意味着输入串有错。在时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈正确的情况下，算法工作完毕时，符号栈S应呈现：应呈现：#N#。n由于非终结符对归约没有影响，因此，非由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈终结符根本可以不进符号栈S。编译原理编译原理PPT课件课件n算符优先分析一般并不等价于规范归约。算符优先分析一般并不等价于规范归约。EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiPn考虑下面的文法考虑下面的文法G(E)：(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P

45、(E)|i的句子的句子i+i*i+i编译原理编译原理PPT课件课件n算符优先分析法特点：算符优先分析法特点：优点优点:简单，快速简单，快速缺点缺点:可能错误接受非法句子，能力有限可能错误接受非法句子，能力有限.n算符优先分析法是一种广为应用、行之算符优先分析法是一种广为应用、行之有效的方法。有效的方法。用于分析各类表达式用于分析各类表达式ALGOL 60编译原理编译原理PPT课件课件5.2.3 5.2.3 优先函数优先函数n把每个终结符把每个终结符 与两个自然数与两个自然数f(f()与与g(g()相对相对应，使得应，使得若若 1 1 2 2，则，则f(f(1 1)g(g(g(2 2)f f称为

46、入栈优先函数，称为入栈优先函数，g g称为比较优先函数。称为比较优先函数。n优点优点:便于比较，节省空间；便于比较，节省空间；n缺点缺点:原来不存在优先关系的两个终结符，由原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行于自然数相对应，变成可以比较的。要进行一些特殊的判断。一些特殊的判断。编译原理编译原理PPT课件课件n文法文法G(E)G(E)(1)EE+T|T (2)TT*F|F (3)FP F|P (4)P(E)|i的优先函数如下表的优先函数如下表+*()i#F2440660G1355050编译原理编译原理PPT课件课件n有许多优先关系表不存在优先函数，如：有许多优

47、先关系表不存在优先函数，如：abab 不存在对应的优先函数不存在对应的优先函数f和和g 假定存在假定存在f和和g，则有，则有 f(a)=g(a)，f(a)g(b)，f(b)=g(a)，f(b)=g(b)导致如下矛盾导致如下矛盾:f(a)g(b)=f(b)=g(a)=f(a)G如果优先函数存在，则不唯一如果优先函数存在，则不唯一(无穷多无穷多)编译原理编译原理PPT课件课件n如果优先函数存在，则可以通过以下三个步如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数骤从优先表构造优先函数:1 1 对于每个终结符对于每个终结符a a，令其对应两个符号，令其对应两个符号f fa a和和g ga

48、 a，画一以所有符号和为结点的方向图。如果画一以所有符号和为结点的方向图。如果a ab b，则从则从f fa a画一条弧至画一条弧至g gb b，如果，如果a ab b，则画一条弧，则画一条弧从从g gb b至至f fa a 。2 2 对每个结点都赋予一个数，此数等于从该结点对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点出发所能到达的结点(包括出发点自身包括出发点自身)。赋给。赋给f fa a的数作为的数作为f(a)f(a)，赋给，赋给g ga a的数作为的数作为g(a)g(a)。3 3 检查所构造出来的函数检查所构造出来的函数f f和和g g是否与原来的关系是否与原来的关系矛盾。

49、若没有矛盾，则矛盾。若没有矛盾，则f f和和g g就是要求的优先函数，就是要求的优先函数，若有矛盾，则不存在优先函数。若有矛盾，则不存在优先函数。编译原理编译原理PPT课件课件n现在必须证明：若现在必须证明：若ab，则，则f(a)g(b)；若若ab，则，则f(a)g(b)。n第一个关系可从函数的构造直接获得。因第一个关系可从函数的构造直接获得。因为，若为，若ab，则既有从，则既有从fa到到gb的弧，又有的弧，又有从从gb到到fa的弧。所以，的弧。所以，fa和和gb所能到达的结所能到达的结是全同的。是全同的。n至于至于ab和和ab的情形，只须证明其一。的情形，只须证明其一。1 1 对于每个终结符

50、对于每个终结符a a，令其对应两个符号，令其对应两个符号f fa a和和g ga a，画一以所有符号和为结点的方向，画一以所有符号和为结点的方向图。如果图。如果a ab b，则从，则从f fa a画一条弧至画一条弧至g gb b，如果如果a ab b，则画一条弧从，则画一条弧从g gb b至至f fa a 。编译原理编译原理PPT课件课件n如果如果ab，则有从，则有从fa到到gb的弧。也就是，的弧。也就是，gb能到达的任何结能到达的任何结fa也能到达。因此，也能到达。因此，f(a)g(b)。我们所需证明的是，在这种情况下，我们所需证明的是，在这种情况下，f(a)g(b)不应成立。不应成立。我们

51、将指出，如果我们将指出，如果f(a)g(b)，则根本不存，则根本不存在优先函数。假若在优先函数。假若f(a)g(b)，那么必有如，那么必有如下的回路：下的回路：编译原理编译原理PPT课件课件 因此有因此有ab,a1b,a1b1,ambm,abm对任何优先函数对任何优先函数f和和g来说，必定有来说，必定有f(a)g(b)f(a1)g(b1)f(am)g(bm)f(a)从而导致从而导致f(a)f(a)，产生矛盾。因此，不存在，产生矛盾。因此，不存在优先函数优先函数f和和g。fa1fafamgb1gbgbm编译原理编译原理PPT课件课件n例例:取前面文法取前面文法G(E)G(E)(1)EE+T|T

52、(2)TT*F|F (3)FP F|P (4)P(E)|i的终结符的终结符+，*，i i编译原理编译原理PPT课件课件+*i+*if+f*f fig+g*g gi+*if2447g1366编译原理编译原理PPT课件课件n语法分析的方法：语法分析的方法：自下而上分析法自下而上分析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归约归约”，直到文法的开始符号。即从树末端开始，构造语直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。

53、把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。性质进行语法分析。适合分析表达式。n优先关系表的构造：优先关系表的构造：FIRSTVT,LASTVTFIRSTVT,LASTVTn优先函数优先函数n算符优先分析法算符优先分析法回顾回顾编译原理编译原理PPT课件课件规范归约规范归约n定义：令定义：令G G是一个文法，是一个文法，S S是文法的开始符是文法的开始符号，假定号，假定是文法是文法G G的一个句型，如果有的一个句型，如果有 且且 AS*A则则 称是句型称是句型相对于非终结符相对于非终结符A A的

54、的短语短语。特别是，如果有特别是，如果有A A,则称则称 是句型是句型相对相对于规则于规则A A 的的直接短语直接短语。一个句型的最左。一个句型的最左直接短语称为该句型的直接短语称为该句型的句柄句柄。编译原理编译原理PPT课件课件n定义：假定定义：假定 是文法是文法G的一个句子，我们的一个句子，我们称序列称序列 n，n-1，0 是的一个是的一个规范归约规范归约，如果此序列满足：，如果此序列满足：1 n=2 0为文法的开始符号，即为文法的开始符号，即 0=S 3 对任何对任何i，0 i n，i-1是从是从 i经把句经把句柄替换成为相应产生式左部符号而得到柄替换成为相应产生式左部符号而得到的。的。

55、编译原理编译原理PPT课件课件5.3 LR分析法分析法nLR分析法：分析法：1965年年 由由Knuth提出提出分析表产分析表产生器生器文法文法分析表分析表输入输入输出输出 产生分析表产生分析表 LR分析器工作分析器工作LR分析总分析总 控程控程 序序分析表分析表编译原理编译原理PPT课件课件主要介绍主要介绍1.总控程序总控程序(LR分析器分析器)的处理思想的处理思想2.LR分析表的构造方法及原理分析表的构造方法及原理编译原理编译原理PPT课件课件5.3.1 LR分析器分析器n规范归约规范归约的关键问题是寻的关键问题是寻找找句柄句柄.“历史历史”：已移入符号栈的：已移入符号栈的内容内容“展望展

56、望”：根据产生式推：根据产生式推测未来可能遇到的输入符测未来可能遇到的输入符号号“现实现实”：当前的输入符：当前的输入符号号 Xn 输入串 X2 a#X1#编译原理编译原理PPT课件课件nLR分析方法：把分析方法：把历史历史及及展望展望综合抽象综合抽象成状态；由栈顶的状态和现行的输入符号成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作唯一确定每一步工作 LR分析分析程程 序序状态状态符号符号SmXmS1X1S0#分析栈分析栈 action goto LR分析表分析表a1a2ai an#输入串输入串 输出输出编译原理编译原理PPT课件课件nLR分析器的核心是一张分析表：分析器的核心是一张分

57、析表：ACTIONs，a：当状态：当状态s面临输入符号面临输入符号a时，时，应采取什么动作应采取什么动作.GOTOs，X：状态：状态s面对文法符号面对文法符号X时，下时，下一状态是什么一状态是什么编译原理编译原理PPT课件课件n每一项每一项ACTIONs，a所规定的四种动作所规定的四种动作:1.移进移进 把把(s，a)的下一状态的下一状态s和输入符号和输入符号a推推进栈，下一输入符号变成现行输入符号进栈，下一输入符号变成现行输入符号.2.归约归约 指用某产生式指用某产生式A进行归约进行归约.假若假若 的长度为的长度为r，归约动作是，归约动作是，去除栈顶去除栈顶r个项，个项，使状态使状态sm-r

58、变成栈顶状态，然后把变成栈顶状态，然后把(sm-r,A)的的下一状态下一状态s=GOTOsm-r,A和文法符号和文法符号A推进推进栈栈.3.接受接受 宣布分析成功，停止分析器工作宣布分析成功，停止分析器工作.4.报错报错编译原理编译原理PPT课件课件n分析开始时分析开始时:状态状态 已归约串已归约串 输入串输入串 (s0，#，a1a2 an#)n以后每步的结果可以表示为以后每步的结果可以表示为:(s0 s1 sm，#X1 Xm，aiai+1 an#)编译原理编译原理PPT课件课件(s0 s1 sm，#X1 Xm，aiai+1 an#)n分析器根据分析器根据ACTION(sm,ai)确定下一步动

59、作确定下一步动作1.若若ACTION(sm,ai)为移进，且为移进，且s=GOTO(sm,ai),，则三元式格局变为则三元式格局变为:(s0 s1 sms，#X1 Xm ai，ai+1 an#)2.若若ACTION(sm,ai)为按为按A归约，三元式变为归约，三元式变为:(s0 s1 sm-rs，#X1 Xm-rA，aiai+1 an#)此处此处,s=GOTO(sm-r,A),r为为 的长度的长度,=Xm-r+1 Xm3.若若ACTION(sm,ai)为为接受接受，则三元式不再变化，则三元式不再变化，变化过程终止，宣布分析成功变化过程终止，宣布分析成功.4.若若ACTION(sm,ai)为为报

60、错报错，则三元式变化过程终，则三元式变化过程终止，报告错误止，报告错误.(s0 s1 sm-r sm-r+1 sm，#X1 Xm-r Xm-r+1 Xm，aiai+1 an#)(s0 s1 sm-r，#X1 Xm-r，aiai+1 an#)(s0 s1 sm-rs，#X1 Xm-rA，aiai+1 an#)编译原理编译原理PPT课件课件LR分析器示例：分析器示例：文法文法G(E)：(1)EET(2)ET(3)TT*F(4)TF(5)F(E)(6)Fi编译原理编译原理PPT课件课件ACTIONGOTO状态状态i+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5

61、s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5其其LR分析表为分析表为:编译原理编译原理PPT课件课件n假定输入串为假定输入串为i*i+i，LR分析器的工作过程分析器的工作过程:步骤步骤状态状态符号符号输入串输入串(1)0#i*i+i#(2)05#i*i+i#(3)03#F*i+i#(4)02#T*i+i#(5)027#T*i+i#TiF*编译原理编译原理PPT课件课件n假定输入串为假定输入串为i*i+i，LR分析器的工作过程分析器的工作过程:步骤步骤状态状态符号符号输入串输入串(5)027#T*i+i#(6)02

62、75#T*i+i#(7)02710#T*F+i#(8)02#T+i#(9)01#E+i#(10)016#E+i#+iTF*TFiE编译原理编译原理PPT课件课件步骤步骤状态状态符号符号输入串输入串(10)016#E+i#(11)0165#E+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15)接受接受+iTF*TFiEiTFE编译原理编译原理PPT课件课件n定义：对于一个文法，如果能够构造一张定义：对于一个文法，如果能够构造一张分析表，使得它的每个入口均是唯一确定分析表，使得它的每个入口均是唯一确定的，则这个文法就称为的，则这个文法就称为LR文法文法。n定义：一个

63、文法，如果能用一个每步顶多定义：一个文法，如果能用一个每步顶多向前检查向前检查k个输入符号的个输入符号的LR分析器进行分分析器进行分析，则这个文法就称为析，则这个文法就称为LR(k)文法文法.n非非LR结构结构LR文法不是二义的，二义文法肯定不会是文法不是二义的，二义文法肯定不会是LR的。的。S iCtS|iCtSeS 栈栈 输入输入 iCtS e#编译原理编译原理PPT课件课件5.3.2 LR(0)项目集族和项目集族和LR(0)分析分析表的构造表的构造n假定假定 是文法是文法G的一个句子，我们称序列的一个句子，我们称序列 n，n-1，0 是的一个是的一个规范归约规范归约，如果此序列满足：，如

64、果此序列满足：1 n=2 0为文法的开始符号，即为文法的开始符号，即 0=S 3 对任何对任何i，0 i n，i-1是从是从 i经把句柄替经把句柄替换成为相应产生式左部符号而得到的。换成为相应产生式左部符号而得到的。编译原理编译原理PPT课件课件5.3.2 LR(0)项目集族和项目集族和LR(0)分析分析表的构造表的构造n规范归约过程中规范归约过程中栈内的符号串和扫描剩下的输入符号串构成了栈内的符号串和扫描剩下的输入符号串构成了一个规范句型一个规范句型栈内的如果出现句柄，句柄一定在栈的顶部栈内的如果出现句柄，句柄一定在栈的顶部Xa 句柄句柄 句句柄柄 柄柄句句a 柄柄句句a 栈内永远不会出现句

65、柄之后的符号！编译原理编译原理PPT课件课件5.3.2 LR(0)项目集族和项目集族和LR(0)分分析表的构造析表的构造n字的前缀字的前缀：是指字的任意首部，如字：是指字的任意首部，如字abc的的前缀有前缀有，a，ab，abcn活前缀活前缀：是指：是指规范句型规范句型的一个前缀，这种前的一个前缀，这种前缀不含缀不含句柄句柄之后的任何符号。即，对于规范之后的任何符号。即，对于规范句型句型，为句柄，如果为句柄，如果=u1u2ur，则，则符号串符号串u1u2ui(1 i r)是是的的活前缀活前缀。(必为终结符串必为终结符串)n对于一个文法对于一个文法G,可以构造一个可以构造一个DFA,它能识它能识别

66、别G的所有活前缀的所有活前缀.编译原理编译原理PPT课件课件指导思想指导思想目标驱动目标驱动n踢足球踢足球“如果你不知道怎样踢球，如果你不知道怎样踢球，就往球门方向踢就往球门方向踢”施拉普纳施拉普纳nLR分析分析“如果你不知道怎样分析，如果你不知道怎样分析，就保证栈中总是就保证栈中总是活前缀活前缀”一个语言都有哪些一个语言都有哪些活前缀活前缀?那些字符串是那些字符串是活前缀活前缀?能不能构造一个能不能构造一个DFA来识来识别别活前缀活前缀?编译原理编译原理PPT课件课件n文法文法G的每个产生式的右部添加一个圆的每个产生式的右部添加一个圆点称为点称为G的的LR(0)项目项目n如如:AXYZ有四个项目：有四个项目：A.XYZ AX.YZ AXY.Z AXYZ.FA.称为称为归约项目归约项目F归约项目归约项目 S.称为称为接受项目接受项目FA.a (a VT)称为称为移进项目移进项目F A.B (B VN)称为称为待约项目待约项目.编译原理编译原理PPT课件课件n文法文法G(S)S E EaA|bB AcA|d BcB|d n 该文法的项目有：该文法的项目有：1.S E2.S E3.EaA