词法分析：运算优先级与正规式

"这篇PPT来自西安交通大学，主题是‘运算的优先级——词法分析’，由Yinliang Zhao在2011年讲解。内容涵盖了词法分析、有限自动机及其设计与实现，重点讲解了正规式、运算优先级以及如何用括号改变运算顺序。" 在计算机科学中，词法分析是编译器或解释器的第一步，它将源代码分解成有意义的符号单元，称为标记（tokens）。这个过程通常由词法分析器（lexer或tokenizer）完成，它依据一定的规则来识别和处理字符序列。在本PPT中，运算的优先级是一个关键概念，特别是在处理正规式时。 正规式是描述字符模式的简洁方式，它们用于定义语言中的字符串模式。例如，正规式`a|b*`表示可以是单一的字符'a'或者零个或多个'b'字符的序列。正规式中存在三种主要运算：选择（|）、连接（）和重复（*）。选择运算表示“或”，连接运算表示连续的字符序列，而重复运算表示前面的字符或子正规式可以重复任意次数。 运算的优先级在正规式中很重要，因为它决定了如何解析复杂的表达式。根据PPT，乘法运算符`*`的优先级最高，连接运算符``其次，选择运算符`|`的优先级最低。例如，正规式`a|bc*`首先会被解析为`a`或`bc`的重复，而不是`a`或`b`后跟着零个或多个`c`。为了改变这种默认的运算顺序，可以使用括号进行分组，如`(a|b)c`或`(a|bb)*`。 正规式`ba*`表示所有以`b`开头，后面跟着零个或多个`a`的字符串，其正规集是所有这样的字符串。`a(a|b)*`则表示所有以`a`开头，后面跟着零个或多个`a`或`b`的字符串。而`(a|b)*(aa|bb)(a|b)*`则是一个更复杂的正规式，它描述了一个更特定的语言模式。 理解正规式和运算优先级对于编写词法分析器或正则表达式至关重要，因为它们直接影响到程序如何理解和处理输入的字符流。在实际编程中，这可以帮助我们编写出能正确匹配和处理各种字符串模式的代码。此外，非确定有限自动机（NFA）和确定有限自动机（DFA）的概念也在词法分析中起到核心作用，它们是理论基础，帮助我们构建能够识别正规集的机器模型。