[教育学]第4章 词法分析.ppt

例：有NFA M4如图，求其等价的正规式R4。 x y (a| b)*(aa| bb)(a| b)* ? 0 1 2 3 4 b a b a a，b a，b ? a，b 图4.9 DFA M4 图4.10 正规式R4 三、从?上的正规式R 构造一个?上的NFA M，使得L(M)=L(R) 首先，对正规式R构造如下拓广转换图： x y R ? 然后通过对R进行分裂和加进新结点的办法，逐步把这个图转变为：每条弧标记为?中的一个字母或ε ，其转换规则如下： 对于 i k j α β 代之为： i j αβ 对于 i j α β 代之为： 1 2 α | β 对于 代之为： 1 2 β * i k j ε β ε 在整个分裂过程中，所有新结点均采用不同的名字，保留x和y为全图的唯一初态结点和终态结点，至此我们就可以得到一个与R 等价的NFA M。 4.5 正规文法与有穷自动机的等价性 一、定理： 对于给定的正规文法G[R]，可以直接构造一个NFA M，使得L（M）=L（ R ）。 对于?上的任一个NFA M ，可以直接构造正规文法G[R] ，使得L（ R ）=L（ M ）。 二、把给定的正规文法G[R]转换为一个?上的NFA M构造规则: 设G[R]=（VN，VT，P，R）， NFA M=（ K，Σ，f，S，Z） 1.令 Σ= VT； 2. K = VN，S = R；即对G中的每个非终结符生成M的一个状态（不妨取相同的名字，G的开始符号是M的初态； 3.增加一个新状态Z，作为NFA M 的终态，Z∈K； 4.对G中的形如A?tB（其中t为终结符或ε；A和B为非终结符）的产生式，构造M的一个转换函数f（A，t）=B； 5.对G中的形如A?t（其中t为终结符或ε；A和B为非终结符）的产生式，构造M的一个转换函数f（A，t）=Z； 例子:P65 三、把给定的?上的NFA M转换为一个正规文法G[R]的构造规则: 设NFA M=（ K，Σ，f，S，Z），G[R]=（VN，VT，P，R）， 1.令 VT = Σ ； 2.令VN = K即对G中的每个非终结符生成M的一个状态（不妨取相同的名字，G的开始符号是M的初态； 3.令R= S（如果M有多个初态，应先拓广自动机，引入新初态x）； 4.对M 的终态Z增加一个产生式： Z?ε； 5.对M的每一个转换函数f（A，t）=B可写G的一个产生式A?tB（其中t为终结符或ε；A和B为非终结符）； 本 章 作 业 P72：7 + 并用正规式描述它所识别的语言。 解题思路：1、文法转化为NFA 2、NFA转化为DFA 3、DFA最小化 4、生成正规式 4.6 词法分析程序的自动构造 词法分析总控程序见图4.15。 界限符 运算符 字母 数字 结束符“#” 开始 到输入流中读下一字符?Char Char是什么？ 初始化 标识符和关键字 词法分析子程序 无符号数 词法分析子程序 运算符 词法分析子程序 界限符 词法分析子程序 结束 图4.15 词法分析总控程序 若对自动机的每一个状态赋予一定的功能，并把其边上的符号视为转移条件，那么自动机就成为一个程序了。以无符号数为例：给定语法图4.16，构造自动机见图4.17。 d . d e + - d 图4.16 无符号数的语法图 图4.17 无符号数的自动机 1 2 3 4 5 6 0 ? d d + ε - . e d . other other d d other e d 7 e 开始 0?N，P，j; 1?e 数字?d; N*10+d?N 是数字？ Y 读字符?char N Y N 整型量 标记?C1 是’－’吗？ 读字符?char 是’e’吗？ 是’－’吗？ －1?e 读字符?char Y N Y N 读字符?char 是数字？ Y 数字?d;N*10+d?N； j+1?j 是数字？ Y 读字符?char ERROR N N 实型量 标记?C1 是数字？ Y 数字?d; P*10+d?P Y 读字符?char ERROR N N 实型量标记?C1 N*10e*P-j? t 结束 Y N 整数部分 小数部分 是’．’吗？ 是数字？ 指数部分 N 图4.18 无符号数词法分析流程图 最后可得到无符号数分析算法流图见图4.18。 第4章 词法分析 本章将讨论词法分析程序的设计原则，单词的描述技术，识别机制及词法分析程序的自动构造原理。 4.1 对于词法分析程序的要求 4.2 正规表达式与正规集（正规语言） 4.3 有穷自动机 4.5 正规文法与有穷自动机的等价性 4.4 正规式与有穷自动机的等