自底向上优先分析方法.ppt

第四章 语法分析——自上而下分析 【例】文法G[S]对输入串 abbcde# 进行语法分析，检查该符号串是否是该文法的正确句子。 【例】已知优先关系分析表，构造函数f和g 【例】设有文法G[S]: S→a|b|(T) T→T,S|S 优先关系分析表对应的bell有向图 串 (a,(a,a)) 的分析过程 算符优先分析中的出错处理 使用优先函数表对符号串的分析过程类似于优先关 系表的过程，另外对“＃”符号有如下规定： f(#)g(x) f(x)g(#) 其中x?(VN?VT). （1）计算每个非终结符的 FIRSTVT 和 LASTVT。 （2）构造算符优先关系分析表。 （3）文法G[S] 是算符优先文法吗？如果是，给出优先函数，并给出串 (a,(a,a)) 的算符优先分析过程。 (1)FIRSTVT(S)={a,b,?}, LASTVT(S)={a,b,?} (2)FIRSTVT(T)={,,a,b,?}, LASTVT(T)={,,a,b,?} = # , ) = ( b a # , ) ( b a 算符优先关系分析表 文法G[S]是算符优先文法。 6.3.3 算符优先关系表的构造 对任意的文法非终结符 A，给出集合FIRSTVT(A)和LASTVT(A)的定义： FIRSTVT(A)={a︱A?a… 或 A?Ba…，a∈VT 而B∈VN} LASTVT(A)={a∣A?…a 或 A?…aB，a∈VT 而B∈VN} ＋ ＋ ＋ ＋ 若产生式右部是 …aA…，且?b∈FIRSTVT(A)，则必有优先关系： a · b 若产生式右部是 …Ab…， 且?a∈LASTVT(A)，则必有优先关系： a · b 由上述定义，我们有： 构造优先关系表的算法 输入：算符优先文法 G输出：关于文法 G 的优先关系表 方法： 为每一个非终结符 A 构造集合 FIRSTVT(A)和LASTVT(A); 由 FIRSTVT(A)和LASTVT(A)集合出发构造分析表; 对 FIRSTVT(S)中的所有 b， 置 ＃ ? b;对 LASTVT(S) 中的所有 a， 置 a ? ＃; 置 ＃ =? ＃; 画一个二维表 M，行下标和列下标分别都是所有的终结符，再加上“＃”。在M(a,b)处填上 a 和 b 的关系（可能为空，表示 a 和 b 无关系），a，b?VT。 构造 FirstVT(A) 的规则： 若有产生式 A→a... 或 A→Ba...，则 a∈FirstVT(A) 若 a∈FirstVT(B)，且有产生式A→B...，则 a∈FirstVT(A) 构造 LastVT(A) 的规则： 若有产生式 A→...a 或P→...aB,则 a∈LastVT(A) 若 a∈LastVT(B)，且有产生式 A→...B，则 a∈LastVT(A) 主程序： BEGIN FOR 每一个非终结符A和终结符a DO F[A,a]:=FALSE; FOR 每个形如A-a…或A-Ba…的产生式 DO INSERT(A,a) WHILE STACK 非空 DO BEGIN 把STACK的顶项记为(B,a)托出去 FOR 每个形如A-B…产生式 DO INSERT(A,a) END END Procedure INSERT(A,a); IF NOT F[A,a] THEN BEGIN F[A,a]:=TRUE PUSH(A,a) ONTO STACK END 计算FIRSTVT(A)的算法： F[A,a]是一个布尔数组 其值为真当且仅当 a?FIRSTVT(A) 由FirstVT(A)和LastVT(A)集构造分析表算法： for ( 每条产生式 A→x1x2…xn ) for ( i=1; i=n-1; i++ ) { if ((xi?VT)(xi+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)) 置 xi ? b; if (xi?VN)(xi+1?VT)) for (? a?LASTVT(xi)) 置 a ? xi+1; } 对于算符优先文法，我们可以引入一个新的文法开始