符号串集合.PPTVIP

词法分析 符号和符号串 正规式和正规集 状态转换图 有限自动机 正规式与有限自动机 词法分析器的设计 例: 对下图所示的NFA M求正规式R，使L(R)=L(M)。 (1)对NFA M的状态转换图加上x和y两个结点，形成下图所示的NFA M’ 消去结点1和3后NFA M’如图所示 消去结点2和4后NFA M’如图所示 正规式R转化为NFA M ：在这个方法中按正规式的语法结构指引构造过程，将正规式分解为一系列子表达式，然后将子表达式对应的NFA依次连接而成，构造规则如下： 1. (a)对正规式ф，对应的NFA为： (b)对正规式ε，对应的NFA为： (c)对正规式a，对应的NFA为： 2.正规式R，首先表示成拓广状态转换图： 例如： 设有正规式R=(a|b) *abb，试构造NFA N，使得L(N)=L(R) 六、词法分析 1词法分析器的设计 词法分析的主要工作: 从源程序的第一个字符开始，从左到右扫描源程序，一次读一个字符，根据词法规则将有关字符组合成单词，并识别各类单词，当确定单词类别后，将单词输出。 在词法分析过程中还要完成其它任务，如： 过滤掉源程序中的注释和空白； 记录读入字符的行号，以便发现错误后能报告出错位置； 进行预编译工作(对宏进行展开等工作)； 符号表操作。 错误处理等。 单词的输出： (1)单词的种类： 保留字：如，program begin end var const for …… 标识符：如，程序名、变量名、常量名、类型名、过程名等 常数：如，125、0.745、15.2E+5 算符 ：如，+、– 、*、/、等 界符：如，分号、逗号等 (2)词法分析器的输出形式： 为了便于编译程序进一步加工，单词的输出形式一般采用二元式： 单词类别 单词值 用整数编码表示，如何分类以处理方便为原则，如： 标识符归为一类； 常数按类型分类； 保留字一字一类，或将全体定位一类； 界符可单独作为一类，或一符一类。 采用什么样的输出形式也是取决于后续处理的方便，如： 标识符用字符串编码或对应地址； 常数用其自身值的二进制形式； 保留字(分界符)若将全体定位一类则需输出其值，可用内部整数编码或串编码表示。 例如：程序段 if i=5 then x ：= y；在经过词法分析器扫描后，输出的单词可表示如下： 保留字if (3，‘if’) 标识符i (1，指向i的符号表入口) 等号= (4，‘=’) 常数5 (2，‘5’的二进制表示) 保留字then (3，‘then’) 标识符x (1，指向x的符号表入口) 赋值号:= (4，‘：= ’) 标识符y (1，指向y的符号表入口) 分号； (5，‘；’) 其中，类别码：“1”表示标识符；“2”表示常数； “3”表示保留字；“4”表示算符；“5”表示界符。 2 词法分析器产生 由状态图生成扫描器 : 通过状态转换图构造词法分析程序 设有以下正规式表示的关于某语言的单词的文法： 标识符: 字母(字母|数字)* 无符号整数: 数字(数字)* 单分隔符号: +|-|*|/|（|）|： 双分隔符号: 斜竖*|冒号= 斜竖: / 冒号: ： 对于用正规式表示单词，我们可以得到与之对应的状态转换图，即能够识别单词的有限自动机，以上文法对应的状态转换图如下： 为了设计出一个能够识别各类单词的扫描器，可把上述各状态转换图合并为一个状态转换图 ： 一个共同的入口 一个共同的出口 加上出错状态等处理 从开始状态出发，对于不同的输入字符，所经过的路径不同，但只要能够到达终态，所经过的弧上的标记组成的串，都是该语言的单词。 状态转换图可以理解为词法分析程序的一张原理性框图。只要在此基础上，加上语义处理等方面的工作，就可以形成扫描器的算法框图: Class存放类别码，用Token表示单词值 “读字符”子程序将下一个字符读到工作单元Char中 P=1时为真读P=0时为假读 “组合标识符”子程序，把该标识符组合完毕，并将单词值送Token “查保留字表”子程序通过查预先准备好的