《词法分析部分总结》PPT课件.ppt

《《词法分析部分总结》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、词法分析部分总结田聪1描述：用正规式对模式进行描述；构造NFA：为每个正规式构造一个NFA；确定化：将NFA转换成等价的DFA；最小化：优化DFA，使其状态数最少；构造词法分析器：由DFA构造词法分析器（表驱动，直接编码，LEX）。构造词法分析器的一般方法和步骤2涉及到的形式化概念正则表达式（正规式）NFADFA正则表达式例如：Char(char

2、digit)*，…字符串，abbA111,….NFADFA正则语言（正规集）3正则语言正则语言上下文无关语言上下文有关语言递归可枚举语言4正则语言正则语言正则表达式有限

3、状态自动机上下文无关语言上下文无关文法非确定的下推自动机上下文有关语言上下文有关文法线性有界自动机（特殊的图灵机）递归可枚举语言短语结构图灵机5AlgebraicLawsforRE’sUnionandconcatenationbehavelikeadditionandmultiplication.+iscommutative(可交换的)andassociative(可结合的)a+b=b+a,a+b+c=a+(b+c)concatenationisassociative(可结合的)a.b.c=a.(b.c)Conc

4、atenationdistributesover+(可分配的)a.(b+c)=a.b+a.cException:Concatenationisnotcommutative(可交换的)a.b≠b.a6IdentitiesandAnnihilators∅istheidentity(单位元)for+.R+∅=R.εistheidentity(单位元)forconcatenation.εR=Rε=R.∅istheannihilator(零元)forconcatenation.∅R=R∅=∅.7正则语言相关内容如何证明正则

5、表达式和NFA的等价性？（1）WeneedtoshowthatforeveryRE,thereisanautomatonthatacceptsthesamelanguage.（2）Andforeveryautomaton,thereisaREdefiningitslanguage.8REtoε-NFA:BasisSymbola:ε:aε9REtoε-NFA:Induction1–UnionForE1ForE2ForE1E2εεεε10REtoε-NFA:Induction2–ConcatenationForE1

6、ForE2ForE1E2ε11REtoε-NFA:Induction3–ClosureForEForE*εεεε12正则语言相关内容如何证明正则表达式和NFA的等价性？（1）WeneedtoshowthatforeveryRE,thereisanautomatonthatacceptsthesamelanguage.（2）Andforeveryautomaton,thereisaREdefiningitslanguage.13FromAutomatatoREArden’sruleForanysetsofstrin

7、gsSandT,theequationX=SX+ThasX=S*Tasasolution.Moreover,thissolutionisuniqueifεnotinS.14FromAutomatatoREGivenanautomatonAAhasstates{q0,…,qn}withq0beingthestartstateLetXidenotethesetofstringsacceptedbyAstartinginstateqiThus,L(A)=X0WecanwriteanequationforeachXi,d

8、efiningitintermsofthesetscorrespondingtoitssuccessorstates.15FromAutomatatoREq2q0q3q1b,caccaa,b,ca,bbA016FromAutomatatoREq2q0q3q1b,caccaa,b,ca,bbA0(0)X0=aX1+bX3+cX3(1)X1=aX3+bX2+cX0+ε(2)X2=aX3+bX3+cX0(3)X3=aX3+bX3+cX3X3=(a+b+c)X3+∅,byArden’srule:X3=(a+b+c)*∅=

9、∅(0)X0=aX1(1)X1=bX2+cX0+ε(2)X2=cX0Substituing(0)and(2)in(1):X1=(bc+c)aX1+ε=((bc+c)a)*(byArden’srule)X0=a((bc+c)a)*17DFA-to-REAnotherapproachPage93,theorem3.4.（形式语言与自动机）Inductiononk-path.1