PPT《编译原理》

FIRST(Bq)=? 针对产生式规则的右部产生开始符号集合

2、开始符号集合的定义: 设G=(VT,VN, P ,S )是上下文无关文法,开始符号集合为First(?)={ a | ? ?aβ,a∈VT, ? 、β∈V*} 规则右部?的开始符号集包括所有终结符 a,使得规则右部?经过若干推导后得到的字符串以a为起始. 若? ?ε,则规定?∈First(?) . * * 例3:上例中文法是: S?Ap|Bq A ? a | cA B ? b | dB则:FIRST(Ap)={a,c};

FIRST(Bq)={b,d} 针对产生式规则的右部产生开始符号集合 如何根据输入串的第1个符号来确定产生式呢? 根据当前输入符号属于哪个产生式右部的开始符号集合而决定选择相应产生式进行推导. 例3:文法G[S]S ? aA | d A ? bAS|ε 若输入W=abd,则推导过程为: S a A ? S a A b A S ? S a A b A S ? d 例3:文法G[S]S ? aA | d A ? bAS|ε 若输入W=abd,则推导过程为: S ?aA ? abAS ? abS ? abd语法树为: 当某一非终结符的产生式中含有空产生式时,第二步推导的产生式该如何确定呢?根据后跟符号集合确定

3、后跟符号集合的定义: 设G=(VT,VN,P,S)是上下文无关文法,A∈VN,S是开始符号,Follow(A)={a | S ?uAβ且a∈VT,a ∈First(β),u∈VT*,β∈V+}.针对非终结符若S ? uAβ,且β ? ε,则#∈Follow(A)(#表示输入串的结束符,或句子括号) 可写成为:Follow(A)={a|S?…Aa…, a∈VT}若S?…A,则#∈Follow(A). * * * * * Follow(A)是所有句型中出现在紧接A之后的终结符或 # . 例4:在例2中文法G[S]为:S ? Ap | Bq A ? a | cA B ? b | dB求Follow集. 解:Follow(S)={?} Follow(A)={?} Follow(B)={?} 换句话说: Follow(A)是所有句型中出现在紧接A之后的终结符或 # . 例4:在例2中文法G[S]为:S ? Ap | Bq A ? a | cA B ? b | dB求Follow集. 解:Follow(S)={#} Follow(A)={p} Follow(B)={q} 自上而下语法分析要解决的关键问题 假定要被代换的最左非终结符号是B,且有n条规则:B→A1|A2|…|An,那么如何确定用哪个右部去替代B?根据规则的选择集合来确定.

4、选择集合的定义给定上下文无关文法的产生式A??,A?VN,??V*,若??ε,则Select(A??)=First(?),若??ε,则Select(A??)=(First(?)-{ε})∪Follow(A) * * 给定输入串,根据产生式规则的选择集合选择产生式进行推导.

5、LL(1)文法的定义:一个上下文无关文法是LL(1)文法的充分必要条件是对每个非终结符A的两个不同产生式:A??,A?β满足Select(A??)∩Select(A?β)=?,其中?、β不同时推出? 只有对满足LL(1)文法的句子,才能进行确定的自顶向下分析:给定输入串,就可以根据产生式规则的选择集合确定唯一的产生式进行推导. LL(1)的含义:从左L向右扫描输入串,分析过程中采用最左L推导,只需向右看1个符号就可确定如何推导(选择哪个产生式进行推导). 例5:上例3文法: S?aA|d A?bAS|ε证明该文法为LL(1)文法. 例5:上例3文法: S?aA|d A?bAS|ε证明该文法为LL(1)文法.不难看出:Select(S?a A)=First(aA)={a} Select (S?d)= First(d)={d} Select (A?bAS)={b} Select (A?ε)=(first(ε)-{ε} )∪follow(A)={a,d,#} Select (S? aA) ∩Select(S?d)= { a}∩{d}=? Select(A?bAS) ∩ Select(A?ε) ={b}∩{a,d,#}={ ? }所以上述文法是LL(1)文法. S?AaaA? ε * S?aA ?abAS ?abAdS ?aA ?abAS ?abAaA所以Follow(A)={a,d,#} 例:设文法G[S]为: S ? aAS | b A ? bA |ε 判别是否是LL(1)文法. 解:Select(S ? aAS)=first(aAS)={a}Select ( S ? b ) ={b}Select ( A ? bA ) ={b}Select ( A ? ε) =(first(ε)-{ε})∪follow(A)={a,b}Select( S?aAS ) ∩Select(S?b ) ={a}∩{ b }=?Select(A ? bA) ∩Select(A ?ε)={b}∩{a,b}?? 因此,该文法不是LL(1)文法,因而也就不可能用确定的自顶向下分析. 当需要选用自顶向下分析技术时,首先必须判定所给的文法是否是LL(1)文法.