自顶向下语法分析方法.ppt

第五章 自顶向下语法分析方法;;;主要内容;5.1 确定的自顶向下分析思想;例5.1;S;;例5.2;语法树为：;;设G=(VN,VT,P，S)是上下文无关文法 FIRST（?）={a|? a?, a∈VT, ?, ?∈V*} 若? ε则规定ε∈FIRST（?） FIRST（?）为?的开始符号集或首符号集 例：文法G2中 FIRST（Ap）= {a, c} FIRST（Bq）= {b, d};;例5.3;语法树为：;;设G=(VN,VT,P，S)是上下文无关文法，A∈VN，S是开始符号 FOLLOW（A）={a?S ? A ?且a ∈ FIRST（?）， ? ∈V*， ?∈V+ } 若S ? A ? ,且? ε，则#∈FOLLOW(A) 也可以定义为： FOLLOW（A）={a?S …Aa…且a ∈VT } 若有S …A ? ,且? ε，则#∈FOLLOW(A) ‘#’为输入串的结束符，或称输入串括号;;定义5.3;定义5.4;LL(1)文法的含义;例5.3;例5.4;5.2 LL(1)文法的判别;例5.5;1) 求出能推出ε的非终结符;2)计算FIRST集;若x?VT，则first(x)＝{x} 若x?VN，且有x?a…，a?VT，则a?first(x) 若x?VN，x ? ?，则??first(x) 若x?VN，y1，y2，…，yi都?VN，若有产生式x?y1y2…yn，当y1，y2，…yi-1都? ?时(1≤i≤n)， 则first(y1)－{?}， first(y2)－{?}，…， first(yi－1)－{?}，first(yi)都包含在first(x)中。 e) 当上式中所有yi ? ? (1≤i≤n)， 则first(x)＝(first(y1)- {?}) ∪(first(y2) - {?}) ∪…∪ ( first(yn) - {?}) ∪ {?};first(S)=(first(A)-{?}) ∪(first(B)-{?}) ∪{?} ∪{b}={a,b, ?} first(A)={b} ∪{?}={b, ?} first(B)={?} ∪{a}={a, ?} first(C)=(first(A)-{?}) ∪first(D) ∪first(b)={a,b, c} first(D)={a} ∪{c}={a,c};一个文法符号串的first集合计算方法：; 根据上面规则，每个产生式的右部符号串开始符号集合为：;方法二：由关系图法求文法符号的first集合;first(S);(4)规则3： first(A)结点有路径可到达的终结符结点所标记的终结符都为first(A)的成员。;follow集的定义： FOLLOW（A）={a?S …Aa…且a ∈VT } 若有S …A ? ,且? ε，则#∈FOLLOW(A) ;;Follow(S)={#} Follow(A)={a，#，c} Follow(B)={#} Follow(C)={#} Follow(D)={#};方法二：由关系图法求非终结符号的follow集;4、若文法中有A??B?，且? ?ε，则从Follw(B)结点到 Follow(A)结点连一条箭弧。 5、对每一first(A)结点，如果有产生式A??X?，且? ?ε，则从First(A)结点到 First(X)结点连一条箭弧。 6、凡是从Follow(A)结点有路径可以到达的终结符或“#”号的结点，其所标记的终结符或“#”即为Follow(A)的成员。 ;文法为： S ? AB | bC A ?ε | b B ?ε | aD C ?AD | b D ?aS | c;(4) 计算Select集： 选择集合的定义 给定上下文无关文法的产生式A??，A?VN， ??V*，若??ε，则Select（A??）=First(?)， 若??ε，则Select(A??)=（First(?)-{ε}）∪Follow(A) ;(4) 计算Select集： 每个产生式的Select集合计算为: Select(S?AB)= (first (AB)-{ε})∪Follow(S)={b,a,#} Select(S? bC)= first (bC)={b} Select(A?ε)= (first (ε)-{ε})∪Follow (A)={c,a,#} Select(A?b)= first (b) ={b } Select(B?ε)= (first (ε) -{ε}) ∪Follow (B)={ #} Select(B?aD)= first (aD) ={a