第3章词法分析与有穷自动机20090316.ppt

2020年1月27日 编译原理 第3章词法分析 本章介绍编译第一个阶段词法分析的设计原理和设计方法 要求明确此阶段的任务 理解通常的单词分类和构词规则 会使用单词的描述和识别机制 要求掌握正规文法 状态图 DFA NFA 正规式和正规集的基本概念和它们之间的关系 掌握词法分析程序的手工实现方法 教学目标 2020年1月27日 编译原理 1词法分析程序的功能2词法分析程序的输出形式3程序设计语言单词的定义4正规式与有穷自动机5正规文法与有穷自动机6词法分析程序的编写方法 教学内容 2020年1月27日 编译原理 1 分析和识别单词及属性 包括识别语言的关键字 标识符 常数 运算符等 2 跳过各种分隔符 如空格 回车 制表符等 3 删除注释 4 进行词法检查 报告所发现的错误 5 建立符号表 3 1词法分析程序的功能 2020年1月27日 编译原理 main ADD intx 10 y 20 sum sum x y 2020年1月27日 编译原理 实现方案 基本上有两种 1 词法分析单独作为一遍 2 词法分析程序作为单独的子程序 S P 字符串 词法分析 S P 符号串 语法分析 第一遍 第二遍 单词串 优点 结构清晰 各遍功能单一缺点 效率低 2020年1月27日 编译原理 单词的种类 1 关键字 if for while 2 标识符 3 常数 4 运算符 5 分界符 3 2词法分析程序的输出形式 2020年1月27日 编译原理 词法分析程序的输出形式 二元式 单词类别单词的属性值 单词类别可以用整数编码表示 一类一种或一字一种 2020年1月27日 编译原理 单词符号属性的值 单词自身符号的机内编码 关键字 运算符 界符 只输出其种别码即可 标识符 自身字符串的值 长度受限制 常数 本身的值 字符型输出字符串本身 数值型 输出其自身的二进制 对于标识符和常数 若要建符号表 则输出其在符号表的入口地址 2020年1月27日 编译原理 表3 1intx 10 y 20 sum 词法分析的结果 表3 1intx 10 y 20 sum 词法分析的结果 2020年1月27日 编译原理 3 3语言单词符号的两种定义方式 文法定义 标识符的定义 标识符是以字母开头的 字母数字的组合 I aB a右线性文法B aB dB a dI a Ia Id左线性文法正规式定义 字母 字母 数字 a a d 2020年1月27日 编译原理 3 5 字母表 定义在 上的正规式和正规集递归定义如下 1 和 都是 上的正规式 它们所表示的正规集分别为 和 2 任何a a是 上的正规式 它所表示的正规集为 a 3 假定e1和e2是 上的正规式 它们所表示的正规集分别记为L e1 和L e2 那么e1 e2 e1 e2和e1 也都是 上的正规式 它们所表示的正规集分别为L e1 L e2 L e1 L e2 和 L e1 4 任何 上的正规式和正规集均由1 2和3产生 3 3 1正规式与正规集 2020年1月27日 编译原理 正规式中的运算符 或 选择 连接 或 重复 括号 运算符的优先级 先 后 最后 在正规式中可以省略 正规式相等 这两个正规式表示的语言相等 2020年1月27日 编译原理 正规式举例 例 设有字母表 a b 根据正规式与正规集的定义 有以下的正规式和正规集正规式正规集a a a b a b ab ab a b a b aa ab ba bb a a aa aaa 任意个a的串 a b a b aa ab ba bb 所有a b组成的串 a b aa bb a b 上所有含两个连续的a或两个连续的b组成的串 2020年1月27日 编译原理 例 d e 则 上的正规式d dd e dd 表示的是实数 其中d为0 9中的数字 比如 2 12 59 3 6e2和471 88e 1等等都是该正规集所表示集合中的元素 例 设 a b c 则aa bb cc 是 上的一个正规式 它所表示的正规集L abc aabc abbc abcc aaabc ambncl m n l 1 2020年1月27日 编译原理 例 设 a b 2020年1月27日 编译原理 例 使用正规式来表示程序设计语言中的相应单词符号 字母 字母 数字 数字 数字 2020年1月27日 编译原理 设r s t均是正规式 则有以下性质 1 交换律 r s s r 2 结合律 r s t r s t rs t r st 3 分配律 r s t rt st 4 同一律 r r r 2020年1月27日 编译原理 3 3 2正规文法与正规式 正规文法 正规式的转换方法 1 将正规文法中的每一个非终结符表示成关于它的一个正规式方程 获得一个联立方程组 2 依照求解规则 若x ax 或x ax 则解为x a 若x xa 或x xa 则解为x a 求关于开始符号S的解 从文法的规则到正规式方程的变换 1 若A a 则有A a 2 若A aB 则有A aB 2020年1月27日 编译原理 举例 例3 4 设有正规文法G Z 0AA 0A 0BB 1A 试给出该文法生成语言的正规式 例3 5 设有正规文法G A aB bBB aC a bC aB试给出该文法生成语言的正规式 2020年1月27日 编译原理 例3 6 设有正规文法G Z U0 V1U Z1 1V Z0 0试给出该文法生成语言的正规式 2020年1月27日 编译原理 正规表达式RE 正规文法G 对任何一个正规表达式e 都存在一个等价的正规文法G 使得L e L G 2020年1月27日 编译原理 字母表 上的正规式到正规文法G VN VT P S 的转换方法如下 1 令VT 2 对任意正规式R选择一个非终结符Z生成规则Z R 并令S Z 3 若a和b都是正规式 对形如A ab的规则转换成A aB和B b两个规则 其中B是新增的非终结符 4 在已转换的文法中 将形如A a b的规则进一步转换成A aA b 5 不断利用规则 3 和 4 进行变换 直到每条规则最多含有一个终结符为止 2020年1月27日 编译原理 例3 8 将R a b aa a b 转换成相应的正规文法 设A是文法的开始符号 根据规则 2 变换为A a b aa a b 根据规则 3 变换为 A a b BB aa a b 根据规则 4 变换为 A aB bBB aaB a b根据规则 3 变换为 A aB bBB aC a bC aB 2020年1月27日 编译原理 例3 9 将描述标识符的正规式R l l d 转换成相应的正规文法 令S为文法的开