自底向上优先分析法 (2).ppt

《自底向上优先分析法 (2).ppt》由会员分享，可在线阅读，更多相关《自底向上优先分析法 (2).ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6 6章章 自底向上优先分析法自底向上优先分析法6.1概述概述原理原理:在采用在采用自左向右自左向右扫描，扫描，自底向上自底向上分析的前提下，该类分析的前提下，该类 分析方法是从输入符号串入手，通过反复查找当前句分析方法是从输入符号串入手，通过反复查找当前句 型的句柄（最左简单短语），并使用文法的产生式把型的句柄（最左简单短语），并使用文法的产生式把 句柄归约成相应的非终结符来一步步地进行分析的。句柄归约成相应的非终结符来一步步地进行分析的。最终把输入串归约成文法的开始符号，表明分析成功。最终把输入串归约成文法的开始符号，表明分析成功。所以，任何自底向上分析方法的关键就是要找出当前所以，任

2、何自底向上分析方法的关键就是要找出当前句型的句柄，然后根据产生式判别将它归约成什么样的非句型的句柄，然后根据产生式判别将它归约成什么样的非终结符号。终结符号。下面，我们结合具体的实现方法，介绍在分析过程中下面，我们结合具体的实现方法，介绍在分析过程中如何来识别句柄的。我们首先介绍自底向上分析的一般过如何来识别句柄的。我们首先介绍自底向上分析的一般过程，再介绍两种常用的分析技术：简单优先分析法和程，再介绍两种常用的分析技术：简单优先分析法和LRLR分分析方法。析方法。一、自底向上分析的一般过程：一、自底向上分析的一般过程：先设置一个寄存符号的栈，称为分析栈。其作用是用来记先设置一个寄存符号的栈，

3、称为分析栈。其作用是用来记录分析的历史和指示分析的下一步动作。分析进行时，把输入录分析的历史和指示分析的下一步动作。分析进行时，把输入符号一个一个地按扫描顺序移进栈中，当栈顶符号形成一个句符号一个一个地按扫描顺序移进栈中，当栈顶符号形成一个句柄（即为某产生式的右部）时，就进行一次归约，即把栈顶构柄（即为某产生式的右部）时，就进行一次归约，即把栈顶构成句柄的那个符号串用相应的产生式左部符号来替换成句柄的那个符号串用相应的产生式左部符号来替换。接着再检查在栈顶是否又出现了新的句柄，则再进行归约，接着再检查在栈顶是否又出现了新的句柄，则再进行归约，直至整个输入符号串处理完。最终如果栈顶为文法的开始符

4、号，直至整个输入符号串处理完。最终如果栈顶为文法的开始符号，则所分析的输入符号串为合法的符号串，报告分析成功则所分析的输入符号串为合法的符号串，报告分析成功,否则，否则，是不合格的符号串，报告错误。是不合格的符号串，报告错误。例：考虑文法例：考虑文法G(E)：EE+T|TTT*F|FFi|(E)并假定输入串为（并假定输入串为（i+i)*ii+i)*i，考察考察自底向上的分析过程。自底向上的分析过程。例：考虑文法例：考虑文法G(E)：EE+T|TTT*F|FFi|(E)并假定输入串为（并假定输入串为（i+i)*ii+i)*i，考察考察自底向上的分析过程。自底向上的分析过程。二、分析过程图表：二、

5、分析过程图表：为了具体实现上的方便，我们仍统一约定以为了具体实现上的方便，我们仍统一约定以“#”#”作为输入串的左右分界作为输入串的左右分界符（开始和结束标志）。作为初始状态，先将符号串的开始标志符（开始和结束标志）。作为初始状态，先将符号串的开始标志“#”#”压入分压入分析栈中，作为栈底符号，则分析过程为：析栈中，作为栈底符号，则分析过程为：步骤步骤 分析栈分析栈 输入串输入串 动作动作1 1#(i+i)*i#(i+i)*i#移进移进2 2#(i+i)*i#(i+i)*i#移进移进3 3#(i +i)*i#(i +i)*i#归约归约4 4#(F +i)*i#(F +i)*i#归约归约5 5#

