编译原理讲义 (第三章:词法分析) 南京大学计算机系 赵建华
编译原理讲义 (第三章:词法分析) 南京大学计算机系 赵建华
词法分析与词法分析程序 ·词法分析的任务是识别源程序中具有独 立含义的最小语法单位-号或单词,如 标识符,无正负号常数与界限符等。并 把源程序转换为等价的内部表示形式 功能: 读入源程序字符串;识别单词(符号); 转换成属性字; 些其他的简单工作:删除注解,预加工处 理
词法分析与词法分析程序 • 词法分析的任务是识别源程序中具有独 立含义的最小语法单位----符号或单词,如 标识符，无正负号常数与界限符等。并 把源程序转换为等价的内部表示形式。 • 功能： – 读入源程序字符串；识别单词（符号）； – 转换成属性字； – 一些其他的简单工作：删除注解，预加工处 理
符号识别和重写规则 规则例子: <标志符>:=字母|<标识符>字母 在上面的例子中,实际可以展开为<标识符>∷ a b c d 如果我们规定终结符号的集合为字符,那 么我们会发现上面的规则都满足正则文法 的规则限制:U:=T|UT。因此,我们可以 使用有限自动机来辅助完成词法分析
符号识别和重写规则 • 规则例子： – <标志符> ::= 字母 | <标识符>字母 | … – 在上面的例子中，实际可以展开为<标识符> ::= a | b | c | d |… • 如果我们规定终结符号的集合为字符，那 么我们会发现上面的规则都满足正则文法 的规则限制: U::=T | UT。因此，我们可以 使用有限自动机来辅助完成词法分析
实现方式 完全融合:由于正则文法是CFG的一种 特例。所以,可以把词法规则和语法规 则统一处理, 相对独立:词法分析作为子程序。当语 法分析程序需要读下一个符号的时候, 调用这个子程序 完仝独立:词法分析程序作为单独的 趟来实现
实现方式 • 完全融合：由于正则文法是CFG的一种 特例。所以，可以把词法规则和语法规 则统一处理。 • 相对独立：词法分析作为子程序。当语 法分析程序需要读下一个符号的时候， 调用这个子程序。 • 完全独立：词法分析程序作为单独的一 趟来实现
状态转换图与转换系统 别标志符程序的程序的流程图见图3-1; 在流程图中的每个边上的操作一般都是 判断输入符号是否满足等于某些值。如 果不等于,那么识别失败。 实际上,这样的流程图是一种模式 我们可以把流程图简化为一个状态转换 图。状态转换图的运行由输入驱动。状 态转换图包括状态,联接状态的边。有 些状态是接收状态,每条边都标记了 个符号
状态转换图与转换系统 • 识别标志符程序的程序的流程图见图3-1； 在流程图中的每个边上的操作一般都是 判断输入符号是否满足等于某些值。如 果不等于，那么识别失败。 • 实际上，这样的流程图是一种模式。 • 我们可以把流程图简化为一个状态转换 图。状态转换图的运行由输入驱动。状 态转换图包括状态，联接状态的边。有 些状态是接收状态，每条边都标记了一 个符号