词法分析与有限自动机：正规式和确定自动机

"该资源是一份来自西安交通大学的关于词法分析的PPT，由Yinliang Zhao主讲，内容涵盖了有限自动机、词法分析器的设计与实现以及自动生成等方面。重点讲解了3型文法的两种表示形式：左线性文法和右线性文法，并深入探讨了正规式和正规集的概念及其运算规则。" 在计算机科学中，词法分析是编译器设计的重要组成部分，其主要任务是将源代码分解成一系列有意义的符号，即标记(token)，以便后续的语法分析和语义分析。在该PPT中，3型文法被提及，这是上下文无关文法的一个子集，它有两种常见的表示形式：左线性文法和右线性文法。 1. 左线性文法：这种文法的所有产生式规则形式为A → αa，其中A是非终结符，α是零个或多个非终结符的序列，a是终结符。左线性文法易于理解，且通常用于构造简单的词法分析器。 2. 右线性文法：与左线性文法类似，它的产生式规则形式为A → aβ，其中A是非终结符，a是终结符，β是零个或多个非终结符的序列。右线性文法同样简洁，易于处理。 PPT还详细讨论了有限自动机，包括确定有限自动机(DFA)和非确定有限自动机(NFA)。这两种自动机都能识别正规集，即可以由正规式表示的字符串集。 3. 确定有限自动机：DFA是一种状态机器，每个状态下都有一个明确的转移，对于给定输入，其行为是确定的。DFA可以用来识别正规式描述的语言。 4. 非确定有限自动机：NFA允许在给定状态下对多个输入符号进行转移，且在某些情况下，即使没有输入也能转移。尽管NFA更灵活，但每个NFA都可以等价地表示为一个DFA。 正规式是描述正规集的一种简洁方式，它们通过基本正规式、选择运算符`|`、连接运算符`·`和重复运算符`*`来构建。正规式的运算遵循特定的优先级，其中`*`的优先级最高，接着是连接，最后是选择。使用括号可以帮助改变运算的顺序。 例如，在给定的字母表{a, b}中，正规式`ba*`表示所有以b开头，后面跟着任意数量a的字符串集合；`a(a|b)*`则表示所有以a开头，后面跟着任意数量的a或b的字符串集合。 通过了解正规式和有限自动机，我们可以有效地设计词法分析器，这些工具在编译器和解释器的开发中扮演着核心角色，因为它们能够高效准确地解析源代码，为编译过程提供基础。