有限自动机与正规文法：词法分析核心概念

"Chomsky文法-词法分析PPT（西安交大）" 本资源主要涵盖了Chomsky文法中的2型文法、3型文法以及正规文法，特别是强调了3型文法与有限自动机的等价性。这份资料来自西安交通大学，内容围绕词法分析展开，包括了有限自动机的概念、设计与实现，以及词法分析器的自动生成。 在第三章“词法分析”中，首先介绍了有限自动机（Finite Automata）。确定有限自动机（Deterministic Finite Automaton, DFA）和非确定有限自动机（Non-deterministic Finite Automaton, NFA）是有限自动机的两种形式。确定有限自动机在每个状态下，对于输入符号集的每一个符号，只有一个确定的转移状态。而非确定有限自动机则可能在相同状态下，对同一输入符号有多个转移状态。尽管NFA具有更多的灵活性，但DFA在某些方面更易于理解和处理，例如在词法分析中。 正规文法（Regular Grammar）和确定有限自动机之间存在等价性，这意味着可以用一种形式来描述的语言，也可以用另一种形式来等价地描述。正规式（Regular Expression）是描述正规文法的一种简便方法，它可以用来表示字符串的模式。正规式的基本操作包括选择（|）、连接（ concatenation）和重复（*）。选择表示“或”，连接表示连续，重复表示零个或多个前一元素的序列。 例如，正规式“ba*”表示所有以“b”开始，后面跟着零个或多个“a”的字符串。正规式“a(a|b)*”则描述所有以“a”开始，后面跟着任意数量的“a”或“b”的字符串。 正规集是所有符合正规式规则的字符串的集合。正规式的运算有明确的优先级，其中*的优先级最高，其次是连接，最后是选择。为了改变运算顺序，可以使用括号。 通过学习这份资料，读者可以深入理解词法分析的基础，掌握如何利用有限自动机和正规式来描述和识别编程语言中的词汇结构，这对于编译原理和语言处理领域来说是非常重要的基础知识。