PPT《第三章 词法分析》

连接:(r)(s),L((r)(s))=L(r)L(s) ;

闭包:(r)*,L((r)*)=(L(r))*;

括号:(r),L((r))=L(r)运算的优先级:连接 >

|正则集合:可以用一个正则表达式定义的语言 正则表达式的例子 Σ={a,b}L(a|b) = {a,b}L((a|b)(a|b)) = {aa,ab,ba,bb}L(a*) = {ε,a,aa,aaa,aaaa,……}L((a|b)*) = {ε,a,b,aa,ab,ba,bb, aaa,aab,……}L(a|a*b) = {a,b,ab,aab,aaab,…} 正则集合、等价 如果L(r)=L(s),正则表达式r和s等价. 正则定义(1) 为了书写方便,可以给正则表达式命名,且可以通过名字使用正则表达式正则定义是如下形式的定义序列d1 ? r1d2 ? r2… …dn?rn其中:di不在Σ中,且各不相同每个ri是字母表Σ U {d1,d2,…,di-1}上的正则表达式.这保证了不会出现递归定义. 正则定义(2) 各个di的Σ上的正则表达式如下:d1的正则表达式即r1.将r2中的d1替换为r1,得到d2的正则表达式.… … … …将ri中的d1,d2,…,di-1替换为各自的正则表达式,得到di的正则表达式.注意:替换的时候不能破坏替换进去的di的完整性. 正则定义的例子 C语言标识符的正则定义letter_ ? A | B | … | Z | a | b | … | z | _digit ?

0 |

1 | … | 9id ? letter_ ( letter_ | digit )*id对应的正则表达式为(A | B | … | Z | a | b | … | z | _) ((A | B | … | Z | a | b | … | z | _) |(0 |

1 | … | 9))* 正则表达式的扩展 基本运算符:并、连接、Kleen闭包扩展的运算符:一个或多个实例:单目后缀+r+等价于rr*零个或一个实例:?r?等价于ε |r字符类[a1a2…an]等价于a1|a2|…|an[a-e]等价于a|b|c|d|e使正则表达式更加简洁,但不会使正则表达式的描述能力增强 内容 词法分析器的作用词法单元的规约词法单元的识别词法分析器生成工具Lex有穷自动机从正则表达式到自动机词法分析器生成工具的设计方法 词法单元的识别 词法分析器要求能够检查输入字符串,在前缀中找出和某个模式匹配的词素.首先通过正则定义来描述各种词法单元的模式.定义ws?(blank | tab | newline)+来消除空白词法分析器识别到这个模式时,不返回词法单元,继续识别其它模式. 状态转换图 词法分析器的重要组件之一状态转换图(transition diagram)状态(state):表示在识别词素时可能出现的情况状态看作是已处理部分的总结.某些状态为接受状态或最终状态,表明已找到词素.加上*的接受状态表示最后读入的符号不在词素中.开始状态(初始状态):用start边表示.边(edge):从一个状态指向另一个状态;

边的标号是一个或多个符号.当前符号为s,下一个输入符号为a,就沿着从s离开,标号为a的边到达下一个状态. 状态转换图的例子 保留字和标识符的识别 在很多时候,保留字也符合标识符的模式,识别标识符的状态转换图也会识别保留字.解决方法在符号表中预先填写保留字,并指明它们不是普通标识符.为关键字/保留字建立独立的、高优先级的状态转换图. 其它的状态转换图 词法分析器的体系结构 从转换图构造词法分析器的方法变量state记录当前状态一个switch根据state的值转到相应的代码每个状态对应于一段代码.这段代码根据读入的符号,确定下一个状态如果找不到相应的边,则调用fail()进行错误恢复进入某个接受状态时,返回相应的词法单元.注意状态有*标记时,需要回退forward指针.实际是模拟转换图的运行 Relop对应的代码概要 处理多个模式的方法 词法分析器需要匹配多个模式解决方法按照优先级,顺序地尝试各个状态转换图.如果引发fail(),回退并尝试下一个状态图.更好的方法: 并行地 运行各个状态转换图.通过greedy策略,识别最长的和某个模式匹配的输入前缀实际使用的方法:预先把各个状态转换图合成一个状态转换图,然后运行这个状态转换图. 内容 词法分析器的作用词法单元的规约词法单元的识别词法分析器生成工具Lex有穷自动机从正则表达式到自动机词法分析器生成工具的设计方法 词法分析工具Lex/Flex Lex/Flex是一个有用的词法分析器生成工具通常和Yacc一起使用,生成编译器的前端 Lex源程序的结构 声明部分包含:明示常量:表示常数的标识符正则定义转换规则模式 {动作}模式是正则表达式动作表示识别到相应模式时采取的处理方式.辅助函数各个动作中使用的函数 声明部分%%转换规则%%辅助函数Lex程序........