第3章有穷自动机(胡).ppt

第三章 有穷自动机 前述内容回顾 本章内容简介 3.1 词法分析程序概述 词法分析程序的功能 单词符号的种类 3.6扫描器的设计 词法分析的主要任务是对源程序进行扫描，从中识别出单词，它是编译过程的第一步，也是编译过程中不可缺少的部分。 本章介绍词法分析程序的手工构造方法。 4.1 词法分析概述 单词符号的种类 单词符号是语言的基本符号，它具有独立的意义且是不可再分的。程序语言中的大部分单词符号都属于下述几类之一。 ① 标识符：用以表示各种名字，如变量名，过程名等等； ② 保留字（或关键字）：如if，goto，begin，end等等，它实质上是标识符的一个子集。 ③ 数（整数或实数）：125，38，34.2,2.5e3等等； ④ 单分界符：如＋，－，*，/，（，），’，；，·等等； ⑤ 复合分界符：如**，/*，：＝等等。 单词的输出形式 扫描程序构造每个单词符号的内部表现形式,简称为记号串。 TOKEN串：（单词的种别码，单词的属性值） 种别码：区分单词的种类，一般用整数编码来表示。分类的方法是最大限度把各类单词区分开。常是一符一码（如，分界符和保留字），一类一码（如，整数）和统一一码（如，标识符）。 单词的属性值：单词符号的属性是指单词符号的特性或特征。属性值是反应特性或特征的值，是单词自身符号的机内编码，它是编译其它阶段所需要的信息。 注意： 1）对于 关键字、运算符和界符 种别码是一字一符。可以完全代表它自己。也就不用写自身值。 2）对于标识符和常数就必须依赖自身值来区分。 标识符自身值是它自己的字符串。 常数自身值是常数本身的二进制数值。 我们可以用指向标识符表或常数表的入口指针作为它们的自身值 下表是简单语言单词符号的内部表示： 例如：对于程序段 begin A+B*C /* Comment */ end 扫描程序将产生下面的结果： 又如： 程序段 if (a1) b=100 见 P 33 3.3 语言单词符号的两种定义方式—— 正规式 与 正规文法 多数程序设计语言的单词符号都能用正规文法来描述，但直观上比较繁琐，不利于词法分析程序的构造。 正规表达式是用于描述称之为正规集的语言类的另一种表示形式，习惯用 RE 来表示。 例如： 表示标识符的文法用左线性文法来描述： 标识符→字母|标识符字母|标识符数字 可抽象为: I→ l | I l | I d 我们可以用正规式来描述 l (a | b)* 3.3.1 正规表达式的定义 例：设有字母表∑={a,b }则根据正规式与正规集的定义有： (1) a和b正规式,则相应正规集为 L(a )={a}, L(b )={b}, (2) a | b 是正规式，则相应正规集为 L(a | b) = L(a) ∪ L(b) = { a , b } (3) ab是正规式 , 则相应正规集为 L(ab) = L(a)L(b) = {a}{b} = {ab} (4) (a | b)* 是正规式 , 则相应正规集为 L((a | b)*)=(L(a | b))*= { a, b }*={ε,a,b,ab,ba, …} (5) ba* 是正规式 , 则相应正规集为 L(ba*)=L(b)L(a*)={b,ba,baa,baaa,…} (6) (a | b)*(aa | bb ) (a | b)*是正规式 , 则相应正规集为 L((a | b)*(aa | bb ) (a | b)*) =L((a | b)*)L(aa | bb ) L((a | b)*) ={a,b}*{aa,bb}{a,b}* 注意：{a,b}*的任一子集不能认为是正规集。如 {anbn |n≥1}就不是一个正规集，不能用正规式来描述，也不能用正规文法来描述，只能用上下文无关文法来描述。 例3.2 设∑={+, -, ., d, E, ε}，正规表达式： ( + | - |ε) d (d)* 表示带符号（或不带符号）的数的集合，d代表数字类。 例3.3 设∑={+, -, ., d, E, ε}， 表示浮点数集合的正规表达式为： ( + | - |ε) (d d*.d* | d d*.dd*) (ε| E ( + | - |ε) dd*) 其中，第一部分表示任选的字符；第二部分表示具体数，该部分必须包括一个小数点，并至少有一个数字在前面或后面；第三部分是任选的指数 正规式的等价 如果正规式R1和R2描述的正规集相同（即描述的语言相同）