编译技术2-2

Lexical Analysis: Lexemes, Tokens, and Patterns 词法分析：词素、标记与模式

1. Core Concepts 核心概念 (1) 基本定义 | 术语 | 英文 | 定义 | 示例 | |------|------|------|------| | 词素 | Lexeme | 源代码中的原始字符序列 | "while", "123" | | 标记 | Token | 词素的逻辑分类 | T_While, T_Number | | 模式 | Pattern | 描述词素结构的规则 | [a-zA-Z_][a-zA-Z0-9_]* | | 正则表达式 | Regular Expression | 形式化的模式描述语言 | [0-9]+(\.[0-9]+)? |

(2) 处理流程 
graph LR
    A[字符流] --> B(词素提取)
    B --> C(标记分类)
    C --> D[Token序列]

2. Token-Lexeme Association 标记与词素的关联 (1) 关联策略 | 关联类型 | 特点 | 示例 | |----------|------|------| | 1对1 | 唯一词素对应唯一标记 | while → T_While | | 1对多 | 多个词素共享标记类型 | x, count → T_Identifier | | 多对1 | 不同模式映射到同一标记 | 123, 3.14 → T_Number |

(2) 集合表示法 

1
2
3
4
# 标记的词素集合定义
T_While   : { "while" }
T_Number  : { "0", "1", ..., "3.14", ... }
T_String  : { "\"\"", "\"a\"", ... }

3. Pattern Specification 模式规范 (1) 正则表达式语法 | 表达式 | 描述 | 匹配示例 | |--------|------|----------| | a | 单字符 | 'a' | | a|b | 逻辑或 | 'a' 或 'b' | | a* | 零次或多次 | '', 'a', 'aa' | | [a-z] | 字符范围 | 'b', 'k' | | \d | 数字简写 | '0'-'9' |

(2) 词法规则示例 

1
2
3
4
5
6
/* C语言部分词法规则 */
%%
"while"     { return T_While; }
[a-zA-Z_]\w* { return T_Identifier; }
[0-9]+      { return T_IntNumber; }
"=="        { return T_EqualOp; }

4. Implementation Techniques 实现技术 (1) 词素提取算法 

1
2
3
4
5
def extract_lexeme(input_stream):
    buffer = []
    while (char := next_char(input_stream)) not in DELIMITERS:
        buffer.append(char)
    return ''.join(buffer)

(2) 标记分类逻辑 

1
2
3
4
5
6
7
Token classify_lexeme(char* lexeme) {
    if (is_keyword(lexeme)) 
        return create_keyword_token(lexeme);
    else if (is_number(lexeme))
        return create_number_token(lexeme);
    // ...其他分类规则
}

5. Case Study: Number Handling 案例研究：数字处理 (1) 模式设计 

1
2
# 匹配整数和浮点数
number = [0-9]+(\.[0-9]+)?([eE][+-]?[0-9]+)?

(2) 属性附加 

1
2
3
4
5
6
7
8
9
10
11
12
struct Token {
    TokenType type;
    union {
        int int_val;
        double float_val;
    } attr;
};

// 解析示例
Token t = parse_number("3.14");
// t.type = T_Number
// t.attr.float_val = 3.14

6. Key Takeaways 核心结论 1. 词素是原始数据，标记是抽象分类
Lexemes are concrete, tokens are abstract categories

  1. 正则表达式是模式描述的核心工具
    Regular expressions are fundamental for pattern definition

  2. 灵活的分类策略支持语言扩展
    Flexible classification enables language evolution

"词法分析是将混沌字符流转化为结构化标记的艺术与科学"
"Lexical analysis is the art and science of transforming chaos into structured tokens"

Formal Languages and Regular Expressions 形式语言与正则表达式

1. Formal Language Basics 形式语言基础 (1) 核心定义

概念 英文 数学表示 示例
字母表 Alphabet Σ = {a,b,...} Σ = {0,1}
字符串 String 字母表元素的有限序列 "0110", "abb"
空串 Empty String ε ""
语言 Language 字符串的集合 {ε, "a", "aa"}

