[第四章词法分析.ppt

第四章 词法分析 词法分析程序的设计 单词的描述技术、识别机制 词法分析程序的自动构造原理。 4.1 词法分析程序的设计 回顾 什麽是词法分析（lexical analysis）程序 又称词法分析器或扫描器，主要功能是逐个读入源程序字符并按照构词规则切分成一系列单词。单词是语言中具有独立意义的最小单位，包括保留字、标识符、运算符、标点符号和常量等。 词法分析是编译过程中的一个阶段，在语法分析前进行 。也可以和语法分析结合在一起作为一遍，由语法分析程序调用词法分析程序来获得当前单词供语法分析使用。 词法分析程序和语法分析程序的关系 词法分析程序的任务 词法分析程序的输出格式 词法分析的输出常采用二元式： （单词类别，单词自身的值） 单词类别通常用一个整数类码或单词记号表示，单词记号比整数码含义明确。 若还需记录单词的一些其它属性值:如标识符的类别、层次等，可将这些属性统一放到符号表中，并将单词的二元式表示为： （标识符，指向该标识符所在符号表中位置的指针） 词法分析程序的结构 将词法分析从语法分析部分独立出来的原因 使整个编译程序的结构更简洁、清晰、条例化 改进编译效率 增加编译系统的可移植性 词法分析程序的常用设计方法 手工构造 首先确定出能够识别程序中单词的确定的有穷自动机（ DFA），然后可以采用直接编程的方法或者表驱动的方法来构造词法分析器。 借助相关工具的自动构造 如：Lex编译系统  多数程序设计语言的单词的语法均可用正规文法来表示。 回顾： 正规文法(3型文法)：任一产生式的形式都为A→aB或A→a，其中A∈VN ，B∈VN ，a∈VT* 正规文法描述的是VT上的正规集。 例：程序设计语言中几类单词的描述规则：标识符、无符号整数、运算符…。（参见课本P52） 4.2 单词的描述工具-正规式 正规式（regular expression也叫正则表达式） 正规式是定义正规集的数学工具，是说明单词的模式(pattern)的一种表示法，用它描述单词符号时一般比正规文法更简洁。 正规式和正规集(即其描述的语言）的定义可以用递归的形式给出。 4.2 单词的描述工具-正规式 4.2 单词的描述工具-正规式 4. 仅有有限次使用上述三步骤而定义的表达式才是∑上的正规式，仅有这些正规式表示的字集才是∑上的正规集。 例4.2.1: 令?={a,b},则?上的正规式和相应正规集为 (1) a (2) a?b (3) ab (4) (a?b)(a?b) (5) a ? (6) (a?b)? (7) (a?b)?(aa?bb)(a?b)? 例4.2.2: 令?={l，d},则?上的正规式 r=l(l?d) ?定义的正规集为 正规式服从的代数运算规律： 设r,s,t为正规式，则它们满足如下运算规律： r|s=s|r r|(s|t)=(r|s)|t (rs)t=r(st) r(s|t)=rs|rt ; (s|t)r=sr|tr :或的分配律 ?r=r ; r?=r : ?是 “连接”的恒等元素 r|r=r : “或”的抽取律 正规文法和正规式的等价性 一个正规语言可用正规文法表示也可用正规式表示，两者具有等价性。一般而言正规式在描述语言时比正规文法更为简洁。 正规文法和正规式的等价性 将?上的正规式r转换成正规文法G=(VN,VT,S,P). 令VT= ?，产生式和VN按如下方法确定： 选择一非终结符S生成类似产生式的形式S?r，并将S定为文法G的识别符。 若x,y是正规式，对形如A?xy的正规式产生式，重写成：A?xB, B?y，B为新选的非终结符。 对形如A?x*y的正规式，重写成: A?xB, A?y, B?xB, B?y， B为新选的非终结符。 对形如A?x|y的正规式，重写成: A?x, A?y。 不断利用上述规则做变换，直到每个产生式都符合正规文法的形式即可。 例4.2.3：将r=a(a|d)*转换成相应的正规文法 正规文法和正规式的等价性 将正规文法转换为正规式 基本上是正规式到正规文法转换过程的逆过程。可反复采用以下三条规则，直到只剩下一个开始符号定义的正规式为止。 产生式A?xB, B?y对应正规式A=xy; 产生式A?xA|y对应正规式A=x*y; 产生式A?x, A?y对应正规式A=x|y; 正规文法和正规式的等价性 例4.2.4: 将G[S]转换为正规式 S?aA S?a A?aA A?dA A?a A?d 4.3 有穷自动机 有穷自动机(有限自动机)作为一种识别装置，它能准确地识别正规集(即正规式所表示的集合)。有穷自动机为词法分析程序的自动构造提供了有效的方法和工具。 有穷自动机