正则表达式的例子 。∑={a,b} ·L(aIb)={a,b} o L((a I b)(a I b))={aa,ab,ba,bb} L(a")={s,a,aa,aaa,aaaa,... L((a I b)")={s,a,b,aa,ab,ba,bb,aaa,aab,... L(a I a'b)=a,b,ab,aab,aaab,... 16
正则表达式的例子 • Σ = { 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, … } 16 南大编译许畅
正则定义(1) 为了书写方便，可以给正则表达式命名，且可以 通过名字使用正则表达式 正则定义是如下形式的定义序列 d1今r1 d2→r2 dn今rn 。 其中 d:不在Σ中，且各不相同 每个Y是字母表∑U{d1vd2,,d1}上的正则表达式； 这保证了不会出现递归定义 18
正则定义 (1) • 为了书写方便，可以给正则表达式命名，且可以 通过名字使用正则表达式 • 正则定义是如下形式的定义序列 d1 → r1 d2 → r2 … dn → rn • 其中 – di不在Σ中，且各不相同 – 每个ri是字母表Σ { d1 , d2 , …, di-1 }上的正则表达式； 这保证了不会出现递归定义 18 南大编译许畅
正则定义的例子 C语言标识符的正则定义 letter >A I B I ..I Z I a I bl...Iz digit→0111..19 id letter (letterI digit 。d对应的正则表达式为 (A I B I ..I Z I a l b l...I z I((A I B I ..IZ I a 1b1..1z1_)1(0111.19)) 20
正则定义的例子 • C语言标识符的正则定义 – letter_ → A | B | … | Z | a | b | … | z | _ – digit → 0 | 1 | … | 9 – id → letter_ ( letter_ | digit ) * • id对应的正则表达式为 – (A | B | … | Z | a | b | … | z | _) ( (A | B | … | Z | a | b | … | z | _) | (0 | 1 | … | 9) )* 20 南大编译许畅
正则表达式的扩展 基本运算符：选择、连接、Kleene闭包 。 扩展的运算符 一个或多个实例：单目后缀 。t等价于rr 零个或一个实例：？ 。r?等价于eIr 字符类 [a1a2an]等价于41|a21..|am -符号，如：[a-e等价于aIb|cldle ·使正则表达式更简洁，但不会使其描述能力增强 21
正则表达式的扩展 • 基本运算符：选择、连接、Kleene闭包 • 扩展的运算符 – 一个或多个实例：单目后缀+ • r +等价于r r * – 零个或一个实例：？ • r?等价于ε | r – 字符类 • [a1 a2…an ]等价于a1 | a2 | … | an • −符号，如：[a−e]等价于a | b | c | d | e • 使正则表达式更简洁，但不会使其描述能力增强 21 南大编译许畅
内容 。词法分析器的作用 词法单元的规约（正则表达式） 词法单元的识别（状态转换图） ·词法分析器生成工具及设计 0 有穷自动机 22
内容 • 词法分析器的作用 • 词法单元的规约 (正则表达式) • 词法单元的识别 (状态转换图) • 词法分析器生成工具及设计 • 有穷自动机 22 南大编译许畅