编译技术2-1

Lexical Analysis: The Scanning Process (词法分析：扫描过程)

1. 核心概念 (Core Concepts) (1) Lexeme (词素) • 定义：源代码中构成token的原始字符序列

• 示例：在while (1377 < i)中：

• "while" → 词素

• "1377" → 词素

• 图示对应：图2中绿色高亮的while和其下方蓝色框T_While的关系

(2) Token (词法单元) • 定义：对词素分类后的抽象表示

• 性质：

• 可视为枚举类型

• 包含逻辑类别信息（如关键字/标识符/运算符）

• 示例：

1
2
// 词素 "while" → Token类型 T_While
// 词素 "1377" → Token类型 T_IntLiteral

(3) Pattern Matching (模式匹配) • 本质：扫描是模式匹配的特例（图1底部文字）

• 过程：将输入流按预定规则切分

• 图1示例："This is a sentence." → 拆分为单词和标点

2. 扫描过程详解 (Scanning Process) (1) 基本流程 1. 读取字符流： • 图3展示的代码字符序列：while ( 1 3 7 < i )\n\t++i ;

  1. 识别词素： • 识别到while时生成T_While

  2. 丢弃无关内容： • 忽略空白符

  3. 属性存储逻辑

    • 关键字/运算符：通常只需类型（如T_While）

      字面量/标识符(需要存储属性)

      • 数字 → 存储解析后的数值
      • 字符串 → 存储字符串指针
      • 标识符 → 指向符号表条目

(2) 关键操作 | 操作 | 说明 | 图示对应 | |------|------|----------| | 词素提取 | 从源代码截取有效片段 | 图1紫色框标注单词 | | Token生成 | 将词素映射为逻辑类型 | 图2的while→T_While | | 空白符处理 | 跳过空格/换行符等 | 图3右侧说明文本 |

3. 关键总结 (Key Takeaways)

  1. 词素是原始文本，token是抽象分类
    "Lexemes are concrete, tokens are abstract"

  2. 扫描过程需兼顾提取与丢弃：
    • 提取有效词素（图1）

    • 丢弃无关字符（图3）

"词法分析是将混沌的字符流转化为结构化token流的第一步"
"Lexical analysis transforms chaotic character streams into structured token sequences"

Lexical Analysis Goals and Process 词法分析目标与流程详解

1. Core Goals of Lexical Analysis 词法分析核心目标 (1) Primary Conversion 主要转换 • Physical → Logical Representation

将程序的物理描述（字符流）转换为逻辑标记序列
Convert from character streams to token sequences

(2) Token Definition 标记定义

属性 说明 示例
Logical Type
逻辑类型		 关键字/标识符等分类 T_While, T_Identifier
Lexeme
词素		 原始文本片段 "while", "137"
Attributes
附加属性		 从文本提取的扩展信息 数值137的类型为int

2. Token Specification 标记规范 (1) Pattern Rules 模式规则

1
2
3
4
# 典型标记模式定义
keyword     : 'while' | 'if' | 'else'
identifier  : [a-zA-Z_][a-zA-Z0-9_]*
number      : [0-9]+ ('.' [0-9]+)?

(2) Attribute Handling 属性处理 

1
2
3
4
5
6
7
8
9
// Token数据结构示例
struct Token {
    TokenType type;  // 标记类型枚举
    union {
        int num_val;    // 数值属性
        char* str_val;  // 字符串属性
        // 其他自定义属性
    } attr;
};

3. System Workflow 系统工作流 (1) Component Interaction 组件交互 
sequenceDiagram
    Source Code->>Scanner: 字符流输入
    Scanner->>Symbol Table: 查询/存储标识符
    Scanner->>Parser: currentToken
    Parser->>Scanner: getNextToken()

(2) Key Operations 关键操作 1. Scanner 扫描器
• 调用getNextToken()逐词读取

• 处理空白符/注释（不生成token）

  1. Symbol Table 符号表
    • 维护标识符的唯一性

    • 存储类型等语义信息

  2. Parser 解析器
    • 通过currentToken恢复语法结构

    • 触发下一token请求

4. Implementation Example 实现示例 (1) Token Generation 标记生成

