编译原理 第8讲(第四章).ppt

第四章词法分析 词法分析程序正规式 正规文法和正规集有穷自动机NFA的确定化 DFA的最小化正规式 正规文法和有穷自动机 有穷自动机和正规表达式的等价性 1 对于 上的一个NFAM 可以构造一个 上的正规式R 使得L R L M 2 对于 上的一个正规式R 可以构造一个 上的NFAM 使的L M L R 由NFAM构造正规式r 从 上的一个NFAM 构造 上的 一个正规式r 使得L M L r 的方法 由NFAM构造正规式r步骤如下 1 在NFAM的状态图中增加2个新节点 X和Y 从X节点到NFAM的所有初态引 标记的弧 从NFAM的所有终态到Y节点引 标记的弧 形成一个新的NFAM 这个M 只有一个初态X和一个终态Y 显然M与M 等价 2 逐步消去M 的节 直至剩下X和Y节 消节的过程中 根据消节规则 逐步用正规式标记弧 消结规则 最后X至Y的标记则为所求的正规式 NFA到正规式的例子 2 消除M中的所有结点 消结规则参见P62 例子的解 由正规式r构造NFAM 从 上的一个正规式r 构造 上的一个NFAM 使得L M L r 的方法 语法制导 的方法 即按正规式的语法结构指引构造过程 构造规则具体描述如下 语法制导 的方法 1 R 构造任一具有空终态集的NFAM 2 R 构造的NFAM k0 f k0 k0 f k0 a 对于所有a 都没定义 3 R a 构造的NFAM k0 k1 f k0 k1 f k0 a k1 4 R R1 R2 将步骤 1 2 3 分别应用到R1 R2 产生M1 K1 f1 k1 F1 M2 K2 f2 k2 F2 其中K1 K2不相交 构造的NFAM K1 K2 k f k F k是新增加的状态符号 f包含f1和f2 且f k a f1 k1 a f2 k2 a 若k1 F1且k2 F2 则F F1 F2 否则F F1 F2 k 语法制导 的方法 5 R R1 R2将步骤 1 2 3 分别应用到R1 R2 产生M1 K1 f1 k1 F1 M2 K2 f2 k2 F2 其中K1 K2不相交 构造的NFAM K1 K2 f k1 F2 f包含f1和f2 且f k a f1 k a 当k F1时 f k a f2 k a 当k K2时 f k1 k2 6 R R1 将步骤 1 2 3 分别应用到R1 产生M1 K1 f1 k1 F1 构造的NFAM K1 k0 F0 f k0 F0 其中k0 F0是新增加的两个状态 f k a f1 k a 当k F1时 f k0 f F1 k1 F0 对于正规式R 构造的NFA S 对于正规式R 构造的NFA x y 或 对于正规式R a 构造的NFA S a 对于正规式r r R1 R2构造的NFA 对于正规式r r R1R2构造的NFA 对于正规式r r R1 构造的NFA 正规表达式1 0 0 1 举例 从正规表达式构造等价的 NFA 或 举例 从正规表达式构造等价的 NFA R a ab bb 有穷自动机和正规文法的等价性 1 对于一个NFAM 都存在一个正规文法G 使得L G L M 2 对于一个正规文法G 都存在一个NFAM 使的L M L G 由正规文法G构造NFAM 定理 设G VN VT P S 为一个正规文法 则存在一个有穷自动机NFAM K f S Z 使得L M L G M的构造方法 VT S S为G中每一个非终结符生成M的一个状态 不妨取成相同的名字 G的开始符号是M的开始状态S 增加一个新状态Z 作为NFA的终态 K VN Z 若G中有形如A tB的产生式 则令f A t B 若G中有形如A t的产生式 则令f A t Z G S S aA bB A aB bAB aS bA 例 求与文法G S 等价的NFA 由NFAM构造正规文法G 定理 已知一个有穷自动机NFAM K f S Z 则存在一个正规文法G VN VT P S 使得L M L G G的构造方法 VN K VT S SP 若f A t B 则A tB在P中 对于可接受状态Z 增加产生式Z G A B C D a b P AP A aB bDB bCC aA bD D aB bD 求得 例 求与NFA等价的文法G S 关系图 词法分析程序的自动构造 对有穷自动机和正规表达式进行了上述讨论之后 我们介绍词法分析程序的自动构造方法 这个方法基于有穷自动机和正规表达式的等价性正规式用于说明 描述 单词的结构十分简洁方便 而把一个正规式编译 或称转换 为一个NFA进而转换为相应的DFA 这个NFA或DFA正是识别该正规式所表示的语言的句子的识别器 基于这种方法来构造词法分析程序 总结 词法分析程序的设计技术可应用于其它领域 比如查询语言以及信息检索系统等 这种应用领域的程序设计特点是 通过字符串模式的匹配来引发动作 又如LEX 说明词法分析程序的语言 可以看成是一个模式动作语言 词法分析程序的自动构造工具也广泛应用于许多方面 如用以生成一个程序 可识别印刷电路板中的缺陷 又如开关线路设计和文本编辑的自动生成等 习题 P721 3 6712 本章小结 词法分析程序是编译第