(2) 关键特性 • 无限语言的有限描述：

1
L = {a^n | n ≥ 1}  // 无限语言{a,aa,aaa...}的正则表达式: a+
• 特殊语言：

• 空语言 ∅ ≠ {ε}（含空串的语言）

2. Regular Expressions 正则表达式 (1) 原子表达式

表达式 匹配内容 示例语言
ε 空串 {""}
a 单字符a {"a"}

(2) 复合表达式

操作 符号 数学意义 示例
连接 R₁R₂ L(R₁)∘L(R₂) a(b|c) → {"ab","ac"}
选择 R₁|R₂ L(R₁)∪L(R₂) a|b → {"a","b"}
闭包 R* 克林闭包 a* → {ε,"a","aa",...}
分组 (R) 运算优先级 (ab)* vs ab*

(3) 语法扩展 

1
2
3
[0-9]    ≡ 0|1|...|9       // 字符类
R+       ≡ RR*             // 正闭包
R?       ≡ ε|R             // 可选

3. Lexical Analysis Applications 词法分析应用 (1) Token模式描述 | Token类型 | 正则表达式 | 匹配词素 | |-----------|------------|----------| | 标识符 | [a-zA-Z_][a-zA-Z0-9_]* | "count", "_temp" | | 整数 | [0-9]+ | "123", "0" | | 浮点数 | [0-9]+\.[0-9]+ | "3.14" |

(2) 词法规则示例 

1
2
3
4
%%
"if"       { return T_If; }
[a-z]+     { return T_Identifier; }
[0-9]+     { return T_Int; }

4. Theoretical Foundations 理论基础 (1) 形式语言层级

graph TD
    A[Regular] --> B[Context-Free]
    B --> C[Context-Sensitive]
    C --> D[Recursively Enumerable]

(2) 自动机对应关系 | 语言类型 | 自动机 | 描述能力 | |----------|--------|----------| | 正则语言 | DFA/NFA | 词法模式 | | 上下文无关 | PDA | 语法结构 |

5. Key Takeaways 核心结论

  1. 正则表达式是描述词素集合的终极工具
    Regular expressions are the ultimate tool for lexeme sets

  2. 有限描述可表达无限语言
    Finite descriptions can capture infinite languages

  3. 理论自动机与实现技术紧密关联
    Automata theory directly informs implementation

"形式语言为编译器提供了精确的模式描述框架"
"Formal languages provide precise pattern description frameworks for compilers"

Regular Expression Operator Precedence and Applications 正则表达式运算符优先级与应用

1. Operator Precedence 运算符优先级 (1) 优先级层级（从高到低） | 优先级 | 运算符 | 英文名称 | 示例 | |--------|--------|----------|------| | 1 | (R) | Parentheses 括号 | (ab)* | | 2 | R* | Kleene Star 克林闭包 | a* | | 3 | R₁R₂ | Concatenation 连接 | ab | | 4 | R₁|R₂ | Alternation 选择 | a|b |

(2) 解析示例 

1
ab*c|d  →  ((a(b*))c)|d
• 解析过程：

  1. 先处理b*（优先级最高）
  2. 连接a与b* → ab*
  3. 连接ab*与c → ab*c
  4. 最后处理|d

2. Practical Examples 实际案例 (1) 包含"00"子串的字符串 

1
(0|1)*00(0|1)*
• 匹配原理：

• (0|1)*：任意前缀（包括空串）

• 00：必须包含的连续两个0

• (0|1)*：任意后缀

• 匹配示例：

1
2
3
11011100101  ✓ (包含"00")
1111101111   ✗ (无"00")
0000         ✓ (包含多个"00")

(2) 长度恰好为4的二进制串 方法一：显式连接 

1
(0|1)(0|1)(0|1)(0|1)
• 示例：

1
2
3
4
0000  ✓
1010  ✓
1111  ✓
10000 ✗ (长度超限)

方法二：使用重复计数 

1
(0|1){4}  // 更简洁的写法

(3) 最多包含一个0的字符串 方法一：显式分支 