1
2
3
4
5
6
7
8
9
10
11
# 伪代码示例
def scan(source):
    tokens = []
    while pos < len(source):
        if source[pos].isdigit():
            num, pos = parse_number(source, pos)
            tokens.append(Token('NUMBER', num))
        elif source[pos].isalpha():
            id, pos = parse_identifier(source, pos)
            tokens.append(Token('ID', id))
    return tokens

(2) Attribute Extraction 属性提取 

1
2
3
4
5
6
// 处理数字字面量
Token processNumber(String lexeme) {
    int value = Integer.parseInt(lexeme);
    return new Token("NUMBER", 
           new NumberAttr(value, "int"));
}

5. Parser Integration 解析器集成 Syntax Recovery 语法恢复 

1
2
3
/* 使用token流重建语法结构 */
while_stmt : T_While '(' expr ')' stmt
expr       : T_Identifier | T_Number

Error Handling 错误处理 • 遇到非法token时立即报错

"Invalid token '12ab' at line 5"

6. Key Takeaways 核心结论

  1. 词法分析是编译器的前端过滤器
    Lexical analysis acts as the compiler's front-end filter

  2. 标记化使语法分析更高效
    Tokenization enables efficient parsing

  3. 属性携带关键语义信息
    Attributes carry vital semantic meaning

Choosing Tokens in Lexical Analysis 词法分析中的标记选择

1. Token Selection Principles 标记选择原则 (1) Language Dependency 语言依赖性 • 完全取决于目标语言设计

Highly dependent on the specific programming language

