《词法分析及词法分析程序..》由会员分享，可在线阅读，更多相关《词法分析及词法分析程序..（67页珍藏版）》请在金锄头文库上搜索。
1、1,第三章 词法分析及词法分析程序,2,词法分析程序设计的流程,1、各类单词表示成不同的正规文法Gi 2、求正规文法Gi对应的正规表达式 3、由各个正规表达式构造对应的-NFA 4、由各个-NFA组合成一个大的-NFA 5、大的-NFA确定化、最小化得到DFA M 6、DFA M就是构造词法分析程序的流程图 7、按照DFA M编写词法分析程序,3,主要内容,3.1 设计扫描器时应考虑的问题 符号的内部表示、识别约定和策略、源程序的输入和预处理 3.2 正规文法和状态转换图 正规文法状态转换图，状态转换图的实现 3.3 有限自动机（FA） DFA、NFA以及二者的等价性；具有动作的NFA的确定化
2、；DFA状态数的最小化 3.4 正规表达式与正规集 正规文法正规式FA 3.5 词法分析程序的实现（自学） 编写、自动生成,4,词法分析的任务,词法分析的任务 扫描输入串中的字符，从中识别出具有独立意义的基本语法单位：单词，生成单词序列。 剥去源程序中的注释（块、行）和“空白”符 预处理宏处理与文件包含 词法分析程序亦称为扫描器 设计和实现扫描器的相关问题： 描述语言中各种单词的结构：3型文法及其正规式 识别源程序中的各个单词：状态转换图或有限自动机,5,扫描器的功能,词法分析器,语法分析器,6,程序语言的单词（1）,单词：同类词文的总称 词文：源程序中能匹配某一记号的字符串 模式：描述用字符
3、串构成单词的规则,7,程序语言的单词（2）,8,3.1 设计扫描器时应考虑的问题,3.1.1 词法分析的两种处理方式 将词法分析纳入到语法分析中进行 词法分析与语法分析分开来进行 描述单词结构比描述语法结构简单，仅用3型文法就够了； 将单词识别从语法分析中分离出来，可采用更有效的工具（状态转移图、有限自动机等）实现； 有些语言（如FORTRAN）的单词识别与前后文相关，将词法分析独立出来，有利于实现统一的语法分析； 使编译程序各部分独立出来，有利于设计、调试和维护 逻辑上的划分，不是指编译程序的执行流程,9,词法分析作为单独的一遍（多遍扫描） 大部分编译时间花在扫描字符上，独立出来便于集中处理
4、. 单词的词法规则简单，可建立特别适用于这种文法的有效技术，实现词法分析的自动生成. 整个编译程序结构简单，清晰，产生中间文件，占内存. 词法分析作为一个独立的子程序，供语法分析程序调用 （单遍扫描） 语法分析调用时，返回一个单词符号. 无中间文件，省内存，编译效率高.,两种具体的实现方式,10,3.1.2 单词符号的内部表示 词法分析器的输出形式 (1) 单词符号的种类 保留字：如begin，end,do等用户不能使用 标识符：由用户定义 无符号整数：如124 单字符分界符：+，*，/ ，；， （ ，），： 双字符分界符：/，/*，*/，:=等,11,(2)单词符号的表示形式二元组 二元组：
5、（单词类别，单词自身值） 单词类别：说明单词属于哪一类，常用助记符或 整数编码表示. 例：标识符用4 表示 + 用8表示 * 用10表示 单词自身值 一种类只有一个单词，不必给出单词自身值.因为 根据类别编码能完全确定. 一种类含有多个单词，必须给出单词自身值予以 区别。,12,一般： 保留字、运算符和分界符都是一个符号一种类别，不需单词自身值. 如 + 类别8, + 的二元组 （8，-） 标识符整体作为一个类别,其单词自身值采用自身的字符串编码表示. 如标识符类别为5，AB的二元组(5，AB） 常数按类型分类别：单词自身值采用自身 的二进制形式. 如整数类别为20，整数4的二元组(20，10
6、0）,13,3.1.3 识别标识符的若干约定和策略 约定： (1)标识符中的字符个数超过最大允许长度，截去尾部. (2)不超过最大长度的标识符，则按“尽可能长”的原则匹配. 如：如果标识符最大长度为6,则identifier识别为identi，而不是identifier; 而NO23A可识别出NO23A标识符,而不是NO、23和A,14,禁止关键字作为标识符的前缀的语言系统（如标准FORTRAN和PASCAL） DO10I会识别为DO 10 I，而不是将之识别为一个标识符。 若允许关键字作为标识符的前缀（非标准FORTRAN） DO99K=1,10 DO循环语句 DO99K=1.10 变量赋值
7、 IF(5.EQ.M)X=5 IF语句 IF(5)=55 函数赋值,15,单词符号的识别超前扫描技术,超前扫描技术：在无法判别和识别当前单词时，先向前扫描若干个字符，直到可以进行判断和识别为止。 嵌套括号的分层 由外向内编号：第一层，第二层， 语句内容的分层 按包含它的括号层次确定 不被括号包含的语句内容称为属于第零层 不被括号包含的等号和逗号分别称为零层等号和零层逗号 利用超前扫描到的零层等号和零层逗号来识别单词符号,16,超前扫描技术示例 DO99K=1,10 DO循环语句 DO99K=1.10 变量赋值 IF(5.EQ.M)X=5 IF语句 IF(5)=55 函数赋值 包含零层等号的语句
8、：赋值语句、DO语句、函数定义语句以及某些逻辑IF语句 既包含零层等号，也包含零层逗号的语句：DO语句 如，函数或数组赋值语句 f(a1,a2,an)=e 函数语句： f不出现在数组说明符中 数组赋值语句： f出现在数组说明符中 再如，扫描到字符,还需继续向前扫描 ,（左移）,=,=（复合赋值）,17,回退字符,在超前扫描结束后，还要“回退”字符，即将超前扫描的字符退回输入缓冲区。 实现回退的数据结构：堆栈 回退：将要回退的字符依次压入堆栈。 扫描：检查堆栈是否为空，如果不为空，则从栈顶读取后续字符，否则从输入字符串读取。 书中 P45程序3-1给出了使用堆栈实现多字符回退的算法。,18,3.
9、1.4 源程序的输入及预处理 缓冲输入：将磁盘上的源程序分批送入缓冲区，等待扫描器处理。可以提高读盘效率和方便扫描器工作。 输入系统：一组完成源程序输入的函数或者子程序，支持读盘、超前搜索、多字符回退等操作 Lex中的扫描缓冲区实例：P46,图3-2 预处理:消除无用空白、回车、换行、制表、注释、区分标号区、续行号（FORTRAN）等.,19,3.2 正规文法和状态转换图,单词的描述：正规文法定义了3型语言，常见的单词可由正规文法定义。 单词的识别：状态转换图可用于识别3型语言，它是设计和实现扫描器的一种有效工具，是有限自动机的直观图示。,20,3.2.1 由正规文法构造状态转换图,程序设计语
10、言的单词都能用正规文法描述，例如，标识符可定义为： 字母 数字 字母 若把字母、数字视为终结符，则上述产生式为左线性文法，是正规文法。 若我们用d表示0-9间的数字，则C语言的的文法是右线性文法，也是正规文法（见P48）,21,状态转换图,状态转换图：由一组矢线连接的有限个结点所组成的有向图。 每个结点代表在识别分析过程中扫描器所处的状态，其中含有一个初始状态和若干个终态。在图中，状态用圆圈表示，终态用双层圆圈表示。 状态之间可用有向边连接，其上标记一字符a，表示从有向边的射出状态出发，识别一字符a后，将进入箭头所指状态（结点） 凡能用正规文法描述的语言，均可由某种有限状态算法状态转换图进行分
11、析。,22,由右线性文法构造状态转换图,设G=(VN,VT,P,S)是一右线性文法，并设|VN|=k,则所要构造的状态转换图共有k+1个状态(结点)。用VN中的每个符号分别标记其中的k个结点，且令G的开始符S为初态结点；余下的一个结点作为终态结点，用F(VN)标记。,23,A,状态转换图的构造原则 G的每一个非终结符号代表一结点(状态) 开始符号S作为初始状态 设一符号F不属于V作为终止状态 形如AaB的规则 a 形如Aa的规则 a 特别:A 未曾在A的射出弧中 出现过的终结符号 某些情况下也可考虑直接将A作为终态,B,S,F,B,A,A,F,A,F,A,24,例:GZ: Z0U1V U 1Z
12、1 V 0Z0,25,例:GZ: 状态转换图: Z0U1V U 1Z1 1 V 0Z0 0 1 初态 1 0 0,Z,U,V,F,26,无符号数文法举例,0. d | | d 1. d | | E | | d 2. E | d | d 3. d | d 4. d | + | - | d 5. d | d 6. d | d d表示09之间的数字,27,无符号数文法对应的状态转换图,例如,P48中定义的无符号数的文法对应的状态转换图为(化简后): 可识别的无符号数形式：dmdm-1d0 . d-1d-n E ddd,28,利用状态转换图识别符号串的方法,对于已给的字符串w=a1a2an,aiVT,
13、利用状态转换图对w 识别的步骤如下: (1)从初始状态S出发,自左至右逐个扫描w的各个字符(当前为a1),此时在结点S所射出的诸矢线中,寻找标记为a1的矢线(若不存在,则表明w有语法错误),读入a1并沿矢线所指方向前进,过渡到下一状态(设为A1). (2)设当前处在Ai状态,所扫描的字符为ai+1,在结点Ai所射出的诸矢线中,寻找标记为ai+1的矢线(若不存在,则表明w有语法错误),读入ai+1,并进入状态Ai+1; (3)重复(2),直到w中所有字符被读完且恰好进入终态F时,宣告整个识别结束,w可被接受.,29,例:GZ: 状态转换图: Z0U1V U 1Z1 1 V 0Z0 0 1 初态
14、1 0 0 1=011001 2=111001,Z,U,V,F,30,状态转换图识别的语言,显然,若从初态出发,分别沿一切可能的路径到达终态结点,并将路径中矢线上所标记的字符依次连接起来,便得到状态转换图所能识别的全部符号串,这些符号串组成的集合构成了该状态转换图识别的语言。,31,状态转换图与文法推导,用状态转换图识别符号串w的过程，就是为w建立一个推导S* w的过程。 在第一步（在初始状态S下，扫描到a1而过渡到下一状态A1），由状态转换图的构造规则可知，G中必有产生式Sa1A1; 对于识别过程的后续步骤，由状态Ai 识别ai+1后过渡到Ai+1恰好对应了使用产生式Ai ai+1Ai+1
15、。 最后在状态An-1识别an后到达终态F，对应了使用产生式A an。 整个推导过程：S a1A1 a1a2A2 a1a2an-1An-1 a1a2an,32,例:GZ: 状态转换图: Z0U1V U 1Z1 1 V 0Z0 0 1 初态 1 0 0 例: =011001 通过状态图可以确定是文法的句子. 此过程是一种推导过程. Z=0U=01Z=011V=0110Z=01100U=011001,Z,U,V,F,33,右线性文法与状态转换图,设G是一右线性文法,M是相应的状态转换图,则从前面的讨论可以看出如下事实： (1)在利用M对符号串w进行识别时,M中每次状态的转换都模拟了一步直接推导,即识别方法(或称分析方法) 是“”的; (2)因右线性文法只有形如AaB、A a的产生式，所以推导的每一步所得句型只含一个非终结符