1
1*(0|ε)1*
• 解析：

• 1*：任意数量的1

• (0|ε)：要么一个0，要么没有

• 1*：任意数量的1

方法二：使用可选符 

1
1*0?1*  // 等价写法
• 匹配示例：

1
2
3
4
11110111  ✓ (一个0)
111111    ✓ (零个0)
0111      ✓ (一个0)
10001     ✗ (两个0)

3. Language Properties 语言性质 (1) 正则语言封闭性 | 性质 | 英文 | 示例 | |------|------|------| | 并集封闭 | Closed under union | L₁∪L₂ = (0|1)* | | 连接封闭 | Closed under concatenation | L₁L₂ = {ab \| a∈L₁, b∈L₂} | | 克林闭包封闭 | Closed under Kleene star | L* = {ε}∪L∪LL∪... |

(2) 非正则语言特征 

1
{0^n1^n | n≥0}  // 需要栈记忆计数，非正则

4. Implementation Notes 实现注意 (1) 贪婪匹配原则 

1
2
import re
re.findall('a*', 'aaa')  # 返回['aaa']而非['a','a','a']

(2) 转义特殊字符 

1
2
\.  # 匹配句点而非任意字符
\\  # 匹配反斜杠

5. Key Takeaways 核心结论 1. 优先级决定解析顺序
Precedence rules govern parsing order

  1. 正则表达式可精确描述词素模式
    Regular expressions precisely define lexeme patterns

  2. 简洁语法与强大表现力并存
    Compact syntax with expressive power

"正则表达式如同精确的手术刀，能解剖出最细微的字符模式"
"Regular expressions are like precision scalpels for dissecting character patterns"

注：本笔记通过具体示例演示了正则表达式优先级规则的实际应用，建议使用regex101.com等工具进行交互式测试。

Regular Expressions for Programming Language Patterns 编程语言模式的正则表达式

1. Identifier Patterns 标识符模式

(1) Basic Identifier Definition 基础标识符定义 

1
2
3
letter = [A-Za-z]          // 字母
digit = [0-9]              // 数字
identifier = letter(letter|digit)*

关键特性： • 首字符必须为字母

First character must be a letter • 后续字符可为字母/数字

Subsequent characters can be alphanumeric • 示例：

count, temp1 (有效)
1stPlace, @name (无效)

(2) C/C++ Identifier Rules C/C++标识符规则 

1
2
// 支持Unicode的现代C++标准
identifier = [a-zA-Z_][a-zA-Z0-9_]*
特殊要求： • 允许下划线开头（如_privateVar）

• 禁止数字开头（如123var无效）

(3) 常见误区分析 

1
(letter* | digit*) ≠ (letter | digit)*
• 错误模式：

letter*允许纯字母，digit*允许纯数字
→ 无法强制"字母开头"规则 • 正确模式：

letter(letter|digit)* 确保首字符为字母

对于二者不相同的理解

初始理解

首先，我看到这个表达式：(letter* | digit*) ≠ (letter | digit)*。这里使用了正则表达式中的符号，如 *（表示零个或多个前面的元素）和 |（表示“或”）。我的任务是理解这两个表达式之间的区别，以及为什么它们不相等。

分解左边的表达式：(letter* | digit*)

让我们先看左边的部分 (letter* | digit*)：

  1. letter*：表示零个或多个字母。例如，可以是 ""（空字符串），"a", "aa", "aaa", 等等。
  2. digit*：表示零个或多个数字。例如，"", "1", "11", "111", 等等。
  3. letter* | digit*：表示要么是零个或多个字母，要么是零个或多个数字。

因此，(letter* | digit*) 生成的语言包括： • 所有由字母组成的字符串（包括空字符串）。

• 所有由数字组成的字符串（包括空字符串）。

例子： • 有效的："", "a", "aa", "1", "11"

• 无效的："a1", "1a", "a1a", "1a1"（因为这些混合了字母和数字）

分解右边的表达式：(letter | digit)*

