sun编译原理第3章词法分析与有穷自动机(第5-8讲).ppt

2020 2 22 信息学院孙丽云 1 3 1词法分析程序的功能 所谓词法 即构成词的规则 词法分析的任务是对字符串表示的源程序从左到右进行扫描和分解 根据语言的词法规则识别出一个一个具有独立意义的单词符号 词法分析是编译过程中的一个阶段 在语法分析前进行 可以作为单独的一遍 将源程序转换成单词符号序列供下一遍使用 也可以和语法分析结合在一起作为一遍 由语法分析程序调用词法分析程序获得当前记号 供语法分析使用 2020 2 22 信息学院孙丽云 2 3 2单词符号及输出单词的形式 单词符号是语言中具有独立意义的最小单位 包括保留字 标识符 常量 运算符和界符等 词法分析程序输出的单词符号通常表示成如下的二元式 单词种别 单词自身的值 2020 2 22 信息学院孙丽云 3 正规式与正规集 3 3语言单词符号的两种定义方式 多数程序设计语言的单词符号都能用正规文法或正规式来定义 设有字母表 a1 a2 an 在字母表上的正规式和它所表示的正规集可用如下规则定义 1 是 上的正规式 它所表示的正规集是 即空集 2 是 上的正规式 它所表示的正规集是 3 ai是 上的正规式 它所表示的正规集由单个符号ai组成 即 ai 2020 2 22 信息学院孙丽云 4 正规式与正规集 4 如果e1和e2都是 上的正规式 它们所表示的正规集分别为L e1 和L e2 则e1 e2是 上的一个正规式 它所表示的正规集为L e1 e2 L e1 L e2 e1e2是 上的一个正规式 它所表示的正规集为L e1e2 L e1 L e2 e1 是 上的一个正规式 它所表示的正规集为L e1 L e1 正规式描述了单词符号的构成规则 正规集是正规式能描述的所有的单词的集合 2020 2 22 信息学院孙丽云 5 设有字母表 a b 根据正规式和正规集的定义有 例3 1 1 a和b是正规式 相应正规集为L a a 2 a b是正规式 相应正规集为L a b a b 3 ab是正规式 相应正规集为L ab ab 4 a b 是正规式 相应正规集为L a b a b a b ab ba 5 ba 是正规式 相应正规集为L ba b ba baa baaa 6 a b aa bb a b 是正规式 相应正规集为L a b aa bb a b 练习 若S a bb 则L a bb 2020 2 22 信息学院孙丽云 6 正规式中运算的优先级 括号优先 次之 连接 再次之 最后例 a bc a b c ab c d ab c d L a bc L a L bc L a L b L c L a L b L c a b c cc ccc a b bc bcc bccc 正规式与正规集举例 思考 L ab c d 2020 2 22 信息学院孙丽云 7 设A B C均为正规式 则正规式有如下性质 A B B A 交换律 A B C A B C 结合律 A BC AB C 结合律 A B C AB AC 分配律 A B C AC BC 分配律 A A AA AA A A A A A 正规式的性质 2020 2 22 信息学院孙丽云 8 正规文法与正规式 正规文法与正规式都是描述正规集的工具 对任意一个正规文法 存在定义同一语言的正规式 反之 对每个正规式存在一个生成同一语言的正规文法 3型 正规文法 左线性 P U t或U Wt其中U W Nt T 右线性 P U t或U tW其中U W Nt T 2020 2 22 信息学院孙丽云 9 正规文法到正规式的转换 1 将正规文法中的每个非终结符表示成关于它的一个正规式方程 获得一个联立方程组 2 依照求解规则 若x x 或x x 则解为x 若x x 或x x 则解为x 以及正规式的分配律 交换律和结合律求关于文法开始符号的正规式方程组的解 这个解是关于该文法开始符号S的一个正规式 显然它表示了由该正规文法所描述的语言 2020 2 22 信息学院孙丽云 10 正规文法到正规式的转换举例 例3 4设有正规文法G Z 0AA 0A 0BB 1A 试给出该文法生成语言的正规式 解 1 联立方程组 用 代替正规式中的 2 依照求解规则求解 2020 2 22 信息学院孙丽云 11 正规文法到正规式的转换举例 例3 5设有正规文法G A aB bBB aC a bC aB试给出该文法生成语言的正规式 解 1 联立方程组 用 代替正规式中的 2 依照求解规则求解 练习 2020 2 22 信息学院孙丽云 12 正规文法到正规式的转换举例 例3 6设有正规文法G Z U0 V1U Z1 1V Z0 0试给出该文法生成语言的正规式 解 1 联立方程组 用 代替正规式中的 2 依照求解规则求解 P28 9 2020 2 22 信息学院孙丽云 13 正规式到正规文法的转换 字母表 上的正规式到正规文法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 2 22 信息学院孙丽云 14 正规式到正规文法的转换举例 例3 8将R a b aa a b 转换成相应的正规文法 例3 9将R l l d 转换成相应的正规文法 练习 2020 2 22 信息学院孙丽云 15 3 4正规式与有穷自动机 有穷自动机是词法的识别工具 它的功能是 寻找 匹配 符合正规式要求的字符串 根据正规式确定正规集 有穷自动机是描述特定类型算法的数学模型 可分为确定性有穷自动机 DFA 和非确定性有穷自动机 NFA 2020 2 22 信息学院孙丽云 16 确定有穷自动机 DFA 数学定义 五元组形式 严密 状态转换表 面向编程 状态转移图 直观 DFA有三种表示形式 2020 2 22 信息学院孙丽云 17 结点代表状态 state 用圆圈 表示 状态之间用箭头 transition 连结 代表一个状态向另一个状态的转换 一个有穷自动机只包含有限个状态 即有限个结点 其中只有一个为初态 startstate 一个有开始状态的箭头指向 至少一个为终态 接受状态acceptingstate 双圈表示 例 标识符的有穷自动机 有穷自动机的状态转移图表示方法 2020 2 22 信息学院孙丽云 18 状态状态转移初始状态接受状态 两字符串的识别过程 有穷自动机的状态转移图表示方法 2020 2 22 信息学院孙丽云 19 确定有穷自动机 DFA 输入字母表 Q有穷状态集 f Q Q 状态转换函数 S Q唯一的初始状态 Z Q终止 接受 状态集合这里的字母表是问题固有的 状态集合是编写DFA时定义的 是用户所做的命名 DFAM是一个五元组 Q f S Z 确定性有穷自动机 DFA 下一状态由当前状态和当前输入字符唯一给出的自动机 取决于f 确定 即状态转移函数是单值函数 数学定义 确定有穷自动机 DFA 例 M Q f S Z 其中 a b z A B Z 0 1 9 Q 1 2 3 S 1 Z 2 f f Q Q是如下的函数 f 1 a 2 f 1 z 2f 1 A 2 f 1 Z 2f 2 a 2 f 2 z 2f 2 A 2 f 2 Z 2 f 2 0 2 f 2 9 2f 1 0 3 f 1 9 3f 3 a 3 f 3 z 3f 3 A 3 f 3 Z 3 2020 2 22 信息学院孙丽云 21 例 有DFAM 0 1 2 3 a b f 0 3 其中f为 f 0 a 1f 0 b 2f 1 a 3f 1 b 2f 2 a 1f 2 b 3f 3 a 3f 3 b 3 它所对应的状态表如图 一个DFA可用一个矩阵表示 该矩阵的行表示状态 列表示输入字符 矩阵元素表示T s a 的值 这个矩阵称状态表 状态转移矩阵 状态 输入字符 后继状态 状态表 2020 2 22 信息学院孙丽云 22 DFA三种表示形式的转化 2020 2 22 信息学院孙丽云 23 DFA所识别的语言 给定DFAM 对于字符c1 c2 cn 当以下条件成立时 称M接受由c1 c2 cn组成的字符串c1c2 cn 存在状态序列s0 s1 s2 sn 使得s1 f S c1 s2 f s1 c2 sn f sn 1 cn 且sn Z 例 判断abbbba是否是上页DFAM所定义的语言 由DFAM接受的语言L M 是所有M接受的字符串组成的集合 2020 2 22 信息学院孙丽云 24 非确定有穷自动机 NFA 由M接受的语言L M L M c1c2c3 cn ci U s1 T s0 c1 s2 T s1 c2 sn T sn 1 cn sn A 非确定 即状态转移函数是多值函数 输入字母表 Q 有穷状态集 f Sx U S 状态转换函数 S Q初始状态集 Z Q终止状态集 NFAM也是一个五元组 Q f S Z 2020 2 22 信息学院孙丽云 25 NFA与DFA的区别 2020 2 22 信息学院孙丽云 26 判断下图是DFA还是NFA的状态转换图 并写出其他2种表示形式 2020 2 22 信息学院孙丽云 27 由正规表达式R构造NFA a 对于正规式 所构造NFA x y b 对于正规式 所构造NFA x y c 对于正规式a a 则NFA x y a 1 基本正规表达式 2020 2 22 信息学院孙丽云 28 由正规表达式R构造NFA 2 若r s为正规式 rs r s r 例 构造与正规表达式R ab a a b 等价的NFA 2020 2 22 信息学院孙丽云 29 为R a b aa bb a b 构造NFA 使得L N L R 课堂练习 课后作业 P553 1 1 2 2020 2 22 信息学院孙丽云 30 NFA确定化为DFA的方法 非确定的有穷自动机与确定的有穷自动机从功能上来说是等价的 NFAM DFAM 构造成一个 使得L M L M 2020 2 22 信息学院孙丽云 31 定义1 状态集合I的 闭包 令I是一个状态集的子集 定义 closure I 为 1 若s I 则s closure I 2 若s I 则从s出发经过任意条 弧能够到达的任何状态都属于 closure I 状态集 closure I 称为I的 闭包 为了使得NFA确定化 给出两个定义 例 如图所示的状态图 令I 1 求 closure I 解 根据定义 closure I 1 3 例 若I1 1 2 则 closure I1 1 2 3 6 2020 2 22 信息学院孙丽云 32 J是从状态子集I中的每个状态出发 经过标记为a的弧而达到的状态集合 Ia是状态子集 其元素为J中的状态 加上从J中每一个状态出发通过 弧到达的状态 定义2 状态子集的构造 s I 例 令I 1 求Ia Ia closure J closure T 1 a closure 2 4 2 4 6 令I是NFAM 的状态集的一个子集 a 定义 Ia closure J 其中J T s a 2020 2 22 信息学院孙丽云 33 例 有NFAM 求DFAM IIaIbIc 初态 I closure 1 1 4 Ia closure T 1 a T 4 a closure 2 3 closure 2 3 2 3 Ib closure T 1 b T 4 b closure Ic closure T 1 c T 4 c I 2 3 Ia 2 Ib 4 Ic 3 4 DFA的状态 P42 2020 2 22 信息学院孙丽云 34 DFAM 状态表 将求得的状态转换矩阵重新编号 包含NFA终态的状态子集全都是DFA的终态 2020 2 22 信息学院孙丽云 35 DFA的化简 自动机理论中的结论 对于任一个DFAM 存在一个唯一的状态最少的等价的DFAM 即 一个有穷自动机可以通过消除多余状态和合并等价状态而转换成一个最小的与之等价的有穷自动机 等价状态状态s和t的等价条件是 1 状态s和t必须同时为可接受状态或非接受状态 2 对于所有输入符号 状态s和t必须转换到等价的状态里 确定等价状态通常采用逆向思维 不直接寻找相互等价的状态 而是先确定互不等价的状态 即 可区别的状态 当所有的互不等价的状态都被确定之后 那些不符合不等价条件的状态就是相互等价的状态了 2020 2 22 信息学院孙丽云 36 例 将该DFA最小化 2 4 3 1 srart a a a a a a a b b b b b b b 状态集的划分将所有DFA的终态与其它状态划分成两个子集G1 G2 分别从两个子集G1 G2中寻找不等价状态进行分割 分割法 把一个DFA 不含多余状态 的状态分割成一些不相关的子集 使得任何不同的两个子集状态都是可区别的 而同一个子集中的任何状态都是等价的 2020 2 22 信息学院孙丽云 37 解 一 区分终态与非终态 a b 2 4 3 1 srart a a a a a a a b b b b b b b 2020 2 22 信息学院孙丽云 38 区号 区号 2020 2 22 信息学院孙丽云 39 例 试求与下图所示NFA等价的化简了的DFA 0 0 3 1 1 2 4 0 1 1 0 1 0 1 0 1 化简后的DFA 2020 2 22 信息学院孙丽云 40 有一台自动售货机 接受1分和2分硬币 出售3分一块儿的硬糖 顾客每次向机器中投放 3分的硬币 便可得到一块糖 注意 只给一块并且不找钱 请为自动售货机编制程序使其能够正确售出货物 1 写出售货机售糖的正规表达式 2 构造识别上述正规式的最简DFA 3 将该DFA用代码实现 设顾客投入1分硬币用a表示 2分硬币用b表示 则售货机售糖的正规表达式为 a a a b b b a b DFA与代码 略 简单应用举例 2020 2 22 信息学院孙丽云 41 例 设计一个DFA 其输入字母表是 0 1 它能接受以0开始 以1结尾的所有序列 解 1 根据题意 得出相应的正规式 0 0 1 1 2 得状态转换图 NFA 3 NFA转换DFA 4 DFA最小化 正规式到DFA 例 构造与正规式R a b b ba 等价的状态最少的DFA 正规式到DFA 课堂练习 比较正规式向DFA转换过程中 弧多少的差异 2020 2 22 信息学院孙丽云 42 练习 M如右 求相应的正规式 有穷自动机到正规式的转换 P46转换规则 1 添加结点 保证只有一个初态结点和一个终态结点 2 逐步消去中间结点 例 P47图3 19 2020 2 22 信息学院孙丽云 43 消除M中的所有结点 解 加x y 新的初态和终态 2020 2 22 信息学院孙丽云 44 课后思考题 有穷自动机到正规式的转换 2020 2 22 信息学院孙丽云 45 正规文法 NFA 正规式 1 2 3 4 5 6 DFA 最小化 正规文法 正规式是描述正规集的工具 有穷自动机是识别正规集的工具 它们可相互转化 2020 2 22 信息学院孙丽云 46 例 有文法G s S aA aA aA dA a d求相应的正规式 复习 S a a d a d 规则 若x x 或x x 则解为x 若x x 或x x 则解为x 正规文法 正规式 2020 2 22 信息学院孙丽云 47 转换规则 1 A ab转换成A aB和B b两规则 其中B是新增的非终结符 2 A a b转换成A aA b 例 将R a a d 转换成相应的正规文法 解 1 S a a d 2 S aAA a d S aAA a d A S aAA aA dA 正规式 正规文法 复习 2020 2 22 信息学院孙丽云 48 3 5正规文法与有穷自动机 有穷自动机 正规文法 1 对转换函数T A t B可写成一个产生式 A tB2 对可接受状态Z 增加一个产生式 Z 3 有穷自动机的初态对应于文法的开始符号 有穷自动机的字母表为文法的终结符号集 例 G a b A B C D P A 其中P A aBA bDB bCC aAC bDC D aBD bDD 右线性正规文法 有穷自动机 例 求与文法G E 等价的NFAG E E aA bB A aB bAB aE bA 解 1 字母