第四章语法3讲课.ppt

表4.9 优先关系表 （1）算符优先文法（OPG） 二、形式方法 优先关系的定义 若G是一OG文法，a,b∈Vt , U,V,W∈Vn a,b之间优先关系分别有以下三种情况: 1) a=b if 文法中有形如 U → …ab…或U → …aVb… 的规则。 2) ab if 文法中有形如 U → …aW …的规则，其中 W? b …或W? Vb … 3) ab if 文法中有形如 U → …Wb …的规则, 其中 W? …a或W? … aV 。 + + . + + . . 算符优先文法（OPG）的定义 设有一OG文法，如果在任意两个终结符之间， 至多只有上述关系中的一种，则称该文法为算符 优先文法(OPG)。 （2）构造优先关系矩阵 FIRSTVT( U )={b|U?b…或U?Vb…,b∈Vt, V∈Vn} + + LASTVT( U )={a|U?…a或U?…aV,a∈Vt, V∈Vn} + + 求 “ = ” 检查每一条规则，若有U → …ab…或 U → …aVb…, 则 a=b 求“ ”、“ ”复杂一些，需定义两个集合 . . . . . . 求“ ”、“ ”: . . 若文法有规则 W →...aU... ，对任何b, b∈FIRSTVT(U) 则有：a b . 若文法有规则 W →...Ub... ，对任何a, a∈LASTVT(U) 则有：a b . . . 构造FIRSTVT(U)的算法 1)若有规则U → b…或U → Vb…(说明存在U?b…或 U?Vb…) 则b∈FIRSTVT(U) + + 2)若有规则U → V…且b∈FIRSTVT(V), 则b∈FIRSTVT(U) 说明:因为V?b…或V?Wb…,所以有U?V…?b…或 U?V… ?Wb… + + + + FIRSTVT(A)= FIRSTVT(T)= FIRSTVT(R)= 设有下列算符优先文法G: A → a | (R) T → A , T | A R→ T 求如下FIRSTVT 集合。 FIRSTVT(A)={ a ( } FIRSTVT(T)={ , a ( } FIRSTVT(R)={ , a ( } 设有下列文法G: S → a | (T) | bT T →T , S | S FIRSTVT(S)=? FIRSTVT(T)=? 构造LASTVT(U)的算法 1.若有规则U → …a或U → …aV,则a∈LASTVT(U) 2.若有规则U → …V,且a∈LASTVT(V)则a∈LASTVT(U) LASTVT(A)= LASTVT(T)= LASTVT(R)= 设有下列算符优先文法G: A → a | (R) T → A , T | A R→ T LASTVT(A)={ a ) } LASTVT(T)={ , a ) } LASTVT(R)={ , a ) } 设有下列文法G: S → a | (T) | bT T →T , S | S 求 LASTVT(S)=? LASTVT(T)=? FOR 每条规则U → x1x2…xn DO BEGIN 产生式中相邻(或只隔一个非终结符) 的两个终结符优先级关系为xi=xi+1； if xi为终结符号， xi+1为非终结符号 FOR FIRSTVT(xi+1)中的每个a DO 置xi