《6 第六章自底向上优先分析.ppt》由会员分享，可在线阅读，更多相关《6 第六章自底向上优先分析.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第六章第六章 自底向上优先分析法自底向上优先分析法学习目标：学习目标：掌掌握握：构构造造算算符符优优先先关关系系表表，进进行行算算符符优先分析，构造优先函数优先分析，构造优先函数理解：理解：算符优先文法，最左素短语算符优先文法，最左素短语了解：简单优先分析法了解：简单优先分析法6.1 自底向上分析方法概述自底向上分析方法概述6.2 自底向上优先分析方法概述自底向上优先分析方法概述6.3 算符优先分析法算符优先分析法6.1 自底向上分析方法概述自底向上分析方法概述1.1.基本思想基本思想从从输输入入符符号号串串开开始始，利利用用文文法法的的产产生生式式逐逐步步进进行行归约，试图归约到文法开始符归
2、约，试图归约到文法开始符从从语语法法树树角角度度看看，是是以以输输入入符符号号串串作作为为语语法法树树的的末末端端结结点点符符号号串串，自自底底向向上上的的构构造造语语法法树树，使使文文法法开开始始符符正正好好是是该该语语法法树树的的根根。如如果果最最终终根根结结点点是是开开始始符符，则则输输入入符符号号串串是是语语言言的的一一个个句句子子，否否则不是。则不是。自自底底向向上上分分析析过过程程实实际际上上是是一一个个不不断断进进行行直直接接归归约的过程。约的过程。2.遇到的问题遇到的问题如何找出进行直接归约的如何找出进行直接归约的“可归约串可归约串”（句柄）（句柄）3.3.基本实现方法基本实现
3、方法“移进归约移进归约”方法方法引进一个先进后出的符号栈来存放符号引进一个先进后出的符号栈来存放符号对对输输入入符符号号串串自自左左向向右右进进行行扫扫描描，并并把把当当前前输入符号下推入栈中（输入符号下推入栈中（移进移进），），边边移移进进边边分分析析，一一旦旦栈栈顶顶符符号号串串形形成成某某个个句句型型的的句句柄柄（为为某某产产生生式式的的右右部部）时时，就就用用相相应应的的非非终终结结符符（产产生生式式的的左左部部）替替换换它它(归归约约)。重重复复这这一一过过程程，直直到到输输入入符符号号串串的的末末端端，此此时时如如果果栈栈中中只只剩剩文文法法开开始始符符号号，则则输输入入符符号号串
4、是文法的句子，否则不是。串是文法的句子，否则不是。规范归约：规范归约：自底向上分析的移进归约过程是自顶向下最右自底向上分析的移进归约过程是自顶向下最右推导的逆过程，因为最右推导为规范推导，所以推导的逆过程，因为最右推导为规范推导，所以自左向右的归约称为规范归约。自左向右的归约称为规范归约。例例 文法：文法：(1)SaAcBe (2)Ab (3)AAb (4)Bd 输入串输入串abbcde#的最右推导的过程为：的最右推导的过程为：S=aAcBe=aAcde=aAbcde=abbcde自底向上分析的过程为：自底向上分析的过程为：abbcde|-aAbcde|-aAcde|-aAcBe|-S例例 文
5、法：文法：(1)SaAcBe (2)Ab (3)AAb (4)Bd 判断输入串判断输入串abbcde#是否为该文法的句子是否为该文法的句子用符号栈对输入符号串自底向上的分析过程为：用符号栈对输入符号串自底向上的分析过程为：归约（归约（SaAcBe）#aAcBe10）接受接受#S11）移进移进ee#aAcB9）归约（归约（Bd）e#aAcd8）移进移进dde#aAc7）归约（归约（AAb）cde#aAb5）移进移进ccde#aA6）移进移进bbcde#aA4）归约（归约（Ab）bcde#ab3）移进移进bbbcde#a2）移进移进aabbcde#1）动作动作输入符号串输入符号串符号栈符号栈步骤步
6、骤关键问题关键问题：如何在分析的过程中确定句柄如何在分析的过程中确定句柄何时移进？栈顶末形成句柄何时移进？栈顶末形成句柄何时归约？栈顶形成句柄何时归约？栈顶形成句柄常用自底向上分析法：常用自底向上分析法：算符优先分析法（算符优先分析法（6.3）LR类分析法（第类分析法（第7章）章）6.2 自底向上优先分析法概述自底向上优先分析法概述优先分析法两类：优先分析法两类：简单优先分析法简单优先分析法基基本本思思想想：按按一一定定原原则则定定义义文文法法中中所所有有符符号号（终终结结符符和和非非终终结结符符）之之间间的的优优先先关关系系，按按照照这种关系确定归约过程中的句柄并实行归约。这种关系确定归约过
7、程中的句柄并实行归约。是一种规范归约。是一种规范归约。简简单单优优先先分分析析法法准准确确、规规范范，但但效效率率低低，不不实实用，不介绍。用，不介绍。算符优先分析法算符优先分析法基基本本思思想想：只只定定义义文文法法中中终终结结符符之之间间的的优优先先关关系系（不不考考虑虑非非终终结结符符），并并由由这这种种关关系系指指导分析过程导分析过程不是规范归约不是规范归约算算符符优优先先分分析析法法分分析析速速度度快快，特特别别适适用用于于表表达达式式的的分分析析。缺缺点点是是不不规规范范，常常常常要要采采用用适适当措施克服其缺点。当措施克服其缺点。6.3 算符优先分析法算符优先分析法算符优先分析法
8、特别适用于表达式的分析算符优先分析法特别适用于表达式的分析从表达式得到的启发：从表达式得到的启发：表达式的归约顺序与运算顺序是一样的表达式的归约顺序与运算顺序是一样的通常算术表达式的运算次序是先乘除后加减，同通常算术表达式的运算次序是先乘除后加减，同优先级时服从左结合优先级时服从左结合EE+T|TTTF|FF(E)|i符号串符号串E+T+TF的归约过程为：的归约过程为：E+T+TF|-E+TF|-E+T|-E运算次序只与运算符（优先级，结合性）有关，运算次序只与运算符（优先级，结合性）有关，与运算对象无关与运算对象无关可以根据运算符（终结符）的优先关系指导归可以根据运算符（终结符）的优先关系指
9、导归约过程，与运算对象（非终结符）无关约过程，与运算对象（非终结符）无关6.3.1 优先关系优先关系6.3.2 算符优先文法的定义算符优先文法的定义6.3.3 算符优先关系表的构造算符优先关系表的构造6.3.4 算符优先分析算法算符优先分析算法6.3.5 优先函数优先函数6.3.6 算符优先分析法的局限性算符优先分析法的局限性6.3.1 优先关系优先关系优先关系只存在于句型中相邻出现的符号优先关系只存在于句型中相邻出现的符号相相邻邻：算算符符优优先先分分析析法法只只考考虑虑终终结结符符之之间间的的优优先先关关系系，不不考考虑虑非非终终结结符符，所所以以两两个个终终结结符符相相邻邻指指其中没有其
10、他的终结符（但可以有非终结符）其中没有其他的终结符（但可以有非终结符）如：如：E+Ti，和和相邻，相邻，和和i相邻，相邻，但和但和i不相邻不相邻终结符间优先关系表示：终结符间优先关系表示：终结符终结符a和和b之间的优先关系表示如下：之间的优先关系表示如下：ab 表示表示a的优先级高于的优先级高于b优先关系定义的依据优先关系定义的依据在在当当前前句句柄柄中中的的符符号号优优先先于于与与其其相相邻邻的的不不在在句句柄柄中的符号被归约，其优先关系大中的符号被归约，其优先关系大同同一一句句柄柄中中的的相相邻邻符符号号同同时时被被归归约约，其其优优先先关关系系相同相同不可能相邻出现在任何句型中的两个符号
11、，无法比不可能相邻出现在任何句型中的两个符号，无法比较其归约的先后，故它们之间无优先关系较其归约的先后，故它们之间无优先关系EE+T|TTTF|FF(E)|iEE+TTF(E)句型句型(E)+T的句柄的句柄是是(E),所以所以)+(=)注注意意：是是三三种种有有序序关关系系，与与数数学学中中的的不同，所以不同，所以a=b不意味不意味b=a，ab不意味不意味b+，在，在(E+T)中得中得+)按公认的计算顺序规定优先级和结合性，得到优先关系如下：按公认的计算顺序规定优先级和结合性，得到优先关系如下：,/的优先级高，遵循左结合，得的优先级高，遵循左结合，得,/,/,/+,-的优先级低的优先级低，遵循
12、左结合，得遵循左结合，得+,+-,-,+(,)规定括号的优先级大于括号外的运算符，小于括号内的规定括号的优先级大于括号外的运算符，小于括号内的运算符，如运算符，如E+(E+T)，有有+(，(+规定规定:#运算对象运算对象i的优先级最高的优先级最高优先关系表如右图所示：优先关系表如右图所示：+（）i#+(=i#=说明：表中为空的元素表示：在该说明：表中为空的元素表示：在该文法的任何句型中都不会出现这两文法的任何句型中都不会出现这两个终结符相邻，所以他们无优先关个终结符相邻，所以他们无优先关系，如不会有这样的表达式系，如不会有这样的表达式)i算符优先分析法算符优先分析法1 文法要满足一定的条件，即
13、为文法要满足一定的条件，即为算符优先文法算符优先文法2 根据文法按一定规则计算算符之间的根据文法按一定规则计算算符之间的优先关系优先关系3 按优先关系进行按优先关系进行算符优先分析算符优先分析6.3.2 算符优先文法的定义算符优先文法的定义1.算符文法算符文法定义：定义：设有上下文无关文法设有上下文无关文法 G，如果如果G中产生式的右部中产生式的右部没有两个非终结符相连，则称没有两个非终结符相连，则称G为算符文法为算符文法（Operater Grammar），），也称也称OG文法文法例如：例如：表达式文法表达式文法 EE+E|EE|(E)|i 是算符文法是算符文法性质：性质：1.在算符文法中任
14、何句型都不包含两个相连的非在算符文法中任何句型都不包含两个相连的非终结符。终结符。2.如果如果Ab或或bA出现在算符文法的出现在算符文法的句型句型r中，其中，其中中A VN，b VT，则则r中任何含中任何含b的的短语短语必含有必含有A（含含A的短语不一定含有的短语不一定含有b）EE+TE+TTF句型句型E+T+TF短语有：短语有：E+TTFE+T+TF2.算符优先关系的定义算符优先关系的定义设设G是是一一个个不不含含产产生生式式的的算算符符文文法法，a和和b是是任任意意两两个个终终结结符符，A,B,C是是非非终终结结符符，算算符符优优先先关关系系定定义如下：义如下：1)a=b当且仅当当且仅当G
15、中有形如中有形如 Aab 或或 AaBb 的产生式。的产生式。说明：说明：为为或或B B，a，b在用一句柄中同时归约所以在用一句柄中同时归约所以优优先级相同先级相同abA例如：有产生式例如：有产生式F(E)所以所以(=)2)a+b 或或 B=+Cb说明：说明：为为或或C C，a，b不在同一句柄中，不在同一句柄中，b先归约，先归约，所以所以a的优先级低于的优先级低于b aBAPb文法文法EE+T|T TTF|F F(E)|i由由EE+T T=+TF得得+b4)当且仅当当且仅当G中有形如中有形如 ABb 的产生式，的产生式，5)且且 B=+a 或或 B=+aC 说明：说明：为为或或C C，a，b不
16、在同一句柄中，不在同一句柄中，a先归约，先归约，所以所以a的优先级大于的优先级大于bbBAPa文法文法EE+T|T TTF|F F(E)|i由由EE+T E=+TF得得+3.算符优先文法算符优先文法定义定义：设设有有一一不不含含产产生生式式的的算算符符文文法法G，如如果果对对任任意意两两个个终终结结符符对对a,b之之间间至至多多只只有有一一种种优优先先关关系系成成立立，则则称称G是是一一个个算算符符优优先先文文法法(Operater Precedence Grammar)，即即OPG文法。文法。说明：说明：两两个个终终结结符符之之间间的的优优先先关关系系是是有有序序的的，算算符符优优先先文文法
17、法允允许许ab，ba同同时时存存在在，而而不不允允许许有有ab，a)，)+同同时时存存在，不允许在，不允许+)和和+EE得得+E+E得得+和和的优先关系不唯一，所以不是算符优先文法的优先关系不唯一，所以不是算符优先文法包含优先级和结合性的表达式文法是算符优先文法包含优先级和结合性的表达式文法是算符优先文法EE+T|TTTF|FF(E)|i6.3.3 算符优先关系表的构造算符优先关系表的构造1.最左终结符集最左终结符集FIRSTVTFIRSTVT(B)=b|B=+b 或或 B=+Cb 其中其中b VT,B,C VN直直观观上上说说FIRSTVT(B)是是由由B推推导导出出的的最最左左终终结结符符
18、(允许左边有一非终结符允许左边有一非终结符)的集合。的集合。与与FIRST()=a VT|*a.对照对照文文法法符符号号串串 的的开开始始符符号号集集是是由由 推推导导出出的的开开头头的的终结符（包括终结符（包括）组成组成例文法：例文法：EE+T|TTTF|FF(E)|iFIRSTVT(F)=(，i FIRSTVT(T)=，(，i FIRSTVT(E)=+，(，i FIRST(F)=(，i FIRST(T)=(，i FIRST(E)=(，i 构造构造FIRSTVT(A)的算法的算法1)令每个非终结符的令每个非终结符的FIRSTVT集为空集为空2)依次扫描文法中的每条产生式，根据规则依次扫描文法
19、中的每条产生式，根据规则(a)(b)，求各非终结符的求各非终结符的FIRSTVT集集(a)若产生式若产生式Aa，或或ABa，则则a FIRSTVT(A)；(b)若有产生式若有产生式AB,且且a FIRSTVT(B)，则则a FIRSTVT(A)3)重复重复2)，直到每个，直到每个FIRSTVT集合都不发生变化为集合都不发生变化为止止例例文法：文法：EE+T|TTTF|FF(E)|i求各非终结符的求各非终结符的FIRSTVT集集(，i，(，i+,第三次第三次FTE(，i +第二次第二次(，i+第一次第一次初值初值第四次迭代的时候，第四次迭代的时候，E、T、F的的FIRSTVT集都不再发生变集都不
20、再发生变换，算法终止换，算法终止,(，i,(，i(a)若产生式若产生式Aa，或或ABa，则则a FIRSTVT(A)；(b)若有产生式若有产生式AB,且且a FIRSTVT(B)，则则a FIRSTVT(A)2.最右终结符集最右终结符集LASTVTLASTVT(B)=a|B=a 或或 B=aC其中其中a VT,B,C VN直直观观上上说说LASTVT(B)是是由由B推推导导出出的的最最右右终终结符结符(允许右边有一非终结符允许右边有一非终结符)的集合。的集合。例文法：例文法：EE+T|TTTF|FF(E)|iLASTVT(F)=)，iLASTVT(T)=，)，iLASTVT(E)=+，)，i构
21、造构造LASTVT(A)的算法的算法与构造与构造FIRSTVT(A)算算法相似法相似根据下面两条规则根据下面两条规则a)若产生式若产生式Aa，或或AaB，则则a LASTVT(A)b)若有产生式若有产生式AB，且且a LASTVT(B)，则则a LASTVT(A)例例文法：文法：EE+T|TTTF|FF(E)|i求各非终结符的求各非终结符的LASTVT集集)，i，)，i+,第三次第三次FTE)，i +第二次第二次)，i+第一次第一次初值初值第四次迭代的时候，第四次迭代的时候，E、T、F的的LASTVT集都不再发生变集都不再发生变换，算法终止换，算法终止,)，i,)，ia)若产生式若产生式Aa，
22、或或AaB，则则a LASTVT(A)b)若有产生式若有产生式AB，且且a LASTVT(B)，则则a LASTVT(A)3.优先关系的确定优先关系的确定(1)=关系：关系：查看产生式右部查看产生式右部，有形如有形如Aab或或AaBb 的产生式，则的产生式，则a=b例例E(E)，则有则有(=)(2)关系：关系：若有形如若有形如AaB 的产生式，对每个的产生式，对每个b FIRSTVT(B)，都有都有ab例例EE+T，FIRSTVT(T)=,i,(，则有则有+，+i，+关系：关系：若有形如若有形如ABb 的产生式，对每个的产生式，对每个a LASTVT(B)，都有都有ab例例EE+T，LASTV
23、T(E)=+,i,)，则有则有+，+，i+，)+4.构造构造算符优先关系表算法算符优先关系表算法逐条扫描文法中的每条产生式，按以下四种情况处理：逐条扫描文法中的每条产生式，按以下四种情况处理：1)对产生式右部对产生式右部终结符终结符相邻的符号对，即产生式右相邻的符号对，即产生式右部有形如部有形如Aab的符号对的符号对(a,b)，则则ab2)对产生式右部两对产生式右部两终结符终结符之间为一个之间为一个非终结符非终结符的符的符号对，即产生式右部有形如号对，即产生式右部有形如AaBb的符号对的符号对(a,b)，则则ab3)对产生式右部对产生式右部终结符终结符在前在前非终结符非终结符在后的相邻符在后的
24、相邻符号对，即产生式右部有形如号对，即产生式右部有形如AaB的符号对的符号对(a,B)，则则aa例例文法文法 EE+T|T TTF|F F(E)|iFIRSTVT（E）=+，i，(FIRSTVT（T）=，i，(FIRSTVT（F）=i，(LASTVT（E）=+,),i LASTVT（T）=,),i LASTVT（F）=),i 依次考察每个产生式的右部：依次考察每个产生式的右部：由由E+和和LASTVT(E)=+,),i得到：得到：+，+，)+，i+#+i)(#i)由由+T和和FIRSTVT(T)=,(,i得到：得到：+，+(，+i由由(E和和FIRSTVT(E)=+,(,i得到得到：(+，(，
25、(，(i=#+(+i)=，)，i由由F和和FIRSTVT(F)=(,i得到：得到：(，)，)，)，i)关于关于#的优先关系，可认为有产生式的优先关系，可认为有产生式E#E#而获得而获得#=#；由由E#，得得LASTVT(E)#,即：即：+#，#，)#，i#由由#E，得得#FIRSTVT(E)，即：即：#+，#，#i，#(根据算符优先关系表可以判断文法是否为算符根据算符优先关系表可以判断文法是否为算符优先文法优先文法=#+(+i)=(#i)文法文法 EE+T|T TTF|F F(E)|I的算符优先关系表为：的算符优先关系表为：优先关系表中无多重定义优先关系表中无多重定义此文法是算符优先文法此文法
26、是算符优先文法6.3.4 算符优先分析算法算符优先分析算法说明：说明：算符优先分析法的归约过程与规范归约不同算符优先分析法的归约过程与规范归约不同文法文法 EE+T|TTTF|FF(E)|i输入串输入串i+i的语法树：的语法树：EE+TTFiFii+i的规范归约：的规范归约：i+i|-F+i|-T+i|-E+i|-E+F|-E+T|-Ei+i的算符优先分析：的算符优先分析：i+i|-F+i|-F+F|-E当单个非终结符是句柄时，算符优先法无法确定该非终结符当单个非终结符是句柄时，算符优先法无法确定该非终结符为句柄为句柄算符优先法每次归约算符优先法每次归约最左素短语最左素短语而不是句柄而不是句柄
27、最左素短语的定义和确定方法是算符优先分析最左素短语的定义和确定方法是算符优先分析算法的关键。算法的关键。1.最左素短语的定义最左素短语的定义定义：定义：设设有有文文法法GS，其其句句型型的的素素短短语语是是一一个个短短语语，它它至至少少包包含含一一个个终终结结符符，并并除除自自身身外外不不包含其它素短语。包含其它素短语。最左边的素短语称为最左边的素短语称为最左素短语最左素短语。例例 文法：文法：EE+T|T TTF|F F(E)|i的一个句型为的一个句型为 T+TF+iETEETTTF+Fi短语为：短语为：T，TF，i，T+TF，T+TF+i素短语为：素短语为：TF，i最左素短语为：最左素短语
28、为：TF规范归约规范归约每次归约当前句型中的每次归约当前句型中的句柄句柄，上面句型的句柄是，上面句型的句柄是T算符优先分析算符优先分析每次归约当前句型的每次归约当前句型的最左素短语最左素短语，TF，去掉了去掉了单非终结符单非终结符的归约，因为若只有一个非终结符时，无法与句型的归约，因为若只有一个非终结符时，无法与句型中该非终结符的左部和右部的串比较优先关系，也就无法确定中该非终结符的左部和右部的串比较优先关系，也就无法确定该非终结符为句柄。该非终结符为句柄。2.最左素短语的确定最左素短语的确定最左素短语的形式为：最左素短语的形式为：NiaiNi+1ai+1.NjajNj+1 其中其中Nk(iK
29、 j+1)为为非终结符非终结符或或空空Ni和和Nj+1在短语中，这是因为算符文法的性质：在短语中，这是因为算符文法的性质：性质性质1：在算符文法中任何句型都不包含两个：在算符文法中任何句型都不包含两个相邻的非终结符相邻的非终结符性质性质2：如果：如果Ab（或或bA）出现在句型出现在句型r中，其中，其中中A VN，b VT，则则r中中任任何何含含b的的短语必含有短语必含有A最左素短语最左素短语NiaiNi+1ai+1.NjajNj+1 满足：满足：ai-1 aj+1 根据上述关系，可以构造出算符优先分析算法：根据上述关系，可以构造出算符优先分析算法：先利用关系先利用关系找到找到最左素短语的尾，再
30、利用关最左素短语的尾，再利用关系系找到最左素短语的头，从而确定最左素短语。找到最左素短语的头，从而确定最左素短语。4*(1+2*3)*(,(+,+)最左素短语最左素短语为为2*34.算符优先分析算法算符优先分析算法此算法用到一个符号栈此算法用到一个符号栈S，算法大意为：算法大意为：1)将输入符号串将输入符号串a1a2at依次逐个存入符号栈依次逐个存入符号栈S中，直至中，直至符号栈顶终结符符号栈顶终结符aj与当前输入符与当前输入符aj+1的关系为的关系为ajaj+1为为止；止；2)最左素短语尾已在符号栈最左素短语尾已在符号栈S的栈顶，由栈顶向下找最的栈顶，由栈顶向下找最左素短语的头符号左素短语的
31、头符号，即找到第一个即找到第一个关系关系ai-1 (=i#F+F6归约归约(Fi)#F+i5移进移进#i#F+4移进移进i#+#i2移进移进+i#i#(H+H7归约归约(Ha)#)#(H+a6移进移进)#a#(H+5移进移进a)#+#(a3移进移进+a)#a#(2移进移进a+a)#(=a+#(T)9移进移进#)=#(T8动作动作剩余输入串剩余输入串当前符号当前符号优先关系优先关系栈栈步骤步骤;()a+#;(=a+#a|(T)T-T,S|S(1)计算GS的FIRSTVT、LASTVT(2)改造算符优先关系表并说明GS是否算符优先文法(3)给出输入串（a,a）#的算符优先分析过程，判断其是否文法G的句子。