Part3词法分析

《Part3词法分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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)

3、(aabb)(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

15、的正规产生式:A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

16、dASaAaA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)如何切分文本只有RE是不够的，还需要一些进行选择的规则大部分的语言，优先选择最长的匹配当最长匹配长度相同时，由优先级决定RE’s+优先级+最长匹配规则=词法分析器的定义有穷自动机有穷自动机（也称有限自动机）作为一种识别装置，它能准确地识别正规集，即识别正规文法所定义的语言与正规式所表示的集合，引入有穷自动机这个理论，正是为词

17、法分析程序的自动构造寻找特殊的方法和工具。有穷自动机分为两类：确定的有穷自动机（DFA）和不确定的有穷自动机（NFA）。其中“不确定”的含义是：对于某个输入符号，在同一状态上存在不止一种转换。确定的和不确定的有穷自动机都能而且仅能识别正规集，即它们能够识别正规表达式所表示的语言。确定的有穷自动机一个确定的有穷自动机(DFA)M是一个五元式：M=(S,∑,δ,s0,F)其中S是一个有限集，它的每个元素称为一个状态。∑是一个有穷字母表，它的每个元素称为一个输入字符δ是一个从S×∑至S的单值映射。δ(s,a)=s’意味着：当现行状态为s、输入字符为a时

18、，将转换到下一个状态s’。我们称s’为s的一个后继状态。s0∈S，是唯一的初态。FS，是一个终态集（可空）确定的有穷自动机DFAM=（