第三章词法分析 32则表达式与有穷状自动机 3.21状态转换图与转换系统 应用状态转换图来识别句子 步骤1:从开始状态开始,以它作为当前状态,并从x的最左字 符开始,重复步骤2直到达到x的右端为止 步骤2:扫描x的下一字符(当前字符),在当前状态射出的各个 弧中找出标记有该字符的弧,并沿此弧前进,以所达到的状 态作为下一当前状态。 定理3.1当识别一个字符串x时,如果能从状态转换图的开始 状态出发行进达到x的右端,ⅹ为句子的充分必要条件是最后 的当前状态为终止状态。 例如: ababa和 bababbb
3.2 正则表达式与有穷状态自动机 3.2.1 状态转换图与转换系统 • 应用状态转换图来识别句子 步骤1：从开始状态开始，以它作为当前状态，并从x的最左字 符开始，重复步骤2直到达到x的右端为止。 步骤2：扫描x的下一字符(当前字符)，在当前状态射出的各个 弧中找出标记有该字符的弧，并沿此弧前进，以所达到的状 态作为下一当前状态。 定理3.1 当识别一个字符串x时，如果能从状态转换图的开始 状态出发行进达到x的右端，x为句子的充分必要条件是最后 的当前状态为终止状态。 例如：ababaaa和bababbb 第三章 词法分析
第三章词法分析 a G[Z]: Z:: =Za Aa Bb b[( 7 A∷=Ba b B::=Ab b (a) 步骤当前状态输入的其余部分 a b a b aaa b a b aa a 12345678 SABABAZZ b aaa aaa aaa a b (b)语法树
G[Z]：Z::=Za|Aa|Bb A::=Ba|a B::=Ab|b 步骤 当前状态 输入的其余部分 1 S a b a b a a a 2 A b a b a a a 3 B a b a a a 4 A b a a a 5 B a a a 6 A a a 7 Z a 8 Z 第三章 词法分析
第三章词法分析 3.2正则表达式与有穷状态自动机 3.21状态转换图与转换系统 用状态转换图为正则语言构造正则文法 (1)为正则语言画出状态转换图。基于其句子的一般形式和 状态转换图运行思想。 (2)从该状态转换图构造相应的正则文法。 如果一个状态转换图中有从状态V到状态U的弧,弧上标 记为T,显然必存在规则U∷=ⅥT 如果从开始状态S到状态U有一弧,弧上标记为T时,则 存在规则U=T
3.2 正则表达式与有穷状态自动机 3.2.1 状态转换图与转换系统 • 用状态转换图为正则语言构造正则文法 （1）为正则语言画出状态转换图。基于其句子的一般形式和 状态转换图运行思想。 （2）从该状态转换图构造相应的正则文法。 如果一个状态转换图中有从状态V到状态U的弧，弧上标 记为T，显然必存在规则U∷=VT； 如果从开始状态S到状态U有一弧，弧上标记为T时，则 存在规则U∷=T。 第三章 词法分析
第三章词法分析 例如,对于正则语言{(ab)2|n≥0}, 相应的正则文法 G[Z]:Z:=CbC∷=Bb|bB∴=AbA∴=Ba|a (1)为正则语言画出状态转换图。 (2)从该状态转换图构造相应的正则文法 如果一个状态转换图中有从状态V到状态U的弧,弧上标 记为T,显然必存在规则U∷=ⅥVT; 如果从开始状态S到状态U有一弧,弧上标记为T时,则 存在规则U=T
例如，对于正则语言｛(ab)nb 2｜n≥0｝， 相应的正则文法： G［Z］: Z∷=Cb C∷=Bb｜b B∷=Ab A∷=Ba｜a （1）为正则语言画出状态转换图。 （2）从该状态转换图构造相应的正则文法。 如果一个状态转换图中有从状态V到状态U的弧，弧上标 记为T，显然必存在规则U∷=VT； 如果从开始状态S到状态U有一弧，弧上标记为T时，则 存在规则U∷=T。 第三章 词法分析
第三章词法分析 3.2正则表达式与有穷状态自动机 ·转换系统 定义3.1转换系统是具有下列三个特征的状态转换图,即 1)只有唯一的开始状态S和唯一的终止状态Z; 2)在其中无弧进入S,也无弧自Z射出; 3)可能存在有ε弧,即标记为ε(空串)的弧
3.2 正则表达式与有穷状态自动机 • 转换系统 定义3.1 转换系统是具有下列三个特征的状态转换图，即, 1)只有唯一的开始状态S和唯一的终止状态Z； 2)在其中无弧进入S，也无弧自Z射出； 3)可能存在有ε弧，即标记为ε(空串)的弧。 第三章 词法分析