优先关系的定义 Sj=Si:当且仅当G中有规则U:=.SjS Sissi:当且仅当U:=SjV…,且V HEAD+ Si S≥Si:当且仅当U∷=.VW..,其中V和 W分别满足ⅤTA±Sj和W HEAD*Sj且S为终结符号
优先关系的定义 • SjSi：当且仅当G中有规则U::=…SjSi… • SjSi：当且仅当U::=…SjV…，且V HEAD+ Si； • SjSi：当且仅当U::=…VW…，其中V和 W分别满足V TAIL+ Sj和W HEAD* Sj且Sj为终结符号
HEAD和TAIL U HEAD S当且仅当U∷=S UTAS当且仅当U∷=.S ·HEAD+,HEAD*分别是HEAD的传递闭包和自反传递闭包。 U HEAD+S当且仅当U:=U1.,U1∷=U2.,, Un:=S..。 UEAD*S当且仅当U=S或者 U HEAD+S ·AL+是ZA的传递闭包 UZA+S当且仅当U∷=.U1,U1∷:=U2,, Un
HEAD和TAIL • U HEAD S 当且仅当U::=S… • U TAIL S 当且仅当U::=…S • HEAD+，HEAD*分别是HEAD的传递闭包和自反传递闭包。 – U HEAD+ S当且仅当 U::=U1…，U1::=U2…，… ， Un::= S…。 – U HEAD* S当且仅当U=S或者U HEAD+ S • TAIL+是TAIL的传递闭包。 – U TAIL+ S当且仅当U::=…U1，U1::=…U2，…， Un::= …S
优先关系 定理51Sj≡S当且仅当SjSi出现在某个 规范句型的句柄中 定理52Sj≥Si当且仅当存在规范句 型.sjSi…,且S是该句型的句柄的最后 符号 定理53Sj≤Si当且仅当存在规范句 型…SjSi.,且Si是该句型的句柄的第 个符号
优先关系 • 定理5.1 Sj Si当且仅当SjSi出现在某个 规范句型的句柄中。 • 定理5.2 Sj Si当且仅当存在规范句 型…SjSi…，且Sj是该句型的句柄的最后 一个符号。 • 定理5.3 SjSi当且仅当存在规范句 型…SjSi…，且Si是该句型的句柄的第一 个符号
定理5.1的证明 如果SjSi出现在句柄中,当然有U∷=:SjSi 如果有规则U∷= uSjsiv, 必然有某个符号串的推导使用了该规则。(假设文 法是已压缩的) 根据该推导构造语法树。则必然存在一个结点标记 为U,其子结点为 luSjsiv。 根据语法树构造最左规约(每一步都对句柄进行规 约)。那么上面的结点对应的一步就是将uSS规约 为U。此时, uSisⅳv为句柄
定理5.1的证明 • 如果SjSi出现在句柄中，当然有U::=…SjSi… • 如果有规则U::=uSjSiv， – 必然有某个符号串的推导使用了该规则。（假设文 法是已压缩的） – 根据该推导构造语法树。则必然存在一个结点标记 为U，其子结点为uSjSiv。 – 根据语法树构造最左规约（每一步都对句柄进行规 约）。那么上面的结点对应的一步就是将uSjSi规约 为U。此时，uSjSiv为句柄
定理52的证明(1) 如果Sj≥Si, 按照定义存在规则U:=VW., V TAIL+ Sj,且W HEAD*S。 必然有句型.VW.,由TAI+和HEAD*的定义,必然 存在句型. vuSjsi.,且V→>*vU=>vuSj,W=>Si.。 构造相应的语法树,并且从语法树构造相应的规范推导。 uSj必然在某一步成为句柄。而此时由于S在Sj的右面, 它必然还没有被规约。所以,当uSj成为句柄的时候,其 规范句型必然为.uSSi
定理5.2的证明(1) • 如果SjSi， – 按照定义存在规则U::=…VW…，V TAIL+ Sj，且W HEAD*S。 – 必然有句型…VW…，由TAIL+和HEAD*的定义，必然 存在句型…vuSjSi…，且V=>*vU=>vuSj，W=>Si…。 – 构造相应的语法树，并且从语法树构造相应的规范推导。 uSj必然在某一步成为句柄。而此时由于Si在Sj的右面， 它必然还没有被规约。所以，当uSj成为句柄的时候，其 规范句型必然为…uSjSi…