6、(T +i)*i#(T +i)*i#归约归约6 6#(E +i)*i#(E +i)*i#移进移进7 7#(E+i)*i#(E+i)*i#移进移进8 8#(E+i )*i#(E+i )*i#归约归约9 9#(E+F )*i#(E+F )*i#归约归约 步骤步骤 分析栈分析栈 输入串输入串 动作动作10#(E+T )*i#10#(E+T )*i#归约归约11#(E )*i#11#(E )*i#移进移进12#(E)*i#12#(E)*i#归约归约13#F *i#13#F *i#归约归约14#T *i#14#T *i#移进移进15#T*i#15#T*i#移进移进16#T*i#16#T*i#归约归约17

7、#T*F#17#T*F#归约归约18#T#18#T#归约归约19#E#19#E#接受接受分析过程图表：分析过程图表：步骤步骤 分析栈分析栈 输入串输入串 动作动作1 1#(i+i)*i#(i+i)*i#移进移进2 2#(i+i)*i#(i+i)*i#移进移进3 3#(i +i)*i#(i +i)*i#归约归约4 4#(F +i)*i#(F +i)*i#归约归约5 5#(T +i)*i#(T +i)*i#归约归约6 6#(E +i)*i#(E +i)*i#移进移进7 7#(E+i)*i#(E+i)*i#移进移进8 8#(E+i )*i#(E+i )*i#归约归约9 9#(E+F )*i#(E+F

8、 )*i#归约归约 步骤步骤 分析栈分析栈 输入串输入串 动作动作10#(E+T )*i#10#(E+T )*i#归约归约11#(E )*i#11#(E )*i#移进移进12#(E)*i#12#(E)*i#归约归约13#F *i#13#F *i#归约归约14#T *i#14#T *i#移进移进15#T*i#15#T*i#移进移进16#T*i#16#T*i#归约归约17#T*F#17#T*F#归约归约18#T#18#T#归约归约19#E#19#E#接受接受 需要说明的是分析栈顶形成的候选式不一定是句柄。例如，在第需要说明的是分析栈顶形成的候选式不一定是句柄。例如，在第1414步对栈顶为步对栈顶为

9、T T，它是，它是E E的一候选式，但它不是句柄，不能归约成的一候选式，但它不是句柄，不能归约成E E。判定候选式是极为简单的事判定候选式是极为简单的事情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。情，但判定句柄就不那么容易。而不同的自底向上方法给出不同的判定方法。从从上述例子可知，自底向上方法主要包括以下四个动作：上述例子可知，自底向上方法主要包括以下四个动作：移进：把输入流的头符读到分析栈中。移进：把输入流的头符读到分析栈中。归约：把分析栈顶的句柄归约为一非终极符。归约：把分析栈顶的句柄归约为一非终极符。接受：分析成功。接受：分析成功。报错：处理错误。报错：处理错误。

10、6.2 6.2 简单优先方法简单优先方法一、概述一、概述 简单优先方法是一种简单直观，广为使用的自底向上的分析简单优先方法是一种简单直观，广为使用的自底向上的分析方法，它是经由算符优先方法变化而来的。这种方法特别有利于方法，它是经由算符优先方法变化而来的。这种方法特别有利于分析表达式。分析表达式。大家知道，在做算术式的四则运算时，为了保证计算过程和大家知道，在做算术式的四则运算时，为了保证计算过程和结果的唯一性，人们作了统一的四则运算规则的规定。这个法则结果的唯一性，人们作了统一的四则运算规则的规定。这个法则的主要方面就是规定运算符之间的优先顺序。即先乘除后加减，的主要方面就是规定运算符之间的

11、优先顺序。即先乘除后加减，同优先级的运算符先左后右（左结合律）。还有先括号内后括号同优先级的运算符先左后右（左结合律）。还有先括号内后括号外的规定。外的规定。而简单优先方法就是根据上述算术运算的计算原理而设计的而简单优先方法就是根据上述算术运算的计算原理而设计的一种语法分析方法。一种语法分析方法。这种方法的基本思想为：这种方法的基本思想为：首先规定文法符号之间的优先关系，然后再利用这种关系，首先规定文法符号之间的优先关系，然后再利用这种关系，通过比较句型中两个相邻的符号之间的优先关系来确定句型的通过比较句型中两个相邻的符号之间的优先关系来确定句型的“句柄句柄”并进行归约。并进行归约。二、相邻关

