词法分析详解：从正规式到有限自动机

"单词的机内表示在编译原理中占据重要位置，它涉及到词法分析这一关键步骤。词法分析器（也称作扫描器）负责读取源程序，根据字符流识别出一个个单词符号，如关键字、标识符、常数、算符和界符。这些单词符号在计算机内部通常通过二元式来表示，结构为 `<单词类别，该单词所在符号表项的地址>`，这种表示方式被称为种别码。 在词法表示中，不同的单词类别有不同的处理方式： 1. 关键字和分界符：如果每个关键字或分界符都有独立的编码，它们的单词值没有实际意义。但若一类只有一个编码，单词值可以是整数的内部编码或其自身符号串。 2. 标识符：其单词值可以直接是标识符的文本本身。 3. 常数：通常以二进制形式表示其单词值。 词法分析阶段依据的是语言的词法规则，正规式和有限自动机是描述这些规则的工具。在教学内容中，正规表达式、状态转换图和有限自动机（NFA和DFA）是重点，包括NFA到DFA的转换、DFA的化简以及正规式与有限自动机之间的转换。此外，词法分析器可以通过手工编写，也可以使用自动工具如LEX自动生成。 词法分析器有以下功能和输出形式： - 输入源程序的字符流。 - 扫描并识别出单词符号，如关键字、标识符、常量、运算符和分界符。 - 输出的单词符号通常分为五类：关键字、标识符、字面常数、运算符和分界符。 例如，在处理如下源代码片段`while i<>j do if i>j then i:=i-j else j:=j-i;`时，词法分析器会将其分解为多个单词符号，如`while`、`i`、`<>`、`j`、`do`、`if`等，并输出这些单词符号供后续的语法分析和语义分析使用。 掌握正规式、有限自动机的概念以及如何将它们用于词法分析程序的设计至关重要。同时，理解词法分析器的自动产生工具如LEX可以帮助简化开发过程，使扫描器能像有限自动机一样工作，根据正规式描述的规则高效地识别单词符号。"