(2) Typical Strategies 典型策略 | 策略 | 说明 | 示例 | |------|------|------| | 关键字独立标记 | 每个关键字对应唯一token | for, int → 单独标记 | | 标点符号独立 | 每个运算符/分隔符独立标记 | <<, ++, [ | | 分类归组 | 同类词素归为一组 | 所有标识符 → T_Identifier | | 信息过滤 | 忽略无关内容 | 空格/注释不生成标记 |

2. Case Study: C++代码分析 (1) 示例代码 

1
2
3
for (int k = 0; k < myArray[5]; ++k) {
    cout << k << endl;
}

(2) 推荐标记方案 | 源代码 | 标记类型 | 分类依据 | |--------|----------|----------| | for | T_For | 关键字独立 | | int | T_Int | 关键字独立 | | k, myArray, cout, endl | T_Identifier | 标识符归组 | | 0, 5 | T_IntConstant | 常量归组 | | <<, ++, =, < | T_Operator | 运算符独立/分组 | | ;, {, }, (, ), [, ] | 各自独立标记 | 分隔符独立 |

3. Implementation Considerations 实现考量 (1) 标记类型枚举设计 

1
2
3
4
5
6
7
8
9
10
typedef enum {
    // 关键字
    T_For, T_Int, 
    // 运算符
    T_Assign, T_LessThan, T_ShiftLeft,
    // 分隔符
    T_Semicolon, T_LeftBrace,
    // 通用类型
    T_Identifier, T_IntConstant
} TokenType;

(2) 词法规则示例 (正则表达式) 

1
2
3
4
5
6
7
8
9
%%
"for"       { return T_For; }
"int"       { return T_Int; }
[a-zA-Z_]\w* { return T_Identifier; }
[0-9]+      { return T_IntConstant; }
"<<"        { return T_ShiftLeft; }
";"         { return T_Semicolon; }
[ \t\n]     ; // 忽略空白符
%%

4. Advanced Techniques 高级技巧 (1) 上下文相关标记 • C++案例：>>可能是运算符或模板闭合符

需结合语法上下文判断

(2) 标记属性扩展

1
2
3
4
5
6
7
8
struct Token {
    TokenType type;
    union {
        char* id_name;  // 标识符名称
        int int_val;    // 整数值
    } attr;
    SourceLocation loc; // 源代码位置
};

5. Anti-Patterns to Avoid 应避免的反模式

  1. 过度细分标记
    如为每个标识符创建独立标记类型
  2. 忽略重要分隔符
    如不区分(和{
  3. 保留无用空白符
    导致解析器复杂度增加

6. 教学示例解析 问题：为何<<应作为独立标记？ • 技术原因：

C++中<<是独立运算符（流输出/位移）
不同于两个单独的<字符 • 实现影响：

避免语法分析时的歧义

7. Key Takeaways 核心结论 1. 标记设计直接影响解析器复杂度
Token design directly affects parser complexity 2. 平衡粒度与效率
Balance between granularity and efficiency 3. 语言语义决定标记策略
Language semantics dictate tokenization

"好的标记设计如同精心设计的字母表，是构建编译器语言的基础"
"Good token design is like a well-crafted alphabet - foundational for compiler languages"

Challenges in Lexical Analysis 词法分析的挑战

1. Historical Context: FORTRAN Case 历史案例：FORTRAN空格问题 (1) 经典歧义示例 

1
2
DO 5 I = 1.25    ! 1. 循环语句 (DO-loop)
DO5I = 1.25      ! 2. 赋值语句 (Assignment)
• 关键问题：FORTRAN中空格无意义

Whitespace is irrelevant in FORTRAN

(2) 技术解析 | 输入文本 | 可能解释 | 判定依据 | |----------|----------|----------| | DO 5 I = 1.25 | DO循环 | 数字5作为标签 | | DO5I = 1.25 | 赋值语句 | DO5I作为变量名 |

(3) 现代启示 • 教训：语言设计应明确分隔符规则

Modern languages enforce clear delimiters

2. C++ Template Syntax Ambiguity C++模板语法歧义 (1) 典型问题 

1
2
vector<vector<int>> myVector;  // 合法C++11+
vector<vector<int>> myVector;   // 旧标准中解析为位移运算符>>

(2) 歧义分解 

1
2
3
4
// 词法分析可能错误拆分：
vector < vector < int >> myVector
// 等价于：
vector < (vector < (int >> myVector))

(3) 解决方案 • C++11标准：引入新的解析规则

>>在模板上下文自动识别为闭合符 • 词法技巧：

1
">>"    { return yylval.angle_count >= 2 ? T_TemplateClose : T_ShiftRight; }

3. Core Challenges 核心挑战 (1) 词素边界判定 • 问题本质：

How to partition character streams without semantic context?
如何在缺乏语义上下文时划分字符流？

(2) 冲突解决策略 | 策略 | 适用场景 | 示例 | |------|----------|------| | 最长匹配 | 大多数语言 | ++优先于两个+ | | 上下文相关 | C++模板 | >>的两种解释 | | 语法反馈 | FORTRAN | 需要解析器协同 |

(3) 效率优化 • 预扫描缓存：

1
2
3
// 预读多个字符辅助决策
char* lookahead = peek_next_n_chars(3);
if (strncmp(lookahead, ">>", 2) == 0) {...}
• 状态机设计：

DFA状态机设计
通过DFA状态分支处理不同词素模式

4. Solution Patterns 解决方案模式 (1) 分层处理架构 
graph LR
    A[字符流] --> B(词法分析器)
    B -->|Token流| C[解析器]
    C -->|上下文反馈| B

(2) 典型算法 • Maximal Munch (最大吞并)：

1
2
3
4
5
6
def next_token():
    longest_match = ""
    for pattern in all_patterns:
        if input.startswith(pattern) and len(pattern) > len(longest_match):
            longest_match = pattern
    return longest_match

(3) 语言设计建议 • 强制分隔符：Python的缩进规则

• 保留字保护：禁止int = 10（int作为变量名）

• 明确优先级：正则规则的编写顺序

5. Key Takeaways 核心结论 1. 历史教训：FORTRAN的空格问题显示明确分隔符的重要性
Historical cases show delimiter significance

  1. 现代挑战：C++模板等特性需要上下文感知的词法分析
    Modern syntax requires contextual awareness

  2. 解决之道：通过最长匹配+语法反馈平衡准确性与效率
    Balance accuracy/efficiency with max-munch and parser feedback

"词法分析如同破解密码，既需要模式识别的精确，也要理解书写者的意图"
"Lexical analysis is like deciphering codes - requiring both pattern precision and intention understanding"