优先关系: 终结符ab的三种优先关系: a=b当且仅当存在形如下面的产生式U→..ab.或 U→….aQb a≤b当且仅当存在形如下面的产生式U→.laW..的生产式, 且有W鸷b a>b当且仅当存在形如U->.Vb.的产生式 且有V乡.a或V参.aQ
优先关系： 终结符ab的三种优先关系： 当且仅当存在形如下面的产生式U→ … ab…或 U→ … aQb… 当且仅当存在形如下面的产生式U→…aW…的生产式， 且有 W b… 当且仅当存在形如U→…V b…的产生式 且有 V …a 或V … aQ a b a b a b
如果一个算符文法的任何终结符对至多只满足三种关系之一, 称为算符优先文法。 例:考虑文法G(E):E→E+TT T→T*FF F→i(E) 是否是算符优先文法? 验证终结符对之间的优先关系(p90优先表)
如果一个算符文法的任何终结符对至多只满足三种关系之一， 称为算符优先文法。 验证终结符对之间的优先关系(p90优先表) 例：考虑文法G(E)：E→E +T |T T→T*F | F F→i| (E) 是否是算符优先文法？
如何从文法构造优先关系表? 检查文法产生式的每个候选,可找出所有满足=的终结符对。 如何找出满足<和>终结符对? 对每个非终结符P构造两个集合 FIRSTⅥT(P和 LASTVT (P) 十 FIRSTⅥTP)=4Pa.或PQn…,a∈VQ∈VN LASTVT(P)=alp 戈P +/a∈n,Q∈N 检查每个产生式候选,若形为.aP..,则对任何b∈ FIRSTVT(P), 我们有a<b 若形为.Pb.,则对任何a∈ LASTVT(P), 我们有a>b。 对表达式文法的非终结符构造 FIRSTVT和LASTⅥ并建立优先关系毒
如何从文法构造优先关系表？ 检查文法产生式的每个候选，可找出所有满足 的终结符对。 如何找出满足 和 终结符对？ 对每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P) FIRSTVT(P)= + + a P a P Qa a VT Q VN | ...或 ..., , LASTVT(P) = + + a P a P aQ a VT Q VN | ... 或 ... , , 检查每个产生式候选，若形为...aP...,则对任何b∈FIRSTVT(P)， 我们有a b。 若形为...Pb...,则对任何a∈LASTVT(P)， 我们有a b。 对表达式文法的非终结符构造FIRSTVT和LASTVT并建立优先关系表
算符优先分析算法 素短语:这样的一个短语,它至少含一个终结符,不含比自身 更小的素短语。 最左素短语:句型最左边的素短语。 定理:算符优先文法的句型N1a1N2a2,, N-an+1#的最左素短语 是满足如下条件的最左子串Na1NaN a;=a;+1 a
算符优先分析算法 素短语：这样的一个短语，它至少含一个终结符，不含比自身 更小的素短语。 最左素短语：句型最左边的素短语。 定理：算符优先文法的句型#N1a1N2a2...NnanNn+1#的最左素短语 是满足如下条件的最左子串Njaj...NiaiNi+1 aj-1 aj aj aj+1 ... ai ai ai+1
优先函数 利用两个函数f和g,对每个终结符θ,映射为两个数f(0)和 g(0),使得: 若01<02则f(01)<g(02) 若 02则f(0)=g( 若01>02则f(1)>g(62) 有的关系表不存在优先函数! 对于存在优先函数的关系表,如何构造优先函数? 请自学p9495优先函数的构造方法
优先函数 利用两个函数f和g，对每个终结符θ，映射为两个数f(θ)和 g(θ)，使得： 若θ1 θ2则f(θ1)< g(θ2) 若θ1 θ2则f(θ1)= g(θ2) 若θ1 θ2则f(θ1)> g(θ2) 有的关系表不存在优先函数！ 对于存在优先函数的关系表，如何构造优先函数？ 请自学p94~95优先函数的构造方法