12、系：二、相邻关系：设设Si和和Sj是文法是文法G G的任意两个符号，那么它们在句型中可相的任意两个符号，那么它们在句型中可相邻出现的充要条件是必须满足下列条件之一：邻出现的充要条件是必须满足下列条件之一：1 1、有形如、有形如 U U SiSj的产生式的产生式2 2、有形如、有形如 U USiWW的产生式，且有的产生式，且有 W W Sj+3 3、有形如、有形如 U UV VSj的产生式，且有的产生式，且有 V V Si+4 4、有形如、有形如 U UVWVW的产生式，且有的产生式，且有 V V Si和和W W Sj+1 1、有形如、有形如 U U SiSj的产生式的产生式U U SiSj S

13、USiSj图图6.1采用采用U US Si iS Sj j的推导的推导+SjU U SiW 图图6.2采用采用U US Si iW W的推导的推导2 2、有形如、有形如 U USiWW的产生式，且有的产生式，且有 W W Sj+SUSiWSiSj+SiU U VSj 图图6.3采用采用U UV VS Sj j的推导的推导3 3、有形如、有形如 U UV VSj的产生式，且有的产生式，且有 V V Si+SUV VSjSiSj+SiU U VW Sj图图6.4采用采用U UVVW W的推导的推导4 4、有形如、有形如 U UVWVW的产生式，且有的产生式，且有V V Si和和W W Sj+SUV

14、 VWjSiSj+三、优先关系：三、优先关系：为了把上述条件加以形式化，引进三种优先关系。其定义如下：为了把上述条件加以形式化，引进三种优先关系。其定义如下：当且仅当当且仅当存在形如下面的产生式存在形如下面的产生式U U SiSj SiSiSjSj当且仅当当且仅当存在形如下面的产生式存在形如下面的产生式U USiW W的生产式，的生产式，且且有有 W W SjSiSiSjSj+当且仅当存在形如下面的产生式当且仅当存在形如下面的产生式U UVWVW的生产式的生产式,且有且有 V V Si和和W W SjSiSiSjSj+*在实际使用这些优先关系去识别句子时，我们希望采用一种在实际使用这些优先关系

15、去识别句子时，我们希望采用一种简洁的方法去表示这些关系，优先关系矩阵是一种常用的方式。简洁的方法去表示这些关系，优先关系矩阵是一种常用的方式。其其定义为：定义为：例：设有文法例：设有文法G Gz：Z Z bMbbMb M Ma a(L(L L LMa)Ma)则可则可根据定义求出其优先矩阵来（如下根据定义求出其优先矩阵来（如下）M MSiSi，SjSj=空空当当 SiSi与与SjSj无关系无关系(不相邻出现不相邻出现)时时当当 SiSiSjSj当当 SiSiSjSj当当 SiSiSjSj优先关系矩阵优先关系矩阵：Z Z bMbbMb M Ma a(L (L L LMa)Ma)Z Zb b M M