现在看右边的部分 (letter | digit)*：

  1. letter | digit：表示一个字母或一个数字。
  2. (letter | digit)*：表示零个或多个 letter | digit 的组合。也就是说，可以交替选择字母或数字，任意次数。

因此，(letter | digit)* 生成的语言包括： • 所有由字母和数字任意组合的字符串（包括空字符串）。

例子： • 有效的："", "a", "1", "a1", "1a", "a1a", "1a1", "aa", "11"

比较两边

现在，我们比较 (letter* | digit*) 和 (letter | digit)*：

• (letter* | digit*)：

• 只允许纯字母或纯数字的字符串。

• 不允许字母和数字的混合。

• (letter | digit)*：

• 允许字母和数字的任意组合。

• 包括纯字母、纯数字以及字母数字混合的字符串。

为什么它们不相等？

从上面的分析可以看出：

• (letter | digit)* 生成的字符串集合严格包含 (letter* | digit*) 生成的字符串集合。

• (letter* | digit*) 是 (letter | digit)* 的一个真子集。

具体来说，(letter | digit)* 可以生成像 "a1" 这样的字符串，而 (letter* | digit*) 不能。因此，(letter* | digit*) 不等于 (letter | digit)*。

举例验证

让我们用具体的例子来验证：

  1. 字符串 "a1"： • (letter* | digit*)：无法生成，因为不能混合字母和数字。

    • (letter | digit)*：可以生成（"a" 后跟 "1"）。

    因此，"a1" 在 (letter | digit)* 中，但不在 (letter* | digit*) 中。

  2. 字符串 "aa"： • (letter* | digit*)：可以生成（letter* 部分）。

    • (letter | digit)*：也可以生成。

    两者都包含 "aa"。

  3. 字符串 ""（空字符串）： • (letter* | digit*)：可以生成（letter* 或 digit* 都可以生成空字符串）。

    • (letter | digit)*：可以生成。

    两者都包含 ""。

更形式化的解释

从形式语言的角度：

• letter* 是字母表 {a, b, ..., z} 上的克林闭包。

• digit* 是字母表 {0, 1, ..., 9} 上的克林闭包。

• (letter* | digit*) 是这两个克林闭包的并集，即所有纯字母或纯数字的字符串。

• (letter | digit)* 是字母表 {a, b, ..., z, 0, 1, ..., 9} 上的克林闭包，即所有字母和数字的任意组合。

因此，(letter | digit)* 是一个更大的集合，包含 (letter* | digit*) 的所有元素，还包含额外的混合字符串。

可能的误解

起初，我可能会误以为 (letter* | digit*) 和 (letter | digit)* 是相同的，因为看起来都是在说“字母或数字的重复”。但关键在于 * 的应用范围：

• 在 (letter* | digit*) 中，* 分别应用于 letter 和 digit，然后进行 | 操作。

• 在 (letter | digit)* 中，* 应用于 (letter | digit) 的整体。

这种括号和操作符的顺序导致了不同的语言。

类比

可以做一个类比：

• (letter* | digit*) 类似于“你可以选择一直吃苹果，或者一直吃香蕉，但不能交替”。

• (letter | digit)* 类似于“你可以随意选择吃苹果或香蕉，可以交替，可以重复”。

显然，后者的选择更自由。

数学上的关系

设：

• L1 = (letter* | digit*)

• L2 = (letter | digit)*

那么：

• L1 ⊂ L2（L1 是 L2 的真子集）

• L2 \ L1 包含所有字母和数字混合的字符串

结论

综上所述，(letter* | digit*) 和 (letter | digit)* 不相等，因为前者只生成纯字母或纯数字的字符串，而后者可以生成字母和数字任意混合的字符串。因此，(letter* | digit*) 是 (letter | digit)* 的一个严格子集。

最终答案

(letter* | digit*) 和 (letter | digit)* 不相等，因为：

• (letter* | digit*) 表示“零个或多个字母”或“零个或多个数字”，即只允许纯字母或纯数字的字符串（包括空字符串）。

例如："", "a", "aa", "1", "11"。

