《ch6自底向上优先分析方法》由会员分享，可在线阅读，更多相关《ch6自底向上优先分析方法（72页珍藏版）》请在金锄头文库上搜索。
1、第六章自下而上优先分析法第六章自下而上优先分析法所有的所有的自下而上分析自下而上分析移进移进-归约法归约法的原理的原理.基本思想是用一个寄存文法符号的先进后出栈，将输入符号基本思想是用一个寄存文法符号的先进后出栈，将输入符号按从左到右扫描顺序逐个移入栈中，边移入边分析，一旦栈按从左到右扫描顺序逐个移入栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄或可归约串时（对应于某条规顶符号串形成某个句型的句柄或可归约串时（对应于某条规则右部）就进行一次归约，即用该规则左部非终结符则右部）就进行一次归约，即用该规则左部非终结符替换替换相相应规则右部符号串应规则右部符号串.重复这一过程直到整个输入串分析
2、完毕重复这一过程直到整个输入串分析完毕.最终若栈中剩下句子右界符最终若栈中剩下句子右界符“#”和文法的开始符号，和文法的开始符号，则所则所分析的输入符号串是文法的正确句子分析的输入符号串是文法的正确句子.否则否则,就不是正确的句就不是正确的句子，报告错误子，报告错误.1设设G=(VT,VN,S,P), (VT VN)*,A P,Aww归约的过程是，已知归约的过程是，已知w和产生式和产生式A，用产生式，用产生式A左部左部A替换替换w中的中的，得到符号串，得到符号串Aw.从输入符号串出发，每次从被归约的句型中找到一个产生式从输入符号串出发，每次从被归约的句型中找到一个产生式的右部，用其左部替换之，
3、得到新的句型，直至归约到文法的右部，用其左部替换之，得到新的句型，直至归约到文法的开始符号。的开始符号。归约归约2【例】文法【例】文法GS对输入串对输入串 abbcde# 进行语法分析，进行语法分析，检查该符号串是否是该文法的正确句子。检查该符号串是否是该文法的正确句子。SaAcBeSaAcBeA AbbAAbAAbBdBd3SaAcBeSaAcBe A Ab AAb Bdb AAb BdabbcdeabbcdeaAbcdeaAcdeaAcBeSAABS4从例子中可以看出，一个句型中当含有多个子串可以匹配不从例子中可以看出，一个句型中当含有多个子串可以匹配不同产生式的右部时，将有不同的归约过程
4、，究竟应该对谁先同产生式的右部时，将有不同的归约过程，究竟应该对谁先归约呢？归约呢？51.一个句型的最左直接短语称为该句型的一个句型的最左直接短语称为该句型的句柄句柄，句柄是规句柄是规范归约的可归约串范归约的可归约串。2.假定假定是文法是文法G的一个句子，称序列的一个句子，称序列n,n-1,n-2,0是是的一个的一个规范归约规范归约，如果此序列满足：如果此序列满足：1)n=；0为文法的开始符，即为文法的开始符，即0=S；2)对任何对任何i，0in,i-1是从是从i经经把句柄替换把句柄替换为相应为相应产生式的左部符号而得到的。产生式的左部符号而得到的。3.如果文法如果文法G是无二义的，规范归约是
5、最右推导的逆过程，是无二义的，规范归约是最右推导的逆过程，规范归约也称最左归约规范归约也称最左归约,最右推导也称规范推导最右推导也称规范推导。4.结论：结论：对规范句型来说，句柄的后面不会出现非终结符。对规范句型来说，句柄的后面不会出现非终结符。因此，因此，规范归约的实质规范归约的实质是在移进过程中，发现栈顶呈现是在移进过程中，发现栈顶呈现句柄时就用相应的产生式的左部符号进行替换。句柄时就用相应的产生式的左部符号进行替换。规范归约简述规范归约简述6对输入串对输入串abbcde的最右推导过程是：的最右推导过程是：SaAcBeaAcdeaAbcdeabbcde。用语法树表示如下图所示：用语法树表示
6、如下图所示：7用语法树表示规范归约用语法树表示规范归约过程如下图所示：过程如下图所示：它与最右推导的逆过程相对应。它与最右推导的逆过程相对应。8非形式地，一个符号串的非形式地，一个符号串的“句柄句柄”是和一个规则右部匹配的是和一个规则右部匹配的子串，而且把它归约到该规则左部的非终结符子串，而且把它归约到该规则左部的非终结符,代表了最右代表了最右推导逆过程的一步。推导逆过程的一步。句柄句柄找句柄是非常重要的找句柄是非常重要的在很多情况下，匹配某个规则在很多情况下，匹配某个规则A右部的最左输入子串右部的最左输入子串 不是句柄，因为用这个规则归约产生的串不能归约到开始符不是句柄，因为用这个规则归约产
7、生的串不能归约到开始符号。号。【例】对于串【例】对于串aAbcdeb是产生式是产生式Ab的右部的右部,但但b不是不是句柄。句柄。如果进行归约，得到如果进行归约，得到aAAcde，而，而aAAcde不能归约到不能归约到S.因此我们必须更精确地定义句柄。因此我们必须更精确地定义句柄。9形式的说，右句型形式的说，右句型(最右推导可得的句型最右推导可得的句型)的句柄是一个与的句柄是一个与规则规则A和和中的一个位置有关的，从这个位置开始往右可中的一个位置有关的，从这个位置开始往右可找到找到，用，用A代替代替得到得到最右推导的前一个右句型最右推导的前一个右句型，即，即如果如果S Aw w,那么，在那么，在
8、 后后是是 w的句柄。的句柄。句柄右侧的句柄右侧的w是是未读入的终结符号。未读入的终结符号。句柄句柄(续续)* rmrm10“移进一归约移进一归约”分析器使用一个栈和一个存放输入符号串分析器使用一个栈和一个存放输入符号串w的缓冲器。分析器的初始状态为的缓冲器。分析器的初始状态为:栈栈输入输入动作动作#w#工作过程：自左至右把串工作过程：自左至右把串w的符号一一移进栈里，一旦的符号一一移进栈里，一旦栈顶形成栈顶形成句柄句柄时，就进行归约。这种归约可能持续多次，直时，就进行归约。这种归约可能持续多次，直至栈顶不再呈现句柄为止。然后，继续向栈里移进符号，重至栈顶不再呈现句柄为止。然后，继续向栈里移进
9、符号，重复这个过程，直至最终形成如下格局：复这个过程，直至最终形成如下格局：栈栈输入输入#S#(分析成功接受分析成功接受)“移进移进- -归约归约”分析法的栈实现分析法的栈实现11符号栈符号栈输入串输入串动作动作初态初态#w#(移进、归约、出错移进、归约、出错)（中间过程）（中间过程）终态终态#S#(分析成功接受分析成功接受)符号栈的使用符号栈的使用12对符号栈的使用有对符号栈的使用有“移进移进”、“归约归约”、“接受接受”、“出错出错处理处理”等操作。等操作。1)“移进移进”是指在栈顶还没有形成可归约串时，把输入串是指在栈顶还没有形成可归约串时，把输入串的一个符号移进符号栈；的一个符号移进符
10、号栈；2)“归约归约”是指发现栈顶已形成可归约串，对其进行归约；是指发现栈顶已形成可归约串，对其进行归约；3)“接受接受”是指宣布分析成功，表明输入串是文法合法的是指宣布分析成功，表明输入串是文法合法的句子；句子；4)“出错处理出错处理”是指栈顶符号和要输入的符号在某种关系是指栈顶符号和要输入的符号在某种关系上出现矛盾，分析过程无法正常进行，通常此时要调用上出现矛盾，分析过程无法正常进行，通常此时要调用出错处理程序确定错误类型、校正错误，并使分析过程出错处理程序确定错误类型、校正错误，并使分析过程继续进行下去。继续进行下去。13还有一个非常重要的事实，还有一个非常重要的事实，任何可归约串的出现
11、必在栈顶任何可归约串的出现必在栈顶，不会在栈的内部。对规范归约而言，这个事实是明显的。不会在栈的内部。对规范归约而言，这个事实是明显的。规范归约是最左归约，这种规范归约是最左归约，这种“最左性最左性”保证可归约串一定在保证可归约串一定在栈顶。也正因为如此，先进后出栈在自下而上分析中是一种栈顶。也正因为如此，先进后出栈在自下而上分析中是一种非常重要的数据结构。非常重要的数据结构。146.1自下而上优先分析法概述自下而上优先分析法概述优先分析法有两种：优先分析法有两种：简简单单优优先先分分析析法法(规规范范归归约约)文文法法按按一定原则规定文法符号的优先关系一定原则规定文法符号的优先关系算符优先分
12、析法算符优先分析法(不规范归约不规范归约)规定规定算符之间的优先关系算符之间的优先关系简单优先分析法简单优先分析法:准确、规范，但效率较低，实际使用价值准确、规范，但效率较低，实际使用价值不大不大.算符优先分析法：分析速度快，适用于表达式分析，但归约算符优先分析法：分析速度快，适用于表达式分析，但归约不规范不规范.156.2简单优先分析法简单优先分析法简单优先分析法是按照文法符号的优先关系确定句柄简单优先分析法是按照文法符号的优先关系确定句柄.因此，在这种方法中的关键是确定文法符号间的优先关系因此，在这种方法中的关键是确定文法符号间的优先关系.1.优先关系优先关系(1)X=Y当且仅当当且仅当G
13、中存在产生式规则中存在产生式规则AXY(2)XXB，且且BY(3)XY当且仅当当且仅当G中存在产生式规则中存在产生式规则ABD，且且BX和和D=Y例例6.2见书见书P.105+*162.简单优先文法简单优先文法若一个文法满足：若一个文法满足：（1）在文法符号集）在文法符号集V中，任意两个符号之间最多只中，任意两个符号之间最多只有一种关系成立；有一种关系成立；（2）在文法中任意两个产生式没有相同的右部）在文法中任意两个产生式没有相同的右部.则这样的文法为简单优先文法则这样的文法为简单优先文法.173.简单优先分析法优先分析算法简单优先分析法优先分析算法（1）根据优先文法构造优先关系矩阵；）根据优
14、先文法构造优先关系矩阵；（2）存储文法产生式，并设符号栈）存储文法产生式，并设符号栈S；（3）将输入符号串）将输入符号串a1a2an#依次逐个存入符号栈依次逐个存入符号栈S中，直到中，直到遇到栈顶符号遇到栈顶符号ai的优先性的优先性下一个待输入符号下一个待输入符号aj时为止时为止.（4）栈顶当前符号）栈顶当前符号ai为句柄尾，由此向左在栈中找句柄的头符为句柄尾，由此向左在栈中找句柄的头符号号ak,即找到即找到ak-1ak为止为止.（5）由句柄）由句柄akai在文法的产生式中查找右部为在文法的产生式中查找右部为akai的产生式，的产生式，若找到则用相应左部代替句柄，若找不到则为出错，这时可若找到
15、则用相应左部代替句柄，若找不到则为出错，这时可断定输入串不是该文法的句子断定输入串不是该文法的句子.（6）重复（）重复（3）（）（5）直至归约完输入串，栈中只剩下文法的）直至归约完输入串，栈中只剩下文法的开始符号为止开始符号为止.186.3 6.3 算符优先分析法算符优先分析法算符优先分析法是一种简单、直观的自下而上分析法。特别算符优先分析法是一种简单、直观的自下而上分析法。特别适合分析程序语言中各类文法且宜于手工实现。适合分析程序语言中各类文法且宜于手工实现。196.3.1 6.3.1 方法概述方法概述算符优先分析法是一种简单、直观、广为使用的自下而上语算符优先分析法是一种简单、直观、广为使
16、用的自下而上语法分析方法，它是法分析方法，它是依据算术表达式的四则运算过程而设计依据算术表达式的四则运算过程而设计的的一种方法，也适用于对一般的高级语言程序的分析。算符优一种方法，也适用于对一般的高级语言程序的分析。算符优先分析法的基本思想是，首先先分析法的基本思想是，首先确定运算符（确切地说是终结确定运算符（确切地说是终结符）之间的优先关系和结合性质符）之间的优先关系和结合性质，然后借助这种关系，比较，然后借助这种关系，比较相邻运算符之间的优先级来确定句型的相邻运算符之间的优先级来确定句型的可归约串可归约串，并进行归，并进行归约。约。值得注意的是，算符优先分析过程虽然是值得注意的是，算符优先
17、分析过程虽然是自下而上归约自下而上归约过程，过程，但它的可归约串但它的可归约串未必是句柄未必是句柄，也就是说，算符优先分析过程，也就是说，算符优先分析过程不是一种规范归约。不是一种规范归约。20【例】文法【例】文法GEGE：EE+E | E*E | (E) | idEE+E | E*E | (E) | id这是一个二义性文法，对句子这是一个二义性文法，对句子id+id*id有两种不同的规有两种不同的规范归约，在规范过程中句型的句柄不唯一。范归约，在规范过程中句型的句柄不唯一。第一个规范归约过程第一个规范归约过程(1)id+id*id(2)E+id*id(3)E+E*id(4)E+E*E(5)E
18、+E(6)E第二个规范归约过程第二个规范归约过程(1)id+id*id(2)E+id*id(3)E+E*id(4)E*id(5)E*E(6)Eid是句柄是句柄E+E是句柄是句柄此现象是由于没有定义运算符此现象是由于没有定义运算符+和和*的优先关系而引起的。的优先关系而引起的。在归约过程中起决定作用的是相邻两个终结符符号之间的优在归约过程中起决定作用的是相邻两个终结符符号之间的优先关系。先关系。21任何两个相邻终结符任何两个相邻终结符a和和b之间的优先关系有三种：之间的优先关系有三种：aba的优先级高于的优先级高于ba=ba的优先级等于的优先级等于b相邻终结符号的优先关系相邻终结符号的优先关系注
19、意：优先关系与出现的左右次序有关。注意：优先关系与出现的左右次序有关。aaa=b不一定有不一定有b=a例：例：表达式中表达式中运算符运算符运算符运算符的优先关系有的优先关系有+.-,但没有但没有-1， n-1满足性质满足性质1。若若 n-1 A ，A为非终结符。由假设的为非终结符。由假设的 的尾符号和的尾符号和 的首的首符号都不是非终结符，否则与假设矛盾。符号都不是非终结符，否则与假设矛盾。又若又若A是文法的规则，则有是文法的规则，则有 n-1 n= 而而A是文法的规则，它不含两个相邻非终结符，所是文法的规则，它不含两个相邻非终结符，所以以 也不含两个相邻的非终结符，满足性质也不含两个相邻的非
20、终结符，满足性质1。*证明：用归纳法证明：用归纳法设设 是句子，是句子，S，即，即S01.n-1n 25性质性质2：若：若Ab或或bA出现在算符文法的句型出现在算符文法的句型 中，其中中，其中A VN,b VT,则则 中任何含中任何含b的短语必包含的短语必包含A.证明：用反证法。证明：用反证法。由算符文法的性质由算符文法的性质1可知。可知。S bA 若存在若存在B b，这时，这时b和和A不同时归约，分属于不同的不同时归约，分属于不同的短语，短语，则必有则必有SBA ，这样在句型，这样在句型BA 中，存在相邻的非终结中，存在相邻的非终结符，所以与性质符，所以与性质1矛盾。矛盾。故：故： 中任何含
21、中任何含b的短语必包含的短语必包含A，证毕。，证毕。*注意：含注意：含b的短语必含的短语必含A，含，含A的短语不一定含的短语不一定含b。262终结符号间的优先关系的定义终结符号间的优先关系的定义设设G是是一一个个算算符符文文法法，对对于于任任何何终终结结符符a、b，算算符符优优先先关关系系定义如下定义如下：1)a=b当且仅当当且仅当G中含有形如中含有形如Aab或或AaBb的规则；的规则；2)ab或或BCb；3)ab当且仅当当且仅当G中含有形如中含有形如ABb的产生式，的产生式，而而Ba或或BaC；+27由语法树来说明优先关系由语法树来说明优先关系1)a=b则存在语法子树则存在语法子树(a)，a
22、和和b在同一句柄中同时归约，所以在同一句柄中同时归约，所以优先级相同。优先级相同。2)ab则存在语法子树则存在语法子树(c)，a和和b不在同一句柄中，不在同一句柄中，a先归约，所先归约，所以以b的优先级小于的优先级小于a。其中其中 为为 或非终结符或非终结符283算符优先文法的定义算符优先文法的定义设有一个不含设有一个不含-规则的算符文法规则的算符文法G，如果任何终结符对如果任何终结符对(a，b)至多只满足下述关系之一：至多只满足下述关系之一：a=b，ab，ab；则称则称G是一个算符优先文法，也称是一个算符优先文法，也称OPG文法。文法。( (OPG Operator Precedence G
23、rammarOPG Operator Precedence Grammar) )29【例】【例】文法文法GEGE：EE+E | E*E | (E) | idEE+E | E*E | (E) | id1.所有规则中都没有相邻的非终结符，所以它是算符文法所有规则中都没有相邻的非终结符，所以它是算符文法OG文法。文法。2.由于由于EE+E和和EE*E，所以有所以有+*运算符运算符+和和*之间存在两种不同的优先关系，所以该文之间存在两种不同的优先关系，所以该文法不是算符优先文法法不是算符优先文法OPG.+文法文法GE：EE+T|TTT*F FF(E)|id该文法是算符优先文法（该文法是算符优先文法（O
24、PG）306.3.3 6.3.3 算符优先关系表的构造算符优先关系表的构造对对任任意意的的文文法法非非终终结结符符 A，给给出出集集合合FIRSTVT(A)和和LASTVT(A)的定义：的定义：FIRSTVT(A)=aAa或或ABa，a VT而而B VNLASTVT(A)=a Aa或或AaB，a VT而而B VNv若产生式右部是若产生式右部是aA，且，且 b FIRSTVT(A)，则必有优先关系：则必有优先关系：ab由上述定义，我们有：由上述定义，我们有：31构造优先关系表的算法构造优先关系表的算法输入：算符优先文法输入：算符优先文法G输出：关于文法输出：关于文法G的优先关系表的优先关系表方法
25、：方法：1.为每一个非终结符为每一个非终结符A构造集合构造集合FIRSTVT(A)和和LASTVT(A);2.由由FIRSTVT(A)和和LASTVT(A)集合出发构造分析表集合出发构造分析表;3.对对FIRSTVT(S)中的所有中的所有b，置置;置置=;4.画一个二维表画一个二维表M，行下标和列下标分别都是所有的终结符，行下标和列下标分别都是所有的终结符，再加上再加上“”。在。在M(a,b)处填上处填上a和和b的关系（可能的关系（可能为空，表示为空，表示a和和b无关系），无关系），a，b VT。32构造构造FirstVT(A)的规则：的规则：v若有产生式若有产生式Aa.或或ABa.，则则a
26、FirstVT(A)v若若a FirstVT(B)，且有产生式且有产生式AB.，则则a FirstVT(A)构造构造LastVT(A)的规则的规则：若有产生式若有产生式A.a或或P.aB,则则a LastVT(A)若若a LastVT(B)，且有产生式且有产生式A.B，则则a LastVT(A)33主程序：主程序：BEGIN FOR 每一个非终结符每一个非终结符A和终结符和终结符a DO FA,a:=FALSE; FOR 每个形如每个形如A-a或或A-Ba的产生式的产生式 DO INSERT(A,a) WHILE STACK 非空非空 DO BEGIN 把把STACK的顶项记为的顶项记为(B,
27、a)托出去托出去 FOR 每个形如每个形如A-B产生式产生式 DO INSERT(A,a) ENDENDProcedure INSERT(A,a); IF NOT FA,a THEN BEGIN FA,a:=TRUE PUSH(A,a) ONTO STACK END计算计算FIRSTVT(A)的算法：的算法：FA,a是一个布尔数组其值为真当且仅当aFIRSTVT(A)34由由FirstVT(A)FirstVT(A)和和LastVT(A)LastVT(A)集集构造分析表构造分析表算法：算法：for(每条产生式每条产生式Ax1x2xn)for(i=1;i=n-1;i+)if(xi VT)&(xi+
28、1 VT)置置xi=xi+1;if(i n-2)&(xi VT)&(xi+2 VT)&(xi+1 VN)置置xi=xi+2;if(xi VT)&(xi+1 VN)for( b FIRSTVT(xi+1)置置xixi+1;35对于算符优先文法，我们可以引入一个对于算符优先文法，我们可以引入一个新的新的文法开始符号。文法开始符号。SS可以看成是句子的括号。可以看成是句子的括号。所以所以:对对FirstVT(S)中的所有中的所有b，置置;置置=;关于输入结束符号关于输入结束符号 的解释的解释36对对E求求FIRSTVT（E）和）和LASTVT（E）:按构造规则，按构造规则，EET，则则+ FIRST
29、VT(E)又又ET，TT*F，则则* FIRSTVT(E)又又ET，TF，F(E)，则则( FIRSTVT(E)又又ET，TF，Fid，则则id FIRSTVT(E)故，故，FIRSTVT(E)+，*， ，id。类似地，类似地，LASTVT(E)+，*， ，id。【例】表达式文法【例】表达式文法GEGE：构造该文法的算符优先关系表构造该文法的算符优先关系表。EE + T | TEE + T | TTT * F | FTT * F | FF (E)idF (E)id首先构造每个非终结符的首先构造每个非终结符的FirstVT和和LastVT:37按步骤构造如下：按步骤构造如下：(1)逐条扫描产生式
30、，因有产生式逐条扫描产生式，因有产生式F(E)，则有（，则有（=）。）。(2)寻找寻找终结符在左边，非终结符在右边终结符在左边，非终结符在右边终结符在左边，非终结符在右边终结符在左边，非终结符在右边的的符号对符号对有有EE+T+T则则+FirstVT(T)TT*F*F则则*FirstVT(F)F(E)(E则则(+TT*FT*则则LastVT(T)*F(E)E)则则LastVT(E)(3)#，#=#.【例【例( (续续) )】构造该文法的算符优先关系表。构造该文法的算符优先关系表。38396.3.4 6.3.4 算符优先分析算法的设计算符优先分析算法的设计算符优先分析方法是一种自下而上分析方法，
31、但它算符优先分析方法是一种自下而上分析方法，但它不是一种不是一种规范归约规范归约的分析方法。的分析方法。其原因是在算符优先分析中，仅在终结符之间定义优先关系，其原因是在算符优先分析中，仅在终结符之间定义优先关系，而不考虑非终结符之间的优先关系，从而无法使用优先关系而不考虑非终结符之间的优先关系，从而无法使用优先关系表去识别由表去识别由单个非终结符组成的可归约串。单个非终结符组成的可归约串。也就是说，算符优先分析法也就是说，算符优先分析法不是用句柄来刻画可归约串不是用句柄来刻画可归约串，而，而是用是用最左素短语最左素短语来刻画可归约串的。来刻画可归约串的。401 1最左素短语的定义最左素短语的定
32、义所谓素短语是指这样的一个短语，它至少含有一个终结符，所谓素短语是指这样的一个短语，它至少含有一个终结符，并且除它自身之外不再含有其它素短语。并且除它自身之外不再含有其它素短语。最左素短语是指处于句型最左边的那个素短语。最左素短语最左素短语是指处于句型最左边的那个素短语。最左素短语是算符优先分析算法的可归约串。是算符优先分析算法的可归约串。【例】考虑表达式文法【例】考虑表达式文法GE的句型的句型T+T*F+id的素短语和的素短语和最左素短语。最左素短语。E E+ +T TF FE E+ +T TT TE EididT T* *F FT*F和和id是素短语，是素短语，T*F是最左素短语是最左素短
33、语T是句柄，但不是素短语是句柄，但不是素短语41根据算符优先文法的定义可知根据算符优先文法的定义可知算符优先分析句型有如下性质算符优先分析句型有如下性质：如果如果aNb(或或ab)出现在句型出现在句型r中，则中，则a和和b之间有且之间有且只有一种优先关系只有一种优先关系,即：即：若若ab则在则在r中必含有中必含有a而不含而不含b的短语存在。的短语存在。若若a=b则在则在r中含有中含有a的短语必含有的短语必含有b，反之亦然。，反之亦然。422 2识别句型最左素短语的方法识别句型最左素短语的方法一个算符优先文法一个算符优先文法G的一般句型可写成：的一般句型可写成：#N1a1N2a2NnanNn+1
34、#其中其中ai 是终结符，是终结符，Ni 是可有可无的非终结符。是可有可无的非终结符。也就是说，在算符优先文法的一般句型中，任何两个终结符也就是说，在算符优先文法的一般句型中，任何两个终结符之间至多只有一个非终结符。任何句型都没有相邻的两个非之间至多只有一个非终结符。任何句型都没有相邻的两个非终结符。终结符。43由最左素短语的定义，一个算符优先文法由最左素短语的定义，一个算符优先文法G的任何句型的任何句型#N1a1N2a2NnanNn+1#的最左素短语是满足下列条件的最左子串的最左素短语是满足下列条件的最左子串NiaiNi+1ai+1NjajNj+1：ai1aj+1也就是说，也就是说，Niai
35、Ni+1ai+1NjajNj+1已经和某个产生已经和某个产生式的右端匹配，即已形成可归约串，可以对它进行归约。式的右端匹配，即已形成可归约串，可以对它进行归约。44【例】考虑表达式文法【例】考虑表达式文法GE的句型的句型T+T*F+id的最左素短的最左素短语。语。#T+T*F+id#N1a1N2a2 N3a3a4#+N2a2 N3是最左素短语是最左素短语算符优先关系表见算符优先关系表见P.111表表6.5453 3算符优先分析算法算符优先分析算法算符优先分析方法是从句子开始，从左到右扫描，找出其中算符优先分析方法是从句子开始，从左到右扫描，找出其中的的最左素短语最左素短语进行归约进行归约;已扫
36、描或归约后的串与未扫描的串连接在一起是某时刻的句已扫描或归约后的串与未扫描的串连接在一起是某时刻的句型，继续对句型进行归约，直至输入串扫描结束，句型为型，继续对句型进行归约，直至输入串扫描结束，句型为#S#为止为止.46最左素短语中的终结符号具有相同的优先关系最左素短语中的终结符号具有相同的优先关系，最左素短语中的符号是当时最先要归约的串，最左素短语中的符号是当时最先要归约的串，v如果当前栈顶的终结符如果当前栈顶的终结符输入符号，表示已找到最左输入符号，表示已找到最左素短语的尾，再从栈顶开始，按优先关系在栈内向左寻素短语的尾，再从栈顶开始，按优先关系在栈内向左寻找最左素短语的头，然后归约最左素
37、短语。找最左素短语的头，然后归约最左素短语。v如果出现两个终结符之间不存在优先关系，则表示语法如果出现两个终结符之间不存在优先关系，则表示语法错误，进行出错处理。错误，进行出错处理。47形成最左形成最左素短语素短语48k:=1；Sk:=#；REPEAT把下一个输入符号读进把下一个输入符号读进a中；中；IFSk VTTHENj:=kELSEj:=k1;WHILESjaDOBEGINREPEATQ:=Sj;IFSj1 VTTHENj:=j1ELSEj:=j2UNTILSjQ;把把Sj+1.Sk归约成某个串归约成某个串N;k:=j+1;Sk:=N;ENDOFWHILE;IFSjaORSj=aTHEN
38、BEGINk:=k+1;Sk:=a;ENDELSEERRORUNTILa=#我们使用一个符号栈我们使用一个符号栈S，既用它寄存终结符，也用它寄存非，既用它寄存终结符，也用它寄存非终结符，用终结符，用k代表符号栈代表符号栈S的使用深度。的使用深度。49由于算符优先分析过程不考虑非终结符，所以任何归约都可由于算符优先分析过程不考虑非终结符，所以任何归约都可以归约到同一个非终结符以归约到同一个非终结符N.甚至非终结符根本就可以不入栈甚至非终结符根本就可以不入栈.我们只要在归约时知道去执行哪个语义子程序就可以了，这我们只要在归约时知道去执行哪个语义子程序就可以了，这样还可以节省栈空间样还可以节省栈空间
39、.50【例】【例】对输入串对输入串id+id# id+id# 的算符优先分析过程。的算符优先分析过程。51F F+ +F FididididE EE E+ +T TF FT TF FE Eidididid句子的算符优先分析过程中，没有考虑非终结符，也就是说，最左素短句子的算符优先分析过程中，没有考虑非终结符，也就是说，最左素短语中包含的非终结符是什么对归约来说无关紧要。例如，语中包含的非终结符是什么对归约来说无关紧要。例如，F+F直接归约直接归约为为E,比规范归约少了一些步骤。显然可以提高分析过程的效率。这种情比规范归约少了一些步骤。显然可以提高分析过程的效率。这种情况可以这样解释，编译程序可
40、以况可以这样解释，编译程序可以不必关心符号名字，而只关心与终结符不必关心符号名字，而只关心与终结符和非终结符相联系的语义信息和非终结符相联系的语义信息，如与非终结符或运算对象相关的类型、，如与非终结符或运算对象相关的类型、存储地址等。也就是说，对存储地址等。也就是说，对E+T归约时执行的语义子程序只关心素短语归约时执行的语义子程序只关心素短语中有无符号，而不关心左右是中有无符号，而不关心左右是E、T还是还是F。算符优先分析过程跳过了许多形如算符优先分析过程跳过了许多形如PA的规则，所以算符优先分析过的规则，所以算符优先分析过程的效率较高。程的效率较高。算符优先算符优先算符优先算符优先分析过程分
41、析过程分析过程分析过程 规范规范规范规范分析过程分析过程分析过程分析过程 526.3.5 6.3.5 优先函数的构造优先函数的构造在算符优先分析法中，文法终结符之间的优先关系是用矩阵在算符优先分析法中，文法终结符之间的优先关系是用矩阵表示的，这样需要大量的内存空间。表示的，这样需要大量的内存空间。当文法有当文法有n个终结符时，就需要个终结符时，就需要(n+1)2个内存单元个内存单元(包括包括#)。实际实现中使用优先函数来代替优先矩阵表示优先关系，对实际实现中使用优先函数来代替优先矩阵表示优先关系，对具有具有n个终结符的文法，它只需个终结符的文法，它只需2(n+1)个内存单元个内存单元存放存放优
42、先函数，可以节省大量存储空间。优先函数，可以节省大量存储空间。53把每个终结符把每个终结符a与两个自然数与两个自然数f(a)和和g(a)相对应，使相对应，使得：得：若若ab则则f(a)b则则f(a)g(b)若若a=b则则f(a)=g(b)f与与g称为优先函数称为优先函数.1 1优先函数的定义优先函数的定义54对应的优先函数如下：对应的优先函数如下：对应的优先函数如下：对应的优先函数如下： 552 2构造优先函数的方法构造优先函数的方法方法一、逐次加一法方法一、逐次加一法(Floyd方法方法)1)确定初值，对所有终结符确定初值，对所有终结符a（包括），包括），令令f(a)g(b)0（也可为其它任
43、意整数）。也可为其它任意整数）。2)对所有终结符对所有终结符a和和b若若ab而而f(a) g(b)，则令则令f(a)=g(b)+1若若ag(b)f(b)g(a)f(b)=g(b)从而从而f(a)g(b)=f(b)g(a)=f(a)f(a)f(a)矛盾矛盾因而不存在对应的优先函数。因而不存在对应的优先函数。59第一步，置初值第一步，置初值第二步，迭代第二步，迭代1次次第三步，迭代第三步，迭代2次次第四步，迭代第四步，迭代3次次第第N+1步，迭代步，迭代N次次永远不能收敛永远不能收敛永远不能收敛永远不能收敛601)对于每个终结符对于每个终结符a（包括包括#）令其对应两个符号）令其对应两个符号fa和
44、和ga，画一张以所有符号画一张以所有符号fa和和ga为节点的方向图：为节点的方向图：如果如果ab或或a=b，则从则从fa画一箭弧至画一箭弧至gb；如果如果ab或或a=b，则从则从gb画一箭弧至画一箭弧至fa；2)对每个节点赋一个值，该数等于从该节点出发所能达到对每个节点赋一个值，该数等于从该节点出发所能达到节点（包括出发节点自身在内）的个数。节点（包括出发节点自身在内）的个数。3)检查所构造出来的函数检查所构造出来的函数f和和g与原优先关系表是否矛与原优先关系表是否矛盾。若无矛盾，则所求即为优先函数，反之，则不存在盾。若无矛盾，则所求即为优先函数，反之，则不存在优先函数。优先函数。2 2构造优
45、先函数的方法构造优先函数的方法方法二、方法二、Bell有向图法有向图法输入关系表输入关系表输出优先函数输出优先函数61【例】已知优先关系分析表，构造函数【例】已知优先关系分析表，构造函数f f和和g g62使用优先函数表对符号串的分析过程类似于优先关使用优先函数表对符号串的分析过程类似于优先关系表的过程，另外对系表的过程，另外对“”符号有如下规定：符号有如下规定： f(#)g(#)其中其中x (VN VT).63【例】设有文法【例】设有文法GS:Sa|b|(T)TT,S|S（1）计算）计算每个非终结符的每个非终结符的FIRSTVT和和LASTVT。（2）构造算符优先关系分析表。构造算符优先关系
46、分析表。（3）文法）文法GS是算符优先文法吗？如果是，给出优先函是算符优先文法吗？如果是，给出优先函数，并给出串数，并给出串(a,(a,a)的算符优先分析过程。的算符优先分析过程。(1)FIRSTVT(S)=a,b, ,LASTVT(S)=a,b, (2)FIRSTVT(T)=,a,b, ,LASTVT(T)=,a,b, 算符优先关系分析表算符优先关系分析表文法文法GS是算符优是算符优先文法。先文法。64优先关系分析表对应的优先关系分析表对应的bell有向图有向图 65串串 (a,(a,a) (a,(a,a) 的分析过程的分析过程（0）#(a,(a,a)#移进移进预备预备（1）#(a,(a,a
47、)#（(移进移进（2）#(a,(a,a)#（,用用Sa归约归约（4）#(S,(a,a)#（,移进移进（5）#(S,(a,a)#,(移进移进（6）#(S,(a,a)#（,用用Sa归约归约（8）#(S,(S,a)#（,移进移进（9）#(S,(S,a)#,)用用Sa归约归约（11）#(S,(T)#,)用用TT,S归约归约（12）#(S,(T)#()移进移进（13）#(S,S)#)用用S(T)归约归约（14）#(T)#,)用用TT,S归约归约（15）#(T)#()移进移进（16）#S#)#用用S(T)归约归约,接受。接受。 步骤步骤符号栈符号栈输入串输入串动作说明动作说明66算符优先分析中的出错处理算
48、符优先分析中的出错处理u优先关系表中没有关系的单元即对应行（栈顶）与列优先关系表中没有关系的单元即对应行（栈顶）与列（当前输入）的两个终结符在合法句子不可能相邻，分（当前输入）的两个终结符在合法句子不可能相邻，分析中若碰到两终结符没有关系时，即句子中出现了语法析中若碰到两终结符没有关系时，即句子中出现了语法错误，错误，u另一种语法错误是找不到与栈顶另一种语法错误是找不到与栈顶“句柄句柄”对应的产生式对应的产生式右边，无法归约。右边，无法归约。这些错误可通过向对应单元填入合适的出错处理子程序进行这些错误可通过向对应单元填入合适的出错处理子程序进行处理。处理。67v优点在于：优点在于：便于比较运算
49、，节省存储空间；便于比较运算，节省存储空间；v缺点在于：缺点在于：原来不存在优先关系的两个终结符，由于与原来不存在优先关系的两个终结符，由于与自然数对应，变成可比较的了。因而，可能会掩盖输入自然数对应，变成可比较的了。因而，可能会掩盖输入串的某些错误。但是，我们可以通过检查栈顶符号和输串的某些错误。但是，我们可以通过检查栈顶符号和输入符号具体内容发现那些原来不可比较的情形。入符号具体内容发现那些原来不可比较的情形。优先函数的优点和缺点优先函数的优点和缺点例如，上表中，例如，上表中，f(id)g(id)，但实际上，不存在但实际上，不存在idid的关系（见优先关系表），的关系（见优先关系表），这样
50、，当分析符号串这样，当分析符号串id+idid*id时，时，只有当其归约到只有当其归约到N+NN才发现错误，这是由于句型中有两才发现错误，这是由于句型中有两个相邻的非终结符，而不是由于个相邻的非终结符，而不是由于id和和id不能相邻。不能相邻。686.3.6 6.3.6 算符优先分析法的局限性算符优先分析法的局限性一般语言的方法很难满足算符优先文法的条件一般语言的方法很难满足算符优先文法的条件文法文法,书写书写限制大。限制大。很难处理像减号这样的记号，因为减号有两个不同的优很难处理像减号这样的记号，因为减号有两个不同的优先级先级(一元、二元运算符一元、二元运算符)很难避免把错误的句子得到正确的
51、归约很难避免把错误的句子得到正确的归约由于算符优先分析法跳过了所有单非规则由于算符优先分析法跳过了所有单非规则(规则的右部只规则的右部只含有单个非终结符含有单个非终结符)之间的归约，这样算符优先分析比规之间的归约，这样算符优先分析比规范归约要快的多，这既是优点也是缺点。范归约要快的多，这既是优点也是缺点。由于忽略非终结符在归约过程中的作用，可能导致本来由于忽略非终结符在归约过程中的作用，可能导致本来不是句子的输入串不是句子的输入串误认为误认为是文法句子。是文法句子。69【例】设有算符优先文法【例】设有算符优先文法AA;D|DDD(E)|FFa|(A)EE+A|A对输入串对输入串(a+a)进行算符优先分析，其结果能正确地进行归进行算符优先分析，其结果能正确地进行归约。约。但是但是A(a+a)不存在不存在，(a+a)不是文法的句子。不是文法的句子。*707172