16、 b ba aZ Zb b M M b b(L LZ Zb b M M b b(L LM M a a)=a(=bL=MZZMLb(a).=.?构造优先矩阵的一种简便方法：构造优先矩阵的一种简便方法：STEP1对每个非终极符对每个非终极符W求下面两种集合：求下面两种集合：STEP2对每个符号对对每个符号对Si,Sj填写优先关系矩阵元素填写优先关系矩阵元素(其中其中W,VVN):ZMLHEADb(,aM,(,aLASTb),L,a)如对如对Ga我们有：我们有：Z Z bMbbMb M Ma a(L (L L LMa)Ma)MSi,Sj=，如果有如果有U USiW且且SjHEAD(W)MSi,Sj=

17、，如果有，如果有U UVW ,且有且有SiLAST(V)和和SjHEAD(W)WMSi,Sj=，如果有如果有U U SiSj HEAD(W)=SW S,S(VNUVT)LAST(W)=SWS,S(VNUVT)+四、简单优先文法的分析方法：四、简单优先文法的分析方法：1 1、简单优先文法的定义：、简单优先文法的定义：定义：满足下面两个条件的文法称为简单优先文法：定义：满足下面两个条件的文法称为简单优先文法：(1)(1)任意两个符号至多成立一种优先关系。任意两个符号至多成立一种优先关系。(2)(2)任意两个产生式具有不同右部。任意两个产生式具有不同右部。为了处理方便，引进特殊符号为了处理方便，引进

18、特殊符号#，并定义，并定义#S，S#(SVNUVT)2 2、简单优先文法的句柄、简单优先文法的句柄这个定理给我们提供确定句柄的一种方法。这个定理给我们提供确定句柄的一种方法。简单优先文法分析算法的主要思想是找出句柄并归纳之。简单优先文法分析算法的主要思想是找出句柄并归纳之。而给定一个句型而给定一个句型X，寻找它的句柄是这样进行的：从左向右进寻找它的句柄是这样进行的：从左向右进行扫描，每次只查看两个相邻的文法符号，并由此得知什么时候行扫描，每次只查看两个相邻的文法符号，并由此得知什么时候查到句柄的尾查到句柄的尾Sj，然后再返过头来向句型左端进行加工，仍然只然后再返过头来向句型左端进行加工，仍然只

19、查看相邻的两个运算符，找出句柄的头查看相邻的两个运算符，找出句柄的头Si。此时就可以进行归约此时就可以进行归约了。了。定理：设定理：设S1S2Sn是简单优先文法的规范句型，其子串是简单优先文法的规范句型，其子串SiSi+1Sj是满足下列条件的最左子串：是满足下列条件的最左子串：则则SiSi+1Sj定是定是S1S2Sn的句柄的句柄。证明：略证明：略。Si-1SiSiSi+1Si+2=SjSjSj+13 3、分析算法的要点：、分析算法的要点：STEP3:用用SiSi+1Sj去查产生式表的右部，并用相应的左去查产生式表的右部，并用相应的左部符号代替部符号代替(归约归约)句柄句柄SiSj，若查不到，则

20、为出错若查不到，则为出错。STEP4：重复上述过程，直至归约完为止。重复上述过程，直至归约完为止。STEP2：从：从Sj开始往回开始往回(左左)找第一个使找第一个使Si-1Si的的SiSTEP1：找出第一个使找出第一个使SjSj+1的的Sj4 4、语法分析程序：语法分析程序：首先设置保存句型前端的首先设置保存句型前端的S S栈和输入串后端的栈和输入串后端的T T队列；队列；,然后用然后用Sj1,Sj1+1,Si去查生产式表，去查生产式表，若查到有若查到有相同右部的产生式即相同右部的产生式即U USj1,Sj1+1,Si,则则从栈中退掉子串从栈中退掉子串Sj1,Sj1+1,Si，并把并把U进栈；

21、然后转进栈；然后转(2)。若查不到转出错处理。若查不到转出错处理。(5)(5)若若T(j)=#,并且并且S栈的内容为栈的内容为#Z(Z为文法开始符号为文法开始符号)则正确停则正确停机。否则，出错停机。机。否则，出错停机。(1)(1)置初始状态：置初始状态：S(1):=#,i:=1,j:=1(2)(2)若若 S(i)与与T(j)无任何关系，则出错停机。无任何关系，则出错停机。(3)(3)若若 S(i)S(i)T(j)T(j)或或S(i)S(i)T(j)T(j)，则把则把T(j)T(j)送入送入S S栈中，读下栈中，读下一符，转（一符，转（2 2）。）。(4)(4)若若S(i)T(j)则从则从S

22、S栈顶开始往前栈串栈顶开始往前栈串Sj1,Sj1+1,Si其中其中 Sj1为第一个使为第一个使Sj1-1Sj1此五部分是语法分析所涉及到的几部分此五部分是语法分析所涉及到的几部分 分析栈和输入流中的内容合起来表示当前被归约的分析栈和输入流中的内容合起来表示当前被归约的句型，每步的动作将由栈顶符号和当前的输入符的优先句型，每步的动作将由栈顶符号和当前的输入符的优先关系矩阵来确定，如果两种符号之间不存在优先关系，关系矩阵来确定，如果两种符号之间不存在优先关系，则表示输入符是错误的；而产生式表则用来确定归约时则表示输入符是错误的；而产生式表则用来确定归约时应选用的产生式。应选用的产生式。分析栈分析栈

23、S SS Si i输入流输入流T Tj j语法分析程序语法分析程序优先关系矩阵优先关系矩阵产生式表产生式表6.3 6.3 算符优先分析算符优先分析 算算符符优优先先分分析析的的基基本本思思想想是是只只规规定定算算符符(广广义义为为终终结结符符)之之间间的的优优先先关关系系，也也就就是是只只考考虑虑终终结结符符之之间间的的优优先先关关系系，不不考考虑虑非非终终结结符符之之间间的的优优先先关关系系。在在归归约约过过程程中中只只要要找找到到可可归归约约串串就就归归约约，并并不不考考虑虑归归约约到到那那个个非非终终结结符符名名，算算符符优优先先分分析析的的可可归归约约串串不不一一定定是是规规范范句句型

24、型的的句句柄柄，所所以以算算符符优优先先归归约约不不是是规规范范归归约约。算算符符优优先先分分析析的的可可归归约约串串是是当当前前符符号号栈栈中中的的符符号号和和剩剩余余的的输输入入符号构成句型的最左素短语符号构成句型的最左素短语。例例6.4:6.4:若有文法若有文法G G为：为：(1)(1)EE+EEE+E(2)(2)EE*EEE*E(3)(3)EiEi(4)(4)考察对输入串考察对输入串i i1 1+i+i2 2*i*i3 3的归约过程。的归约过程。解：解：归约归约过程见分析过程表过程见分析过程表6.36.3：P106P106页页 在分析到第在分析到第6 6步步时时，栈顶栈顶的符号串的符号

25、串为为E+EE+E，若只从移若只从移进进-归约归约的角度的角度讲讲，栈顶栈顶已出已出现现了了产产生式生式(1)(1)的右部，可以的右部，可以进进行行归约归约，但，但从通常四从通常四则则运算的运算的习惯习惯来看来看应应先乘后加，所以先乘后加，所以应应移移进进，这这就提就提出了算符出了算符优优先的先的问题问题。例例6.5:6.5:下面给出一个表达式的文法为：下面给出一个表达式的文法为：EE+E|EEE+E|EE|E*E|E/E|EE|(E)|iE|E*E|E/E|EE|(E)|i 本本文文法法是是二二义义性性的的，由由于于人人为为地地规规定定了了算算符符之之间间的的优优先先级级别别和和同同一一个个

26、级级别别中中的的结结合合性性质质，所所以以可可能能构构造造出出确确定定的的分分析析过过程。程。我们可以对此表达式的文法按公认的计算顺序规定优先级和我们可以对此表达式的文法按公认的计算顺序规定优先级和结合性如下：结合性如下：优先级最高。遵循右结合。优先级最高。遵循右结合。*,/,/优先级其次。服从左结合。优先级其次。服从左结合。+，-优先级最低。服从左结合。优先级最低。服从左结合。对对(，)规定括号的优先性大于括号外的运算符，小于括规定括号的优先性大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号。对于句子括号号内的运算符，内括号的优先性大于外括号。对于句子括号#号规定与它相邻的任

27、何运算符的优先性都比它大。此外，对运算号规定与它相邻的任何运算符的优先性都比它大。此外，对运算对象的终结符对象的终结符i i其优先级最高。其优先级最高。综上所述，我们可对表达式运算符的优先关系构造如表综上所述，我们可对表达式运算符的优先关系构造如表6.46.4。表表 6.4 6.4 算符优先关系表算符优先关系表#i)(/*-+#i)(/*-+很显然所给表达式文法是二义性的，但我们人为直观地给很显然所给表达式文法是二义性的，但我们人为直观地给出运算符之间的优先关系，由优先关系表出运算符之间的优先关系，由优先关系表6.46.4可知这种优先关可知这种优先关系是唯一的，有了这个优先关系表我们对前面表达

28、式的输入串系是唯一的，有了这个优先关系表我们对前面表达式的输入串i i1 1+i+i2 2*i*i3 3归约过程就能唯一确定了，也就是说在表归约过程就能唯一确定了，也就是说在表6.36.3分析到第分析到第6 6）步时，栈中出现了）步时，栈中出现了#E+E#E+E，可归约为可归约为E E，但当前输入符为但当前输入符为*，由于规定，由于规定 +*，所以应移进。，所以应移进。这里只简单介绍直观算符优先分析法，仅仅是为了易于这里只简单介绍直观算符优先分析法，仅仅是为了易于理解算符优先分析法的概念，后面将介绍对任意给定的一个理解算符优先分析法的概念，后面将介绍对任意给定的一个文法如何按形式算法的规则计算

29、算符之间的优先关系。文法如何按形式算法的规则计算算符之间的优先关系。6.3.1 6.3.1 算符优先文法及优先表构造算符优先文法及优先表构造一、算符文法的定义一、算符文法的定义算符文法算符文法定义定义6.26.2：设设有一文法有一文法G G，如果如果G G中没有形如中没有形如AABCBC的的产产生式，其生式，其中中B B和和C C为为非非终结终结符，符，则则称称G G为为算符文法算符文法(OperaterOperater Grammar)Grammar)也也称称OGOG文法。文法。例如：表达式文法例如：表达式文法EE+E|E*E|(E)|iEE+E|E*E|(E)|i其中任何一个其中任何一个产

30、产生式中都不包含两个非生式中都不包含两个非终结终结符相符相邻邻的情况，的情况，因此因此该该文法是算符文法。文法是算符文法。算符文法有如下两个性算符文法有如下两个性质质：性质性质1 1：在算符文法中任何句型都不包含两个相邻的非终结符。在算符文法中任何句型都不包含两个相邻的非终结符。性性质质2 2：如果如果AbAb或或(bAbA)出出现现在算符文法的句型在算符文法的句型中，其中中，其中A AV VN N ，b bV VT T，则则中任何含中任何含b b的短的短语语必含有必含有A A。二、算符优先关系的定义二、算符优先关系的定义由定义由定义6.36.3可有如下推论：可有如下推论：a)a)若若有有产产

