编译原理讲义 (第三章:词法分析) 南京大学计算机系 赵建华
编译原理讲义 (第三章:词法分析) 南京大学计算机系 赵建华
词法分析与词法分析程序 ·词法分析的任务是识别源程序中具有独 立含义的最小语法单位-号或单词,如 标识符,无正负号常数与界限符等。并 把源程序转换为等价的内部表示形式 功能: 读入源程序字符串;识别单词(符号); 转换成属性字; 些其他的简单工作:删除注解,预加工处 理
词法分析与词法分析程序 • 词法分析的任务是识别源程序中具有独 立含义的最小语法单位----符号或单词,如 标识符，无正负号常数与界限符等。并 把源程序转换为等价的内部表示形式。 • 功能： – 读入源程序字符串；识别单词（符号）； – 转换成属性字； – 一些其他的简单工作：删除注解，预加工处 理
符号识别和重写规则 规则例子: :=字母|字母 在上面的例子中,实际可以展开为∷ a b c d 如果我们规定终结符号的集合为字符,那 么我们会发现上面的规则都满足正则文法 的规则限制:U:=T|UT。因此,我们可以 使用有限自动机来辅助完成词法分析
符号识别和重写规则 • 规则例子： – ::= 字母 | 字母 | … – 在上面的例子中，实际可以展开为 ::= a | b | c | d |… • 如果我们规定终结符号的集合为字符，那 么我们会发现上面的规则都满足正则文法 的规则限制: U::=T | UT。因此，我们可以 使用有限自动机来辅助完成词法分析
实现方式 完全融合:由于正则文法是CFG的一种 特例。所以,可以把词法规则和语法规 则统一处理, 相对独立:词法分析作为子程序。当语 法分析程序需要读下一个符号的时候, 调用这个子程序 完仝独立:词法分析程序作为单独的 趟来实现
实现方式 • 完全融合：由于正则文法是CFG的一种 特例。所以，可以把词法规则和语法规 则统一处理。 • 相对独立：词法分析作为子程序。当语 法分析程序需要读下一个符号的时候， 调用这个子程序。 • 完全独立：词法分析程序作为单独的一 趟来实现
状态转换图与转换系统 别标志符程序的程序的流程图见图3-1; 在流程图中的每个边上的操作一般都是 判断输入符号是否满足等于某些值。如 果不等于,那么识别失败。 实际上,这样的流程图是一种模式 我们可以把流程图简化为一个状态转换 图。状态转换图的运行由输入驱动。状 态转换图包括状态,联接状态的边。有 些状态是接收状态,每条边都标记了 个符号
状态转换图与转换系统 • 识别标志符程序的程序的流程图见图3-1； 在流程图中的每个边上的操作一般都是 判断输入符号是否满足等于某些值。如 果不等于，那么识别失败。 • 实际上，这样的流程图是一种模式。 • 我们可以把流程图简化为一个状态转换 图。状态转换图的运行由输入驱动。状 态转换图包括状态，联接状态的边。有 些状态是接收状态，每条边都标记了一 个符号
转换图的运行和接受 转换图在运行的时候,由一个当前的状 态。每次输入一个符号的时候,转换图 的状态改变如下:沿着从当前状态离开 的,并且用输入符号标记的边,到达这 个边的目标状态 一个符号串被状态转换图接受当且仅当 从初始状态出发,逐次输入符号串中的 所有符号的时候,最终的状态是接受状
转换图的运行和接受 • 转换图在运行的时候，由一个当前的状 态。每次输入一个符号的时候，转换图 的状态改变如下：沿着从当前状态离开 的，并且用输入符号标记的边，到达这 个边的目标状态。 • 一个符号串被状态转换图接受当且仅当 从初始状态出发，逐次输入符号串中的 所有符号的时候，最终的状态是接受状 态
从文法构造状态转换图 我们可以给每个正则文法构造一个状态 转换图。 其基本思想如下: 当我们使用自底向上的方式规约一个正则文 法的句子的时候,得到的句型都是形如 Utx(tx为终结符号串)。而下次规约的规则总 是满足V∴=Ut。如果我们把非终结符号作为 状态,而把饮看作尚未读入的部分时,就得 到一个状态转换图。P61图3-4
从文法构造状态转换图 • 我们可以给每个正则文法构造一个状态 转换图。 • 其基本思想如下： – 当我们使用自底向上的方式规约一个正则文 法的句子的时候，得到的句型都是形如 Utx(tx为终结符号串)。而下次规约的规则总 是满足V::=Ut。如果我们把非终结符号作为 状态，而把tx看作尚未读入的部分时，就得 到一个状态转换图。P61图3-4
从文法构造状态转换图(算法) 步骤一:引入一个开支状态S(假定S不 是非终结符号 步骤二:每个非终结符号作为一个结点。 步骤三 Q:=T:从S到Q有一条标记为T的弧 Q:=RT:从R到Q有一条标记为T的弧。 识别符号为接受状态
从文法构造状态转换图(算法) • 步骤一：引入一个开支状态S（假定S不 是非终结符号。 • 步骤二：每个非终结符号作为一个结点。 • 步骤三： – Q::=T：从S到Q有一条标记为T的弧。 – Q::=RT：从R到Q有一条标记为T的弧。 • 识别符号为接受状态
从文法构造状态转换图(例子) A Z: :Za Aa Bb A: : a S z B: =Ab b
从文法构造状态转换图(例子) S A B Z Z ::= Za | Aa | Bb A::= Ba | a B ::= Ab | b
使用状态转换图构造正则文法 从构造步骤来看,正则文法和状态转换 图之间具有一种对应关系 状态转换图具有直观的特点,所以给定 个正则语言,构造状态转化图比较方 便
使用状态转换图构造正则文法 • 从构造步骤来看，正则文法和状态转换 图之间具有一种对应关系。 • 状态转换图具有直观的特点，所以给定 一个正则语言，构造状态转化图比较方 便