正则表达式与词法分析笔记

"这篇笔记主要涵盖了编译原理中的基本概念，包括词法分析和正则表达式的使用。" 在编译原理中，我们首先关注的是如何处理源代码的字符序列。这一过程通常由读取源程序的字符序列开始，接着是拼接这些字符形成单词，也就是我们所说的“token”，并构建其内部表示。这个内部表示是编译器理解源代码的基础，它能够帮助我们检查源程序中的词法错误，确保输入的字符序列符合编程语言的规则。 在字符序列的处理中，有一些特殊的符号串概念。例如，空串用符号""表示，它不包含任何字符，但仍然是一种有效的字符串。空串集与空集不同，空串集包含一个元素""，而空集不包含任何元素。符号串可以通过连接操作组合，比如"abc"和"de"连接后形成"abcde"。此外，还有符号串的方幂运算，如Α0表示空串，Α1是集合Α本身，Α2是Α与自身连接等。 符号串集合的操作也十分关键，比如乘积操作AB包含了所有可能的AB组合，其中A和B是两个符号串集合。正闭包A+表示集合A的所有非空子串的集合，而星闭包A*则包含A的所有子串，包括空串。正闭包和星闭包在表示字符序列的无限可能性时非常有用，比如集合A={a,b}，A+就能表示所有由a和b组成的任意长度的字符串。 正则表达式是描述这些符号串集合的有效工具。ε表示空字符串，可以匹配任何位置的空隙，而∅表示空集，不匹配任何字符串。一个字符a是它自身的正则表达式，可以匹配单个a字符。正则表达式可以通过一些操作结合，如括号分组()、逻辑或运算|、连接运算(连接两个正则表达式)、重复运算*(零次或多次)和+(一次或多次)来构建复杂模式。例如，(0|1)*可以匹配所有0和1的任意组合，而{0,1}*虽然形式上相似，但它表示的是集合{0,1}的星闭包，即所有由0和1组成的字符串。 词法分析阶段，正则表达式的语义函数用来给正则表达式赋予实际意义，它生成的符号串集合被称为正则表达式的正则集。在实践中，正则表达式用于识别源代码中的关键字、标识符、数字等元素，帮助构建出语言的词汇结构，为后续的语法分析奠定基础。 编译原理的核心是理解和转换源代码，而词法分析作为第一步，通过正则表达式和符号串的概念来解析源代码的结构，为整个编译过程提供准确的输入。