31、生生式式AaAa或或ABaABa 则则aFIRSTVT(A)aFIRSTVT(A)，其其中中A A、B B为为非非终终结结符，符，a a为终结符。为终结符。b)b)若若aaFIRSTVT(B)FIRSTVT(B)且有产生式且有产生式ABAB则有则有aaFIRSTVT(A)FIRSTVT(A)。定义定义6.3:6.3:设设G G是是一一个个不不含含产产生生式式的的算算符符文文法法，a a和和b b是是任任意意两两个个终终结结符符，A A、B B、C C是是非非终结符，算符优先关系终结符，算符优先关系、定义如下定义如下 ：a a b b当且仅当当且仅当G G中含有形如中含有形如AAabab或或AA

32、aBbaBb的产生式的产生式 a ab b当且仅当当且仅当G G中含有形如中含有形如AAaBaB的产生式，且的产生式，且B+B+推导推导b b 或或 B+B+推导推导CbCb a ab b当且当且仅仅当当G G中含有形如中含有形如AABbBb的的产产生式，且生式，且B+B+推推导导a a 或或 B+B+推推导导aCaC三、算符优先文法的定义三、算符优先文法的定义结论结论：算符：算符优优先文法是无二先文法是无二义义性的。性的。算符算符优优先文法先文法定义定义6.4 6.4：设设有一不含有一不含产产生式的算符文法生式的算符文法G G，如果如果对对任意两个任意两个终结终结符符对对a a，b b之之间

