第四章-词法分析.ppt

第四章词法分析本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。4.1词法分析程序4.2正规表达式与正规集（正规语言）4.3有穷自动机4.4词法分析程序的自动构造?本章重点单词的描述工具单词的识别系统设计和实现词法分析程序首先需要描述和刻画程序设计语言中的原子单位——单词，其次需要识别单词和执行某些相关的动作。描述程序设计语言的词法的机制是正则表达式，识别机制是有穷状态自动机。回顾什麽是词法分析程序实现词法分析（lexicalanalysis）的程序逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。词法分析是编译过程中的一个阶段，在语法分析前进行。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。词法分析程序和语法分析程序的关系词法分析工作从语法分析工作独立出来的原因：简化设计改进编译效率增加编译系统的可移植性正规表达式与正规集（正规语言）程序设计语言中的单词是基本语法成分.单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造.首先表述一些基本术语和概念.符号一个抽象实体,我们不再形式地定义它(就象几何中的”点”一样).例如字母是符号,数字也是符号。字母表字母表是元素的非空有穷集合，我们把字母表中的元素称为符号，因此字母表也称为符号集。不同的语言可以有不同的字母表，例如汉语的字母表中包括汉字、数字及标点符号等。PASCAL语言的字母表是由字母、数字、若干专用符号及BEGIN、IF之类的保留字组成。符号串的连接：设x和y是符号串，它们的连接xy是把y的符号写在x的符号之后得到的符号串.由于ε的含义，显然有εx=xε=x。例如x=ST，y=abu，则它们的连接xy=STabu，看出｜x｜=2，｜y｜=3，｜xy｜=5符号串的方幂：符号串自身连接n次得到的符号串an定义为aa…aan个aa1=a,a2=aa且a0=ε例；若x=AB则:x0=εx1=ABx2=ABABx3=ABABABxn=xxn-1=xn-1x(n0)两个符号串集合A和B的乘积定义为AB=?xy|x?A且y?B?若集合A=?ab,cde?集合B=?0,1?则AB=?ab1,ab0,cde0,cde1?使用?*表示?上的一切符号串（包括ε）组成的集合。Σ*称为Σ的闭包。?上的除ε外的所有符号串组成的集合记为?+。Σ+称为Σ的正闭包。

例：Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}正规式正规式也称正则表达式,正规表达式（regularexpression）是说明单词的模式(pattern)的一种重要的表示法（记号），是定义正规集的数学工具。我们用以描述单词符号。下面是正规式和它所表示的正规集的递归定义。定义（正规式和它所表示的正规集）：设字母表为?，辅助字母表?`={?，?，?，?，?，?，?}。1。?和?都是?上的正规式，它们所表示的正规集分别为{?}和{}；2。任何a??，a是?上的一个正规式，它所表示的正规集为{a}；3。假定e1和e2都是?上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1),e1?e2,e1?e2,e1?也都是正规式,它们所表示的正规集分别为L(e1),L(e1)?L(e2),L(e1)L(e2)和(L(e1))?。4。仅由有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集。

正规式中的符号

其中的“?”读为“或”（也有使用“+”代替“?”