《湖南大学编译原理课件3.ppt

构建词法分析器的方法 DFA代码化 使用词法分析器自动生成工具，如：LEX 一个状态转换图可用于识别(或接受)一定的字符串。 作业 3.3.2，3.3.3 3.4.1a)b)，3.6.3， 3.6.4 3.7.1，3.7.2，3.9.3 词法分析器生成工具的功能 在生成的词法分析器中有一个模拟自动机的程序 其余部分由生成工具根据词法规则的描述自动生成，包括 自动机的转换表 和动作相关的代码，适当的时候由模拟器调用。 构造自动机时 首先构造出各个模式对应的NFA 然后将这些NFA合并成为一个NFA （根据需要）进行确定化 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. NFA合并的方法 合并方法： 引入新的开始状态，并引入从这个开始状态到各个原开始状态的ε转换。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 确定化NFA后的处理 对于DFA的每个接受状态，如果对应的NFA状态子集包含多个模式对应的接受状态，那么找出第一个这样的模式，将这个模式作为这个DFA状态的输出。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例子（1） 假设有三个模式 a {A1} abb {A2} a*b+ {A3} 构造各模式的NFA a abb a*b+ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 识别标识符的状态转换图 1 2 3 字母 其他 字母或数位 * 识别整常数的状态转换图 1 2 3 数位 其他 数位 * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 状态转换图举例：关系算符relop 注：双圈表示接收状态 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 保留字和标识符的识别 在很多程序设计语言中，保留字也符合标识符的模式，识别标识符的状态转换图也会识别保留字。 解决方法 在符号表中预先填写保留字，并指明它们不是普通标识符。 为关键字/保留字建立单独的状态转换图。并设定保留字的优先级高于标识符。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 其它常用状态转换图 问题：状态19,20,21分别识别什么记号 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 词法分析器的体系结构 从转换图构造词法分析器的方法（DFA代码化） 变量state记录当前状态 整体可通过一个switch来根据state的值转到相应的代码 每个状态对应于一段代码。 这段代码根据读入的符号，确定下一个状态 如果找不到相应的边，则调用fail()进行错误恢复 进入某个接受状态时，返回相应的记号。 注意状态有*标记时，需要回退forward指针。 失效函数 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. DFA代码化举例——Relop对应的代码概要 Evaluation only. Created with As