词法分析：编译原理中的关键构造

在高等教育的编译原理课程中，第三章深入探讨了词法分析这一关键环节。词法分析是程序语言处理的第一步，主要负责将源程序中的字符流转换为可理解的单词流，即二元式表示。这一章由李明新老师编著，共50页，于19-2-23更新。 首先，词法分析器的功能被明确为接收输入源程序，通过识别并分类不同的符号（如关键字、标识符、常数、运算符和界限符），将其转换成TOKEN字，每个TOKEN字包含一个表示类别(class)的整数值和可能的属性(value)。关键字、运算符和界限符由编译程序预先定义，而标识符和常数则由用户提供，并通过TOKEN的VALUE字段存储符号表或常数表的指针。 单词符号的内部表示形式非常重要，TOKEN字通过CLASS和VALUE字段分别记录单词的类别和属性。CLASS用于语法分析，VALUE则在语义分析阶段提供更具体的上下文信息。例如，"BEGINA:=BEND;" 的词法分析结果会形成一个符号表，其中包含了每个单词的类别和相应的值。 词法分析器的设计分为两大部分：词法分析器的要求和其设计方法。词法分析器需要具备一次或多次扫描的能力，即既可以采用交互式结构（一遍扫描），也可以采取独立式结构（多遍扫描）。设计步骤包括明确词法分析器与其他模块的接口，确定不同类型的单词如何转化为TOKEN字，以及定义TOKEN字的结构。 此外，本章还涉及到了确定有限自动机（DFA）和非确定有限自动机（NFA）在词法分析中的应用，以及如何通过正规式与有限自动机的等价转换，确保词法分析器的正确性和效率。这涉及到理论基础，如正规集、正规文法与自动机之间的转换，这些概念对于理解和实现高效的词法分析器至关重要。 第三章内容涵盖了词法分析器的核心概念、分类标准、设计原则和实现技术，为学习编译原理的学生提供了深入理解词法分析阶段的关键知识。