哈工大编译原理词法分析.ppt

词法分析 第三章 词法分析 词法分析器(Scanner)的功能 正规表达式 状态转换图 词法分析器的设计与实现 有穷自动机FA 3.1 词法分析（扫描）器的功能 功能：输入源程序，输出单词符号(token)。即：把构成源程序的字符串转换成单词符号的序列 单词符号的形式 按照最小的语义单位设计 通常表示为二元组： （单词种别，属性值 ） 关键——找出符号的分割符 1) 单词符号的表示 常用单词种别—分类（肖军模P53，杜P46） 各关键字（保留字、基本字），各种运算符，各种分界符——各用一个种别码标识 其它标识符——用一个种别码标识 整、实、字符常数——各用一个种别码标识 属性（值）——单词的值 常数的值，标识符的名字等 保留字、运算符、分界符的属性值可以省略 例 3-1: 单词符号序列while(*pointer!=\0){pointer++;} while (WHILE， _ ) ( (SLP， _ ) * (FETCH， _ ) pointer (IDN， 符号表入口指针) != (RELOP， NE ) \0 (CONST， 0 ) ) (SRP， _ ) { (LP， _ ) pointer (IDN， 符号表入口指针) ++ (INC， _ ) ; (SEMI， _ ) } (RP， _ ) 2）相关问题 超前扫描 双字符运算符（**, /*,:=,…） DO 90 k=1,10 DO 90 k=1.10 预处理问题 剔除源程序中的无用符号、空格、换行、注释等 扫描器的运行方式 作为独立的遍：简单，但需增加额外的开销 作为独立的子程序：节省内存 扫描器作为独立的子程序 2）相关问题 符号表的存储 线性表 哈希表 发现词法错误 行、列计数 发现并定位词法错误 一种符号表的数据结构 2）相关问题 输入缓冲区 2）相关问题 双缓冲区问题__超前扫描导致的效率问题 3.2 记号的描述__正规(表达)式 例：标识符的文法描述 约定：用digit表示数字：0,1,2,…,9; 用letter表示字母：A,B,…,Z,a,b,…,z G =({digit,letter}, {S}, P, S) S→letter L→letter|letter T S→S digit T→Letter T|letter S→S letter T→digit T|digit 左线性 右线性 表示集合：{letter}{letter,digit}* 1) 正规式：正规语言的另一种描述方法 例3-2：标识符的另一种表示 letter(letter|digit)* | 表示或 * 表示Kleene闭包 Letter和(letter|digit)*的并列表示两者的连接 正规式 r 表示正规集,相应的正规集记为 L(r) 正规(表达)式(Regular Expression——RE) 设∑是一个字母表， ⑴ Φ是∑上的RE，L(Φ)=Φ； ⑵ ε是∑上的RE，L(ε)={ε}； ⑶ 对于?a∈∑，a是RE，L(a)={a}； ⑷如果r和s是RE，L(r)=R,L(s)=S，则： r与s的“和” (r|s)是RE，L(r|s)=R∪S； r与s的“乘积” (rs)是RE，L(rs)=RS； r的克林闭包(r*)是RE，L(r*)=R*。 ⑸ 只有满足⑴、⑵、⑶、⑷的才是RE。 运算的优先级 运算优先级和结合性: *高于“连接” 和| ， “连接” 高于 | |具有交换律、结合律 “连接” 具有结合律、和对|的分配律 ( )指定优先关系 意义清楚时，括号可以省略 例：L(a(a|b)*(ε|((.|_)(a|b)(a|b)*))) {a}{a,b}*({ε}∪{.,_}{a,b}{a,b}* ) 2) 正规文法与正规式 正规文法与正规式等价 对任何正规文法，存在定义同一语言的正规式 对任何正规式，存在生成同一语言的正规文法 例 3-3 标识符定义的转换 引入 S S→letter (letter|digit)* 引入A消除闭包 S→letter A A→(letter|digit)A|ε 执行连接对|的分配律 S→letter A A→letter A|digit A|ε 例3-4正规式到正规文法的转换 a(a|b)*(ε|((.|_)(a|b)(a|b)*)) = a(a|b)* |a(a|b)*.(a(a|b)*|b(a|b)*) |a