编译原理3词法分析ppt课件.ppt

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

1、Part3词法分析授课：胡静内容提要词法分析器的作用词法分析程序的设计与实现——状态图词法分析程序的自动生成——有穷自动机正则表达式与有限自动机问题的提出如果只向前看一个字符，不能够确定我们将要读入的是哪种类型的token如果token的开头是“i”，那么它一定是标识符么？如果token的开头是“2”，那么它一定是一个整型的常数么？如果我们通过上面的类似“插入”式的方法来写识别token的程序，这样的程序不容易写正确，而且也不容易维护因此需要一个更加有原理性的方法：词法分析器的生成器，可以自动产生有效的词法分析器。（例如lex，flex，Jlex）一般说来，没有限制

2、的向前看是必要的一些问题如何明确的描述tokens2.e020.e-012.0000“”“x”“\”“”’”如何将文本分割成tokensif(x==0)a=x<<1;if(x==0)a=x<1;如何描述tokens我们可以使用正则表达式来描述程序设计语言中的tokens。正则表达式的定义如下：正则集合（语言）正则表达式的例子令={a，b}，正则表达式正则集合集a{a}ab{a,b}ab{ab}(ab)(ab){aa,ab,ba,bb}a{,a,a,……任意个a的串}(ab){,a,b,aa,ab……所有由a和b组成的串}(ab)(aab

3、b)(ab){上所有含有两个相继的a或两个相继的b组成的串}正则表达式的例子={a，b}，r=a(ab)定义的正则集合:{a,aa,ab,abb,……}={d，，e，+，-},则上的正则表达式d(dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。若两个正则表达式所表示的正则集合相同，则认为二者等价。两个等价的正则表达式U和V记为U=V。例如：U=(ab)，V=ba又如：U=b(ab),V=(ba)b再如：U=(ab),V=(ab)正则表达式的性质设U、V和W都是正则表达式，则如下关系普

4、遍成立：U

5、V=V

6、U（交换律）U

7、(V

8、W)=(U

9、V)

10、W（结合律）U(VW)=(UV)W（结合律）、U(V

11、W)=UV

12、UW（分配律）(V

13、W)U=VU

14、WU；εU=Uε=Urr=rr=rrr…“或”的抽取律正则文法和正则表达式对上的正则表达式U,存在一个正则文法G=(VN,VT,P,S):L(G)=L(r)初始，VT=,SVN，生成正则产生式SU(R.1)对形如Ar1r2的正则产生式：Ar1BBr2BVN(R.2)对形如Arr1的正则产生式：ArBAr1BrBBr1BVN(R.3)对形如Ar1r2的正则产生式:A

15、r1Ar2不断应用R做变换，直到每个产生式右端只含一个VN正则文法和正则表达式对G=(VN,VT,P,S),存在一个=VT上的正则表达式r:L(r)=L(G)AxB,ByA=xyAxAyA=xyAxyA=xy正则文法和正则表达式举例例1：r=a(ad)VT={a,d}Sa(ad)R.1SaAA(ad)R.2A(ad)BAB(ad)BBR.3G[s]:SaAAVT={a,d}AaBVN={S,A,B}AdBBaBBdBBP正则表达式和正则文法举例G[s]:SaAAaAAdASaAaA

16、dSaAaAaAadAdA(ad)A(ad)A(ad)(ad)S=a(ad)(ad)a=a((ad)(ad))=a((ad)+)R=a(ad)有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正则集合，即识别正则文法所定义的语言与正则表达式所表示的集合，引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）。其中“不确定”的含义是：对于某个输入符号，在同一状态上存在不止一种转换。确定的和不

17、确定的有穷自动机都能而且仅能识别正则集合，即它们能够识别正则表达式所表示的语言。确定的有穷自动机一个确定的有穷自动机(DFA)M是一个五元式：M=(S,∑,δ,s0,F)其中S是一个有限集，它的每个元素称为一个状态。∑是一个有穷字母表，它的每个元素称为一个输入字符δ是一个从S×∑至S的单值映射。δ(s,a)=s’意味着：当现行状态为s、输入字符为a时，将转换到下一个状态s’。我们称s’为s的一个后继状态。s0∈S，是唯一的初态。FS，是一个终态集（可空）确定的有穷自动机DFAM=（{S，U，V，Q}，{a，b}，δ，S，{Q}）其中f定义为：δ（S，a）=Uδ