• (letter | digit)* 表示“零个或多个字母或数字的任意组合”，即允许字母和数字的任意混合字符串（包括空字符串）。

例如："", "a", "1", "a1", "1a", "a1a", "1a1"。

因此，(letter | digit)* 可以生成 (letter* | digit*) 无法生成的混合字符串（如 "a1"），所以两者不相等。(letter* | digit*) 是 (letter | digit)* 的一个真子集。

Applied Regular Expressions: Email Address Validation

电子邮件地址验证的正则表达式应用

1. 基础定义与字母表 (1) 限定字母表 

1
Σ = \{letter\} ∪ \{., @\} = \{l, ., @\}
• 符号说明：

• l 代表任意字母（letter）

• . 和 @ 作为特殊符号

(2) 正则表达式结构 

1
l+(.l+)*@l+.l+(.l+)*
组件解析： | 部分 | 英文描述 | 中文说明 | 示例 | |------|----------|----------|------| | l+ | One or more letters | 1个或多个字母 | zhangsan | | (.l+)* | Optional subdomains | 可选子域名 | .scut | | @ | Mandatory separator | 固定分隔符 | | | l+.l+ | Main domain | 主域名 | edu.cn |

2. 正则表达式分解 (1) 用户名部分 l+(.l+)* • l+：

必须包含至少1个字母（如zhangsan） • (.l+)*：

可选的.加字母组合（如.cn）

(2) 域名部分 l+.l+(.l+)* • l+：

主域名前缀（如163） • .l+：

顶级域名（如.com） • (.l+)*：

多级子域名（如.edu.cn）

3. 匹配案例验证 (1) 合法案例
zhangsan@scut.edu.cn
• 匹配过程：

  1. zhangsan → l+
  2. @ → 分隔符
  3. scut → l+
  4. .edu → .l+
  5. .cn → .l+

Regular Expressions for Even Number Recognition 偶数识别的正则表达式

1. Problem Definition 问题定义 (1) 目标 识别所有ASCII字符组成的十进制偶数（包含正负号）

(2) 合法示例 

1
2
3
4
42      // 正整数偶数
+1370   // 带符号大数
-3248   // 负偶数
0       // 零是特殊偶数

(3) 非法示例 

1
2
3
4
123     // 奇数
-337    // 负奇数
1.0     // 浮点数（虽然数学上是偶数，但此处不处理）
ABC     // 非数字

2. Regular Expression Breakdown 正则表达式解析 (1) 完整表达式 

1
^[+-]?[0-9]*[02468]$

(2) 组件详解 | 组件 | 英文解释 | 中文说明 | 数学意义 | |------|----------|----------|----------| | ^ | Start of string | 字符串起始锚点 | 确保从头匹配 | | [+-]? | Optional sign | 可选正负号 | {+, -, ε} | | [0-9]* | Any number of digits | 任意长度数字序列 | ℕ* | | [02468]$ | Even digit at end | 末位偶数数字 | x ≡ 0 mod 2 | | $ | End of string | 字符串结束锚点 | 禁止后缀 |

3. Edge Case Handling 边界情况处理 (1) 零的处理 

1
2
0       → 匹配（数学定义中0是偶数）
00      → 匹配（虽非常规写法，但数值有效）

(2) 前导零问题 

1
01234   → 匹配末位4（但实际编程中可能需要禁止前导零）
改进版（禁止前导零）： 
1
^[+-]?(0|[1-9][0-9]*[02468])$

(3) 空字符串防护 

1
""      → 不匹配（因需要至少一个偶数位）

4. Mathematical Foundation 数学基础 (1) 偶数定义 

1
n ∈ ℤ 是偶数 ⇔ ∃k∈ℤ, n=2k
• 正则表达式通过末位数字实现该判定：

1
末位 ∈ {0,2,4,6,8} ⇒ n mod 2 = 0

(2) 形式语言理论 • 该模式描述的语言属于正则语言：

• 可用DFA（确定性有限自动机）识别

• DFA状态数：5个状态（符号→数字→偶数位）