第三章词法分析 3.2正则表达式与有穷状态自动机 321状态转换图与转换系统 3.22确定有穷状态自动机DFA 3.23非确定有穷状态自动机NFA 3.24确定有穷状态自动机的化简 3.2.5正则表达式
3.2 正则表达式与有穷状态自动机 3.2.1 状态转换图与转换系统 3.2.2 确定有穷状态自动机DFA 3.2.3 非确定有穷状态自动机NFA 3.2.4 确定有穷状态自动机的化简 3.2.5 正则表达式 第三章 词法分析
第三章词法分析 3.2正则表达式与有穷状态自动机 3.2.1状态转换图与转换系统 状态转换图的定义 ·状态转换图的构造 应用状态转换图来识别句子 用状态转换图为正则语言构造正则文法 ·转换系统
3.2 正则表达式与有穷状态自动机 3.2.1 状态转换图与转换系统 • 状态转换图的定义 • 状态转换图的构造 • 应用状态转换图来识别句子 • 用状态转换图为正则语言构造正则文法 • 转换系统 第三章 词法分析
第三章词法分析 3.2正则表达式与有穷状态自动机 字母或数字 3.2.1状态转换图与转换系统 状态转换图的定义 E) 字母 其他 状态转换图:为了识别正则文法的句子而专门设计的有向图 1.有穷多个状态(结点):每个状态结点都代表文法的非终结符号; 2.弧:弧上的标记指明在射出弧的结点状态下可能出现的输入字符或字符 类
3.2 正则表达式与有穷状态自动机 3.2.1 状态转换图与转换系统 • 状态转换图的定义 状态转换图: 为了识别正则文法的句子而专门设计的有向图 1.有穷多个状态(结点):每个状态结点都代表文法的非终结符号； 2.弧:弧上的标记指明在射出弧的结点状态下可能出现的输入字符或字符 类。 第三章 词法分析
第三章词法分析 3.2正则表达式与有穷状态自动机 3.21状态转换图与转换系统 状态转换图的构造 步骤1:以S为开始状态作结点; 步骤2:以每一个非终结符号为状态作结点 步骤3:对于形如Q∷=的每个规则,引一条从开始状态S到状 态Q的弧,其标记为T;而对形如Q∷=RT的规则引一条从状态 R到Q的弧,其标记为T。其中R为非终结符号,T为终结符号; 步骤4:识别符号为终止状态
3.2 正则表达式与有穷状态自动机 3.2.1 状态转换图与转换系统 • 状态转换图的构造 步骤1：以S为开始状态作结点； 步骤2：以每一个非终结符号为状态作结点； 步骤3：对于形如Q∷=T的每个规则，引一条从开始状态S到状 态Q的弧，其标记为T；而对形如Q∷=RT的规则引一条从状态 R到Q的弧，其标记为T。其中R为非终结符号，T为终结符号； 步骤4：识别符号为终止状态。 第三章 词法分析
第三章词法分析 3.2正则表达式与有穷状态自动机 3.21状态转换图与转换系统 A 状态转换图的构造 a 步骤1:以S为开始状态作结点; B 步骤2:以每一个非终结符号为状态作结点 (a) 步骤3:对于形如Q∷=T的每个规则,引一条从开始状态S到状 态Q的弧,其标记为T;而对形如Q∷=RT的规则引一条从状态 R到Q的弧,其标记为T。其中R为非终结符号,T为终结符号; 步骤4:识别符号为终止状态 GLZ]: Z::Za Aa Bb A::=Ba a B::=Ab b
3.2 正则表达式与有穷状态自动机 3.2.1 状态转换图与转换系统 • 状态转换图的构造 步骤1：以S为开始状态作结点； 步骤2：以每一个非终结符号为状态作结点； 步骤3：对于形如Q∷=T的每个规则，引一条从开始状态S到状 态Q的弧，其标记为T；而对形如Q∷=RT的规则引一条从状态 R到Q的弧，其标记为T。其中R为非终结符号，T为终结符号； 步骤4：识别符号为终止状态。 G[Z]：Z::=Za|Aa|Bb A::=Ba|a B::=Ab|b 第三章 词法分析