资源描述：
《编译原理PPT总结》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、编译原理PPT总结1.正规文法到正规式的转换:(1)将正规文法中的每个非终结符表示成关于它的一个正规式方程，获得一个联立方程组。(2)依照求解规则：若x=αx
2、β(或x=αx+β)则解为x=α*β;若x=xα
3、β(或x=xα+β)则解为x=βα*以及正规式的分配律、交换律和结合律求关于文法开始符号的正规式方程组的解。例1设有正规文法G：Z®0AA®0A
4、0BB®1A
5、ε试给出该文法生成语言的正规式。分析首先给出相应的正规式方程组(方程组中用“＋”代替正规式中的“
6、”)如下：Z=0A(1)A=0A+0B(2)B=1A+ε
7、(3)将(3)代入(2)中的B得A=0A+01A+0(4)对(4)利用分配律得A=(0+01)A+0(5)对(5)使用求解规则得A=(0+01)*0(6)将(6)代入(1)式中的A，得Z=0(0+01)*0即正规文法G[Z]所生成语言的正规式是:R=0(0
8、01)*0例2设有正规文法G：A®aB
9、bBB®aC
10、a
11、bC®aB试给出该文法生成语言的正规式。分析首先给出相应的正规式方程组(方程组中用“＋”代替正规式中的“
12、”)如下：A=aB+bB(1)B=aC+a+b(2)C=aB(3)将(3)代入(2)中的C得B=aaB
13、+a+b(4)对(4)使用求解规则得B=(aa)*(a+b)(5)(5)代入(1)中的B得A=(a+b)(aa)*(a+b)即正规文法G[A]所生成语言的正规式是:R=(a
14、b)(aa)*(a
15、b)2.正规式到正规文法的转换:(1)令VT=Σ(2)对任何正规式R选择一个非终结符Z生成规则Z®R并令S＝Z。(3)若a和b都是正规式，对形如A®ab的规则转换成A®aB和B®b两规则，其中B是新增的非终结符。(4)对已转换的文法中,形如A®a*b的规则，进一步转换成A®aA
16、b。(5)不断利用规则(3)和(4)进行变换，直到
17、每条规则最多含有一个终结符为止。例1将R=(a
18、b)(aa)*(a
19、b)转换成相应的正规文法。解：令A是文法开始符号，根据规则(2)变换为：A®(a
20、b)(aa)*(a
21、b)根据规则(3)变换为：A®(a
22、b)BB®(aa)*(a
23、b)对B根据规则(4)变换为A®aB
24、bBB®aaB
25、a
26、b根据规则(3)变换为A®aB
27、bBB®aC
28、a
29、bC®aB3.确定有限自动机(DFA)的定义：确定的有限自动机DFAM是一个五元式M=（S，å，δ，s0，F)(1)S是一个非空有限集，它的每个元素称为一个状态(2)å第10页(共10
30、页)是一个有穷字母表，它的每个元素称为一个输入符号，所以也称为输入符号字母表(3)δ是状态转换函数，是在S×å→S上的单值映射。δ（s,a）=s’意味着：当先行状态为s、输入字符为a时，将转到下一状态s’。我们称s’为s的一个后继状态。(4)s0∈S，是唯一的一个初态(5)FÍS，是一个终态集（可空）,终态也称可接受状态或结束状态。例如有DFAM=（{0,1,2,3},{a,b}，δ,0,{3}）其中δ定义为：δ（0，a）=1δ（0，b）=2δ（1，a）=3δ（1，b）=2δ（2，a）=1δ（2，b）=3δ（3，a）=
31、3δ（3，b）=3其它表示形式：状态转换矩阵和状态转换图NFA和DFA的不同在于：1)δ的值域是S的子集2)开始状态有不止一个3)在NFA中每个结点可射出若干条弧与别的结点相连接,每条弧用∑中的一个正规式做标记。例如NFAM=({0,1,2,3,4},{a,b},δ,{0},{1,2})其中：δ(0,a)={0,3}δ(0,b)={0,4}δ(1,a)={1}δ(1,b)={1}δ(2,a)={2}δ(2,b)={2}δ(3,a)={1}δ(3,b)=φδ(4,a)=φδ(4,b)={2}状态转换矩阵和状态转换图：01
32、2ab34{0,3}{0,4}{1}{1}{2}{2}{1}φ{2}φ例1试构造识别语言R=(a
33、b)*abb的NFAN,使L(N)=L(R)。首先将R表示成如下拓广转换图第10页(共10页)1.从NFAM构造正规式r举例从NFAM构造正规式r举例：第10页(共10页)1.由NFA确定DFA：将NFA确定化为DFA的原因：•使用NFA判定某个输入符号串的时候，可能出现不确定的情况：不知道下面选择那个状态。如果选择不好，该输入符号串可能不能到达终止状态。但是，我们不能说该输入符号串不能被该NFA接受•如果通过尝试的方法，
34、不断试探来确定输入符号串是否可被接受，那么判定的效率将降低。解决的方法是将NFA转换为等价的DFA例1构造下述文法G[Z]的有穷自动机。Z→0AA→0A
35、0BB→1A
36、ε解：f(Z,0)=Af(Z,1)=Φf(z,ε)=Φf(A,0)=A,Bf(A,0)=A,Bf(A,1)=Φf(A,ε)=Φf(B,0)=Φff(B,0)=Φf(
