本章将讨论词法分析程序的设计原则，单 词的描述技术，识别机制及词法分析程序 的自动构造原理。 4.1 词法分析程序 4.2 正规表达式与正规集（正规语言） 4.3 有穷自动机 4.4 词法分析程序的自动构造第四章 词法分析本章重点 单词的描述工具 单词的识别系统 设计和实现词法分析程序 首先需要描述和刻画程序设计语言中的原子 单位单词，其次需要识别单词和执行某 些相关的动作。 描述程序设计语言的词法的机制是正则表达 式，识别机制是有穷状态自动机。回顾 什麽是词法分析程序4实现词法分析（lexical analysis）的程序逐个读入源程序字符并按照构词规则切分成 一系列单词。 单词是语言中具有独立意义的最小单位，包 括保留字、标识符、运算符、标点符号和常 量等。 词法分析是编译过程中的一个阶段，在语法 分析前进行 。也可以和语法分析结合在一起 作为一遍，由语法分析程序调用词法分析程 序来获得当前单词供语法分析使用。词法分析程序的任务v 词法分析是编译的第一个阶段。v 词法分析所做的工作也叫“扫描处理”，因 此，词法分析程序也常被叫做“扫描器”。v 词法分析的任务是识别单词，为语法分析提供语法单位序列。v 单词的形式一般为：v 词法分析程序的输入是源程序，输出是一定形式的单词序列。单词类别 单词自身值词法分析程序和语法分析程序的关系源程序词法分析程序语法分析程序Tokenget token.词法分析程序的主要任务： 读源程序，产生单词符号词法分析程序的其他任务： 滤掉空格，跳过注释、换行符 追踪换行标志，复制出错源程序， 宏展开，词法分析程序的要求v 词法分析程序必须按照一定的分类标准将源程 序中的单词进行识别并进行预加工处理。v 常见的单词分类形式有两种： 1、一字一类型 2、按下列方式将单词分为5种类型关键字：也叫保留字、基本字，是由程序语言定义的具有固定意 义的标识符。 标识符：开发人员自己定义的用来表示变量、数组等名称的。 常数：包括整型、实型、布尔型、字符及字符串型等。 运算符：包括+、*、/、 以及布尔运算等。 界符：逗号、分号、括号、回车、换行等将语法单位分隔开的符号 。词法分析程序的工作阶段v 词法分析工作可以分成两个工作阶段：1、输入、预处理阶段：预处理子程序。2、识别单词符号：超前搜索法。所谓超前搜 索法，是指想要识别出某个字符串是否是一个 单词，必须超前扫描一个或多个字符，直到能 够肯定某个字符序列是一个单词为止。 编译程序的“遍数”影响词法分析的设 计。词法分析工作从语法分析工作独立出来的 原因： 简化设计 改进编译效率 增加编译系统的可移植性 正规文法和正规式v 多数程序设计语言的单词的词法规则都 能用正规文法来描述。 v正规文法所描述的式文法的字符表Vt*上 的正规集。 v 正规式也称正则表达式，也是表示正规 集的工具 v 正规式服从的代数规律： r|s=s|r r|(s|t)=(r|s)|t (rs)t=r(st) r(s|t)=rs|rt (s|t)r=sr|trr=r r=r正规式正规式也称正则表达式,正规表达式（ regular expression）是说明单词的模式 (pattern)的一种重要的表示法（记号）， 是定义正规集的数学工具。我们用以描 述单词符号。下面是正规式和它所表示 的正规集的递归定义。定义（正规式和它所表示的正规集）：设字母表为，辅助字母表=， ，。1。 和都是上的正规式，它们所表示的正 规集分别为和 ；2。任何a ，a是上的一个正规式，它所表示的正规集为a；3。假定e1和e2都是上的正规式，它们所表示的正规集分别为L(e1)和L(e2)，那么，(e1), e1 e2, e1e2, e1也都是正规式,它们所表示的正规集分别为L(e1), L(e1)L(e2), L(e1)L(e2)和(L(e1)。4。仅由有限次使用上述三步骤而定义的表达式才是上的正规式，仅由这些正规式所表示的集合才是上的正规集。正规式中的符号其中的“”读为“或”（也有使用“+”代替 “” 的）；“ ”读为“连接”；“”读为“闭包”（即，任意有限次的自重复连接）。在不致混淆 时，括号可省去，但规定算符的优先顺序为 “”、“ ”、“” 。连接符“ ”一般可省略不 写。“”、“ ”和“” 都是左结合的。例子令=a，b， 上的正规式和相应的正规集的例 子有： 正规式 正规集 a a ab a,b ab ab (ab)(ab) aa,ab,ba,bb a ,a,a, 任意个a的串正规式 正规集 (ab) ,a,b,aa,ab 所有由a 和b组成的串 (ab)(aabb)(ab) 上所有含有两个相继的a或两个相继的b 组成 的串讨论下面两个例子 例 令=l，d，则上的正规式 r=l(l d) 定义的正 规集为: l,ll,ld,ldd,其中l代表字母,d代表 数字,正规式 即是 字母(字母|数字) ,它表示的 正规集中的每个元素的模式是“字母打头的字 母数字串”,就是Pascal和 多数程序设计语言允 许的的标识符的词法规则. 例 =d，e，+，-, 则上的正规式 d(dd )(e(+- )dd ) 表示的是无符号数的集合。其中d为09的数字 。 程序设计语言的单词都能用正规式 来定义.4若两个正规式e1和e2所表示的正规集相同 ,则说e1和e2等价,写作e1=e2。 例如： e1= (ab)， e2 = ba 又如： e1= b(ab) , e2 =(ba)be1= (ab) , e2 =(ab)4设r,s,t为正规式，正规式服从的代数规律 有： 1。rs=sr “或”服从交换律 2。r(st)=(rs)t “或”的可结合律 3。(rs)t=r(st) “连接”的可结合律 4。r(st)=rsrt (st)r=srtr 分配律 5。 r=r, r=r 是“连接”的恒等元素 零一律 6。 rr=rr=rrr “或”的抽取律 正规文法和正规式对上的正规式r ,存在一个G=(VN,VT,P,S)： L(G)=L(r)初始， VT= ,S VN ，生成正规产生式 Sr (R1) 对形如 Ar1r2的正规产生式： Ar1BBr2BVN (R2)对形如Arr1的正规产生式： ArBAr1BrBBr1 BVN (R3)对形如Ar1r2的正规产生式:Ar1A r2 不断应用R做变换，直到每个产生式右端至多有一个VN例 r=a(ad)Sa(ad)SaA A(ad) A(ad)B AB(ad)B BGs: SaA A VT=a,d AaBVN=S,A,B AdB BaB BdB B正规文法和正规式对G=(VN,VT,P,S),存在一个 =VT上的正规式r : L(r)=L(G)AxB, By A=xy AxAy A=xyAxy A=xy正规文法和正规式Gs:SaA|aAaAadAd A(ad)A(ad) A(ad)(ad)S=a(ad)(ad)a =a(ad)(ad) =a(ad)R=a(ad)正规表达式与正规集（正规语言）程序设计语言中的单词是基本语法成 分.单词符号的语法可以用有效的工 具加以描述，并且基于这类描述工具 ，实现词法分析程序的自动构造.3型文法产生的语言是有穷自动机（FA） 所接受的集合。定理 设G=（VN，VT，P，S）是3型文法，则存在一个有 穷自动机 M=(K, , f, A, Z)，使得L(M)=L(G) 有穷自动机NFA M 这样构造： l= VT lK= VN N, N为一个新状态,它不在VN中 lA=S lZ=N l对G中的形如 DtB的产生式,t为终结符或,有 f(D,t)=B；对G中形如Dt的产生式， t为终结符或,有 f(D,t)=N;对VT中的每一个a ,有f(N,a)=状态转换图（状态图）v 状态转换图是为了识别正规文法而专门设计 的有向图。一个DFA可以表示成一个状态图。 v 状态转换图包含有穷个状态，除开始状态不 代表任何非终结符号外，每个状态结点都代表 文法的非终结符号；状态图的转换弧上所标记 的符号是文法的终结符号。 如规则：U:=Va的状态图为：VUa正规文法与状态转换图v 左线性文法：其规则形如： U:=a U:=Wa v 右线性文法：其规则形如： U:=a U:=aW v 右线性文法利用状态转换图的识别过程实 际上是一种自上而下的推导过程。v 左线性文法利用状态转换图的识别过程实际上是一种自下而上的规约过程。状态转换图的构造法v 左线性正规文法的状态转换图的构造步骤：1、增加结点S为开始状态（假定文法的符号中不存在符号S）2、以每一个非终结符号为状态结点3、对于形如U:=a的每条规则，引一条从开始状态S到状态U的弧 ，弧的标记为a；而对形如U:=Va的规则，引一条从状态V到U的 弧，其标记为a。4、将识别符号作为终止状态。v 右线性正规文法的状态转换图的构造步骤：1、增加结点Z为终止状态（假定文法的符号中不存在符号Z）2、以每一个非终结符号为状态结点3、对于形如U:=a的每条规则，引一条从状态U到终止状态Z的弧 ，弧的标记为a；而对形如U:=aV的规则，引一条从状态U 到V的 弧，其标记为a。4、将识别符号作为开始状态。G：SaA|bBAbB|aD|aBaA|bD|bDaD|bD|a|bBASaaabbb a,bDZaba b定理 已知一有穷自动机M= (K, , f, A, Z),存 在有一个3型文法G = （VN，VT，P，S）,使 得L(G)=L(M) G 的定义：lVT = lVN= KlS = A l若 f(D,t)=B ，则DtB在P中 若 f(D,t)=B ，且B在Z中，则Dt在P中。G：SaA|bBAbB|aD|aBaA|bD|bDaD|bD|a|bDBASaaabba,bb有穷自动机v 有穷自动机也称有限自动机，是一种能准确识 别正规集的识别装置。v 有穷自动机分为确定的有穷自动机（DFA）和 非确定的有穷自动机（NFA）两类。v 一个DFA可以表示成一个状态图。v 对于任意一个给定的NFA，都存在一个与之等 价的DFA。v 我们可以用“子集法”将NFA转换成DFA。v 不存在两个或两个以上的状态互相等价的DFA 称为化简了的DFA。关于有穷自动机我们将讨论如下