33、间至多只有至多只有、和和 三种关系中的一种成立，三种关系中的一种成立，则则称称G G是一个算符是一个算符优优先文法。先文法。(Operator Precedence Grammar)(Operator Precedence Grammar)即即OPGOPG文法。文法。四、算符优先关系表的构造四、算符优先关系表的构造由由定定义义6.36.3我我们们可可计计算算出出给给定定的的算算符符文文法法中中任任何何两两个个终终结结符符对对(a,b)(a,b)之之间间的的优优先关系，其算法如下：先关系，其算法如下：首先定首先定义义如下两个集合：如下两个集合：FIRSTVT(B)=b|B bFIRSTVT(B)

34、=b|B b 或或 B B CbCb LASTVT(B)=a|B LASTVT(B)=a|B a a 或或 B B aCaC +三种优先关系的计算为：三种优先关系的计算为：a)a)关系关系:可直接查看产生式的右部，对如下形式的产生式可直接查看产生式的右部，对如下形式的产生式AAabab,A,AaBbaBb有有a a b b成成 立。立。b)b)关系关系:求出每个非终结符求出每个非终结符B B的的FIRSTVT(B)FIRSTVT(B)，在如下形式的产生式在如下形式的产生式AAaBaB 中，对每一中，对每一 bFIRSTVT(B),bFIRSTVT(B),有有a ab b成立。成立。c)c)关系

