第4章-词法分析(完).ppt

第4章词法分析第4章词法分析第4章词法分析主要内容：单词的描述工具：正规文法和正规式单词识别系统：有穷自动机词法分析程序的设计词法分析程序的自动构造原理第4章词法分析学习目标:掌握：词法分析程序的构造，正规式和正规文法到有穷自动机的转换，NFA到DFA的*转换、DFA的化简理解：正规文法、正规式、DFA的概念、NFA的概念了解：词法分析程序的自动构造工具第4章词法分析4.1词法分析程序的设计4.2 单词的描述工具4.3 有穷自动机4.4 正规式和有穷自动机的等价性4.5 正则文法和有穷自动机的等价性§4.1词法分析程序的设计主要任务：从左到右逐个字符地对源程序进行扫描，产生一个个单词序列，用以语法分析。将词法分析程序设计成子程序，每当语法分析程序需要一个单词时，调用该子程序。§4.1词法分析程序的设计词法分析程序输出的单词符号：关键字：如begin,if,while等等；标识符：如常量名，变量名，过程名等等；常数：25，3.14159，TRUE，”ABC”等；运算符：如+，*，=等；界符：如逗号，分号，括号等。所输出的单词符号常常采用二元式表示：（单词种别，单词自身的值）§4.1词法分析程序的设计例:源程序beginvarsum,first,count:real;

sum:=first+count*10

end.§4.2单词的描述工具作用:描述单词的构成规则,基于这类描述工具建立词法分析技术,进而实现词法分析程序的自动构造.工具:正规文法 正规式(RegularExpression)§4.2单词的描述工具1、正规文法 多数程序设计语言单词的语法都能用正规文法(3型文法)描述正规文法回顾文法的任一产生式α→β的形式都为A→aB或A→a，其中A，B∈VN，a∈VT。正规文法描述的是VT*上的正规集§4.2单词的描述工具例如: 用l表示a~z中的任一英文字母，d表示0~9中任一数字描述标识符的正规文法为 标识符→l｜l字母数字 字母数字→l｜d｜l字母数字｜d字母数字描述无符号整数的正规文法 无符号整数→d｜d无符号整数§4.2单词的描述工具2、正规式(正则表达式)

RegularExpression对于字母表∑，我们感兴趣的是它的一些特殊字集——正规集。正规式是描述正规集的方便工具。§4.2单词的描述工具正规式与正规集的递归定义ε和φ都是∑上的正规式，它所表示的正规集分别为｛ε｝和Ф；对于任何ａ∈∑，ａ是∑上的正规式，它所表示的正规集为｛ａ｝；§4.2单词的描述工具假定ｅ1和ｅ2都是∑上的正规式，他们所表示的正规集分别为Ｌ(ｅ1)和Ｌ(ｅ2)，那么，以下也都是正规式和他们所表示的正规集；§4.2单词的描述工具仅由有限次使用上述三步定义的表达式才是∑上的正规式，仅由这些正规式所表示的字集才是∑上的正规集。§4.2单词的描述工具§4.2单词的描述工具正规式的代数性质：设r，s，t是正规式，正规式的代数规律是： r｜s=s｜r “｜”满足交换律 r｜(s｜t)=(r｜s)｜t “｜”的结合律 (rs)t=r(st) “.(连接)”的结合律 r(s｜t)=rs｜rt (r｜s)t=rt｜st 分配律 εr=rε=r ε是“.”的恒等元素 r?r=r “｜”的抽取律 r?=??r?rr?… §4.2单词的描述工具程序中的单词都能用正规式来定义 令l为a~z的字母，d为0~9的数字 e1=l(l|d)* e1表示标识符集合 e2=dd* e2表示无符号整数注： 标识符→l｜l字母数字字母数字→l｜d｜l字母数字｜d字母数字正规式比正规文法更容易让人理解单词是按怎样的规律构成的，且可以从某个正规式自动地构造识别程序。§4.2单词的描述工具3、正规文法和正规式间的转换等价性：对任意一个正规文法G，存在一个定义同一语言的正规式r对任意一个正规式r，存在一个定义同一语言的正规文法G§4.2单词的描述工具§4.2单词的描述工具例:将r=a(a|d)*转换成相应的正则文法令转换成文法G=(VN,VT,P,S)其中VT={a,d}，文法开始符为S首先形成S→a(a|d)*,然后变换: