算符优先分析法详解(2)

算符优先分析法。

算符优先表的构造算符优先表的构造方法：通过检查G的每个产生式的每个候选式，可以首先找出满足a=b的终结符对；为了找出所有满足关系<和>的终结符对，首先需要对G的每个非终结符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}有了这两个集合后，就可以通过检查每个产生式的候选式确定满足关系<和>的所有终结符对。

四川大学计算机学院金军

7

四川大学计算机学院

金军

8

算符优先表的构造假定有产生式的一个候选式形为…aP…,那么，对任何b∈FISTVT(P),a<b;假定有产生式的一个候选式形为…Pb…,那么，对任何a∈LASTVT(P),a>b。

FIRSTVT和LASTVT集合FIRSTVT(P)的构造：若有产生式P→ a…或P→ Qa…,则 a∈FIRSTVT(P);若a∈FIRSTVT(Q),且有产生式P→ Q…,则a∈FIRSTVT(P)。

LASTVT(U)的构造：若有产生式U→…a或U→…aV,则 a∈LASTVT(U);若a∈LASTVT(V),且有产生式U→…V,则 a∈LASTVT(U)。四川大学计算机学院金军 9四川大学计算机学院金军 10

FIRSTVT构造算法建立一个二维布尔数组F[P, a],使得F[P, a]为真的条件适当且仅当a∈FIRSTVT(P);再用一个栈STACK,把所有初值为真的数组元素F[P, a]的符号对(P, a)全都放到栈中，对栈施加如下操作：如栈不空，弹出栈顶符号对记作(Q, a),查看是否有形如P Q…的产生式，若有，且 a∈FIRSTVT(P),则将F[P, a]置为真，并把 (P, a)入栈；重复上步，直到栈空为止。四川大学计算机学院金军 11

优先表构造算法有了每个非终结符P的FISTVT(P)和 LASTVT(P)之后，就能构造文法G的优先表。其算法如下：

四川大学计算机学院金军

12

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库算符优先分析法详解(2)在线全文阅读。