35、关系:计算每个非终结符计算每个非终结符B B的的LASTVT(B)LASTVT(B)，在如下形式的产生式在如下形式的产生式AABbBb 中，中，对对每一每一a aLASTVT(B)LASTVT(B)，有，有a ab b成立。成立。例例6.56.5：现现在可用上述算法在可用上述算法计计算下列表达式文法的算符算下列表达式文法的算符优优先关系。先关系。若有表达式文法为：若有表达式文法为：(0)(0)E#E#E#E#(1)(1)EE+T EE+T (2)(2)ET ET (3)(3)TT*F TT*F (4)(4)TFTF (5)(5)FPF|P (6)FPF|P (6)P(E)P(E)(7)Pi(7

36、)Pi 解：计算表达式文法的优先关系为：解：计算表达式文法的优先关系为：a)a)关系关系由产生式由产生式(0)E#E#(0)E#E#和和(6)P(E),(6)P(E),可得可得#，（）成立。成立。为为了了求求和和关关系系 ，需需先先由由定定义义6.26.2计计算算每每个个非非终终结结符符的的FIRSTVTFIRSTVT集集合合和和LASTVTLASTVT集合，结果为：集合，结果为：FIRSTVT(E)=#FIRSTVT(E)=#FIRSTVT(E)=+FIRSTVT(E)=+，*，(，iiFIRSTVT(T)=*FIRSTVT(T)=*，(，iiFIRSTVT(F)=,(FIRSTVT(F)=

37、,(，iiFIRSTVT(P)=(FIRSTVT(P)=(，iiLASTVT(E)=#LASTVT(E)=#LASTVT(E)=+LASTVT(E)=+，*，)，iiLASTVT(T)=*LASTVT(T)=*，)，iiLASTVT(F)=LASTVT(F)=，)，iiLASTVT(P)=)LASTVT(P)=)，ii 在在计计算每个非算每个非终结终结符的符的FIRSTVTFIRSTVT集合和集合和LASTVTLASTVT集合集合时时，可先考，可先考虑虑文法中文法中含有含有ETET，TFTF，FPFP形式的形式的产产生式，由定生式，由定义义6.36.3的推的推论论可知可知P P的的FIRSTV

38、TFIRSTVT集集合和合和LASTVTLASTVT集合也属于集合也属于F F的的FIRSTVTFIRSTVT集合和集合和LASTVTLASTVT集合，同集合，同样样F F的也属于的也属于T T的，的，T T的也属于的也属于E E的。集合中的其它元素可根据定的。集合中的其它元素可根据定义义由由产产生式直接生式直接计计算。算。然然后后逐逐条条扫扫描描产产生生式式寻寻找找终终结结符符在在前前非非终终结结符符在在后后的的相相邻邻符符号号对对和和非非终终结结符符在在前终结符在后的相邻符号对，即产生式右部有形如前终结符在后的相邻符号对，即产生式右部有形如AAaBaB 和和 AABbBb 的的产产生式。生

39、式。b)b)关系：关系：对所给表达式文法中终结符在前非终结符在后的相邻符号对对所给表达式文法中终结符在前非终结符在后的相邻符号对有：有：#E#E 则有：则有：#FIRSTVT(E)FIRSTVT(E)+T+T 则有：则有：+FIRSTVT(T)FIRSTVT(T)*F F 则有：则有：*FIRSTVT(F)FIRSTVT(F)F F 则有：则有：FIRSTVT(F)FIRSTVT(F)(E(E 则有：则有：(FIRSTVT(E)FIRSTVT(E)c)c)关系：对表达式文法中非终结符在前终结符在后的相邻符号对有：关系：对表达式文法中非终结符在前终结符在后的相邻符号对有：E#E#则有：则有：LASTVT(E)LASTVT(E)#E+E+则有：则有：LASTVT(E)LASTVT(E)+T*T*则有：则有：LASTVT(T)LASTVT(T)*P P 则有：则有：LASTVT(P)LASTVT(P)E)E)则有：则有：LASTVT(E)LASTVT(E)从而可以构造优先关系矩阵为表从而可以构造优先关系矩阵为表6.56.5。表表6.5 6.5 表达式文法算符优先关系表表达式文法算符优先关系表#)(i*+#)(i*+本本章章作作业业P122：1#(1)(2)