2hhh第及4章 词法分析.pptxVIP

第2章 词法分析;字符串形式字符的源程序;(2) 把词法分析程序作为语法分析程序调用的子程序。 进行语法分析时, 每当需要一个单 词时便调用词法分析程序。;词法分析器设计方法 一个简单的词法分析器示例 正规表达式与FA简介 正规表达式到FA的构造 词法分析器的自动生成;2.1 词法分析器的设计方法;保留字: 如if, else, while, do 标识符: 用于标记常量、变量、数组、函数、类型等的名字 常数: 如实型0.628, 布尔型True 运算符: 如+, -, *, /, , 界符: 分界符号, 如, ; ( ) 注意: 一个程序语言的保留字、运算符和界符的个数是确定的, 而标识符和常数的个数不确定。;2. 单词符号的输出形式 单词符号通常表示为二元式: (单词种别, 单词自身的值) (1) 单词种别 单词种别表示单词的种类。一个语言的单词符号如何分类、分为几类取决于处理上的方便。 通常, 每种单词对应一个整数码。;保留字: 可全体视为一种, 也可一字一种; 标识符: 统归为一种; 常 数: 统归为一种, 或按整型、实型、布尔型等分为几种; 运算符和界符: 统归为一种, 或一符一种;(2) 单词自身的值 若一个种别只含一个单词, 则其种别编码代表自身的值。 若一个种别含多个单词, 则除种别编码外, 还需给出单词自身的值, 从而把同一种类的不同单词区分开。;说明: 标识符自身的值为标识符自身的字符串, 而常数自身的值为常数本身的二进制数值; 可以用指向某表格中一个特定项目的指针区分同一种类中的不同单词。例如, 标识符可用它在符号表中的入口指针作为自身的值; 常数可用它在常数表中的入口指针作为自身的值。;在词法分析中, 可以用状态转换图来识别单词。在状态转换图中, 结点代表状态, 结点之间用有向边连接, 有向边上可标记字符。;说明: 状态转换图中的状态数目是有限的,其中必有一个初态和若干个终态。每个 终态对应一类单词, 终态用双圈表示, 以区别于其它状态。;识别无符号整数的状态转换图如下:;*;在状态转换图中, 到达终态意味着识别出一个单词符号, 因此, 终态时输出相应单词的种类编码。 若到达终态时多读入了一个符号,则识别出该单词后再把多读入的那个符号退回。此类情况在终态上以 *作为标识。;对于一个不含回路的分支状态, 可;状态i对应的switch语句如下:;对于一个含回路的状态, 可用一个 while语句来实现。考虑下述状态转换图, 其对应的while语句如下:;状态i对应的while语句:;2.2 一个简单的词法分析器示例 大多数程序语言的单词符号都可用状态转换图予以识别。下面利用状态转换图构造一个C语言子集的简单词法分析器。;2.2.1 C语言子集的单词符号表示 假定一个C语言子集的所有单词 符号为: while, if, else, switch, case, 标识符, 常数, +, -, *, , =, =, ==, ;。 其种别编码和内码值如下表所示:;表2.1 一个C语言子集的单词符号及其种别编码和内码值;单词符号;2.2.2 C语言子集对应的状态转换图 首先, 对输入串做预处理, 即剔除多余的空格、注释等。 其次, 把保留字作为一类特殊标识符处理, 即当状态转换图识别出一个标识符时, 查保留字表以确定它是否为一个保留字。 C语言子集对应的状态转换图如下:;返回(op,*) 返回(rop, LE);说明: 状态2识别出一个单词符号后, 需先查保留字表。若匹配, 则为保留字, 否则为标识符。若为标识符, 还需查符号表。若符号表中没有该标识符, 则先登录到符号表中, 再返回它在符号表中入口地址作为内码值; 若符号表中有该标识符, 则直接返回其入口地址作为内码值。 状态4识别出一个常数后, 需先把它转换成二进制常数, 再登录到常数表, 然后返回它在常数表中入口指针作为内码值。;2.2.3 状态转换图的实现 状态转换图易于用程序实现, 最简单的办法是让每个状态对应一小段程序。对于C语言子集对应的状态转换图, 首先引进一组变量和过程: character: 字符变量, 存放一个必威体育精装版读入的源程序字符。 token: 字符数组, 存放构成单词符号的字符串。;getbe( ): 若character中字符为空,则调用getchar( ), 直至character为非空字符。 concatenation( ): 把token中字符串与character中字符连接作为token 中的新字符串。 letter( )和digit( ): 判断character中字符是否为字母/数字, 若是返回 true, 否则返回false。;reserve( ): 按token数组中字符串查保留字表, 若是保留字则返回 其编码, 否则返回0