编译原理第03章文法和语言.ppt

* 执行算法1 第一步，由于产生式U→a、 V→ac的右部均为终结符号串，故置VN(1) ={U，V}； 第二步，对于产生式S→U ，由于U ? VN(1) ，故将S置于中，所以VN(1) ={S，U，V}； 于是得到以下文法G1： G1=（{S,U,V},{a,b,c},P (1),S），其中P (1)由如下产生式组成： S→aS S→U U→a V→bV V→ac * 执行算法2 第一步，置VN’ ={S}； 第二步，因为G1中含有产生式S→U、U→a ，故应将U、a分别置于，即VN’ ={S，U} VT’ ={a}; 因此得到等价的且不含无用符号和无用产生式的文法为G2=（{S，U}，{a}，P’，S），其中，P’由如下产生式组成： S→aS S→U U→a * ε-产生式的消除 算法3 算法4（ ε不属于文法所产生的语言） 算法5 （ε属于文法所产生的语言） 示例： ε不属于文法所产生的语言 ε属于文法所产生的语言 * 算法3 1、作集合 W1={A|产生式A →ε?P}； 2、作集合序列 WK+1=WKU{B| B→? ?P,且? ?WK+}；K ? 1 并使WK+1 收敛； 令W= WK+1 ,则对于每一个A?W，有A?*ε。 对于上述W，如果G中不含有可能导出ε的符号，则W= ? 。 * 算法4 1、利用算法3，可将分VN为两个不相交的子集：W和VN -W； 设A →X1X2 … Xm是P中的任一产生式，则按以下规则将所有形如A →Y1Y2 … Ym的产生式置入P’中： （1）若Xi ? VN –W，则取Yi = Xi ； （2）若Xi ? W，则Yi分别取Xi 和ε，若所有的均Xi属于W，则不将所有Yi的取ε。 * ε不属于文法所产生的语言 已知文法G=（{S,A,B,C}，{a,b,c}，P，S），产生式P的组成如下： S→aA A→BC B→bB C→cC B→ε C→ε 执行算法3，得到W={A,B,C} 执行算法4，可得到P’如下： 对于S→aA,将产生式S→aA、S→a放入P’； 对于A→BC ,将产生式A→BC、A→B、A→C放入P’； 对于B→bB，将产生式B→bB、B→b放入P’； 对于C→cC，将产生式C→cC、C→c放入P’。 则消除ε-产生式之后的文法的产生式如下： S→aA S→a A→BC A→B A→C B→bB B→b C→cC C→c * 算法5 1、引入新的符号S’（S’?VNUVT）作为G的开始符号，令= VNU{S’}； 2、作产生式集 P’=PU{S’→ ? |产生式S→? ?P} 3、对文法G’=（VN’，VT，P’ ，S’）执行算法4消去P’中全部ε-产生式。 4、将S’加入到所得的产生式集中。 * ε属于文法所产生的语言 已知文法G=（{S,A,B}，{a,b,c}，P，S），产生式P的组成如下： S→cS S→AB A→aAb B→Bb A→ε B→ε 引入新的符号S’； 作产生式集P’= PU{S’→cS, S’→AB} 利用算法4消去P’中的ε-产生式，并加入S’→ε，得到全部的产生式如下： S’→cS S’→c S’→AB S’→A S’→B S’ → ε S→cS S→c S→AB S→A S→B A→aAb A→ab B→Bb B→b * 单产生式的消除 算法： 1、设A={A1 , A2, …, An}，对于每一个Ai，作集合序列 W1(Ai)={Ai} WK+1 (Ai) = WK(Ai)U{D|C→D, C ? WK(Ai), D ? VN}，并使其收敛为Wi。 构造产生式集 P’={Ai →? |产生式B→? ?P，B ?Wi ，? ?VN}，此时P’中不含有单产生式。 示例 * 示例：单产生式的消除 已知文法G=（{S,A,B}，{a,b}，P，S），产生式P的组成如下： S→A S→B S→AB A→aAb B→Bb A→ab B→b 对于G，执行算法得到： W(S)={S,A,B} W(A)={A} W(B)={B} 由此可构造产生式集P’如下： S→AB S→aAb S→ab S→Bb S→b A→aAb A→ab B→Bb B→b * 12班2008年28日，banana提问 * 2008年2月28日止 * 0229 * 0227 0307 * 0312 * * 乔姆斯基对文法的分类 通过对产生式施加不同的限制，Chomsky（乔姆斯基）将文法分为四种类型： 0型文法：对文法G=(VN，VT，P，S)的任一产生式α→β，都有α∈(VN∪VT)*且至少含有一个非终结符，β∈(VN∪VT)*。 1型文法（上下文有关文法） ：对文