z第二章 文法和语言.ppt

等价：若文法G1、G2满足 L(G1)=L(G2)， 则称文法G1、G2是等价的。 拓广文法： 设文法G1[S] = (VN,VT,P,S)，构造文法 G2[S’]=(VN∪{S’},VT,P’,S’)，其中：P’={A→?|A→?∈P} ∪{S’→S}，显然L(G1)=L(G2)，则G2称为G1的拓广文法。 1. 消除无用符号和无用产生式 定义2.23 无用符号 任给一文法符号X∈V，若X 满足： (1) S??X? (2) X??，其中?∈VT* 则称文法符号X是有用的，否则，称X为无用符号。 无用产生式 任给一产生式A→?∈P，若产生式左部或右部含有无用符号，则称此产生式A→?为无用产生式。 * * 算法2.1，按定义2.23中（2）的要求构造文法G1=(VN1,VT,P1,S)， (X??，其中?∈VT*) 消除无用符号和无用产生式(针对VN): (a) VN1:={ }；P1:={ }。(只对非终极符) (b)对每个A→x1x2…xn ∈ P且xi∈VN1∪VT∪{?} (i=1,…,n)，置VN1:= VN1∪{A}。 (c) 重复（b），直至VN1不再扩大为止。 (d)对每个A→x1x2…xn ∈ P且xi∈VN1∪VT∪{?} (i=1,…,n)，则A→x1x2…xn置入P1中。 * 例2.9 设文法G[S]=({S,U,V,M,N}，{a, b}，P，S)，其中： P ：S→U│V， U→M， V→a， N→b。 按算法2.1 得：VN1={S,V,N}，VT不变， P1 ={ S→V，V→a，N→b } 则文法G1[S]=({S,V,N}，{a,b}， { S→V，V→a，N→b }，S) 算法2.2 消除无用符号和无用产生式，按定义2.23(1) S??X?中的要求构造G2=(VN2,VT2,P2,S)。 （a）VN2={S}；VT2={ }；P2={ }； （b）对于G1的每个产生式A→x1x2…xn， 置VN2=VN2∪{xi│A∈VN2∧xi∈VN1，i=1,…,n}； VT2=VT2∪{xi│A∈VN2∧xi∈VT，i=1,…,n}。 （c）重复（b），直至VN2、VT2不再扩大为止。 （d）对于每一个产生式A→?∈P1，若A→?的左、右部之任意文法符号x∈VN2∪VT2，P2= P2∪{A→?}。 * 文法G1[S]=({S,V,N}，{a,b}， { S→V，V→a，N→b }，S) 经过算法2.2的处理，得到文法 G2[S]= (VN2,VT2,P2,S)，其中 VN2={S,V}，VT2={a}，P2 ={ S→V，V→a}。 算法2.1、2.2，将文法G依次等价变换成G1、G2，文法G2： L(G)=L(G1)= L(G2)。 例2.10 化简文法G[S]=({S,U,V,W}，{a,b,c}，P，S)其中： P={S→aS│W│U，U→a，V→bV│ac，W→aW} 施行算法2.1得： VN1={S,U,V} VT={a,b,c} P1 ={S→aS│U，U→a，V→bV│ac} 施行算法2.2得： VN2={S,U} VT2={a} P2 ={S→aS│U，U→a} 2. 消除单一产生式 单一产生式：指产生式 A→B∈P∧(A,B∈VN )。 算法2.3 消除单一产生式 算法步骤： （a）将文法G的非终极符给出一种排序，使VN = {A1,…,An}，对于每个Ai作集合W(Ai)={B│Ai?B，B∈VN}（i=1,2,…,n）（注意： Ai 本身属于该集合） * （b）构造产生式集合 P1= （c）构造VN1={A|A→?∈P1} 最后得到的文法G1=(VN1,VT,P1,S)就消除了单一产生式。 例2.11 文法G=({S,A,B}，{a,b}，P，S)，其中： P={S→AB│A│B， A→aAb│ab，B→Bb│b} 先构造W(Ai)集合：W(S)={S,A,B} W(A)={A} W(B)={B} 再构造产生式P1： S→AB│aAb│ab│Bb│b A→aAb│ab B→Bb│b 例2.12 试将文法G=({S,A,B,C}，{a}，P，S)， 其中：P={S→AB，A→B，B→C，C→a} 消除文