编译原理3.3.1-正规式.ppt

第三章词法分析 3 1对于词法分析器的要求3 2词法分析器的设计3 3正规表达式和自动机3 4词法分析器的自动产生 3 3正规表达式和自动机 3 3 1正规式和正规集3 3 2确定有限自动机3 3 3非确定有限自动机3 3 4正规文法与有限自动机的等价性3 3 5正规式与有限自动机的等价性3 3 6确定有限自动机的化简 正规语言 确定化 最小化 正规式 正规文法 自动机 3 3 1正规式和正规集 1 正规式的引入2 正规式和正规集的定义3 两个正规式等价的定义4 正规式服从的代数规律 1 正规式的引入 正则表达式 正规表达式 RERegularExpression 正规语言是VT 上的正规集 L G VT 单词描述工具 2 正规式和正规集的定义 设字母表为 辅助字母表 1 2 语言的字母表VT 3 假定U和V都是 上的正规式 他们所表示的正规集分别为L U 和L V 4 仅由有限次使用上述三步骤而定义的表达式才是 上的正规式 仅由这些正规式表示的字集才是 上的正规集 规定算符的优先顺序 正规式aa bab a b a b a a b 正规集 a a b ab aa ab ba bb a aa aaa a b aa ab 所有由a和b组成的串 补充例 令 a b 上的正规式和相应的正规集 例3 1 a b P47 ba b a 上所有以b为首 后面跟任意多个a的符号串a a b a a b 上所有以a为首的符号串 a b aa bb a b a b aa bb a b 上所有含有两个相继a或两个相继b的符号串 例3 2 A B 0 1 P47 A B A B 0 1 A B A B 0 1 上 标识符 的全体 0 1 0 1 0 1 0 1 上 数 的全体 补充例 0 9 a z A Z 正规式d 0 1 9正规式l a z A Z整数的集合 dd dd d 标识符的集合 l l d 3 两个正规式等价的定义 若两个正规式U和V表示的正规集相同 则说U和V等价 写作U V 例 a b b ab ab ba b a b a b 4 正规式服从的代数规律 U V W为正规式 U V V U U V W U V W UV W U VW U V W UV UW V W U VU WU U U U P47 补充 正规式服从的代数规律 r r rr r rr r r 0 1 2 n 补充例 定义无符号数的正规式 d e d为0 9的数字 表示小数点d dd e dd 2 12 59 3 6e2 471 88e 1