Lexical Analysis
o To introduce the concept and function of a compiler
o LA
o ‘token’
o To introduce the procedure of scanning
o Design of LA program
Lexical Analysis (LA)
Lexical Analysis (LA) 是编译器中的第一个阶段，其主要任务是将源代码分解成有意义的“token”（词法单元）。以下是详细的解读内容：
1. 编译器的概念和功能
编译器的核心功能是将源代码（source code）转换成目标代码（target code），这是一个多阶段的过程。
• 编译器的各阶段：
• Lexical Analysis (词法分析)
• Syntax Analysis (语法分析)
• Semantic Analysis (语义分析)
• Intermediate Code Generation (中间代码生成)
• Optimization (优化)
• Code Generation (目标代码生成)
在这些阶段中，词法分析是第一个步骤，负责将输入的源代码拆分为token，这些 token 是编译器后续阶段的基础。
2. 什么是 Lexical Analysis？
• Lexical Analysis 是编译器的前端部分，也称为词法分析或扫描器（Scanner）。
• 它的主要任务是扫描源代码的输入字符流，并将其分解成一系列有意义的“token”。
• Token 是源代码的最小单位，代表语言中的语法元素，例如关键词、标识符、常量、运算符等。
3. 什么是 Token？
Token 是 Lexical Analysis 的输出，是源代码中的逻辑单元。Token 包括两个部分：
Token 类别（class）：表示这个单元的类型，例如关键字、标识符、常量、操作符等。
属性值（attribute）：进一步描述 token 的具体值，例如 int 是一个关键词，而 count 是一个标识符。
示例：
int count = 5;
Token 流：
• INT_TOKEN (类别: 关键字，值: “int”)
• IDENTIFIER_TOKEN (类别: 标识符，值: “count”)
• ASSIGNMENT_TOKEN (类别: 运算符，值: “=”)
• NUMERIC_TOKEN (类别: 常量，值: “5”)
• SEMICOLON_TOKEN (类别: 符号，值: “;”)
4. 词法分析的过程
词法分析的核心过程是扫描（scanning），它按照字符流进行处理，完成以下任务：
读取输入字符流：从左到右扫描源代码，逐个字符读取。
跳过无关字符：忽略空格、换行符和注释等不影响语法分析的字符。
识别 token：根据正则表达式或词法规则，提取关键字、标识符、数字、字符串等。
返回 token：将 token 传递给语法分析器（Syntax Analyzer）。
5. 设计 LA 程序
设计 Lexical Analyzer 的过程包括以下几个步骤：
- 定义 Token 类别：识别语言中所有可能的 token 类别，例如：
• 关键字 (if, for, while 等)
• 标识符 (变量名、函数名等)
• 常量 (数字、字符串等)
• 运算符 (+, -, *, / 等)
• 分隔符 (, ; 等)
- 编写扫描逻辑：
• 使用有限状态机 (FSM, Finite State Machine) 来识别各类 token。
• 逐字符读取，进入不同的状态以匹配 token 的类型。
- 预处理输入：
• 跳过空格、换行符和注释等无用字符。
• 缓冲输入，提高扫描效率。
- 存储 Token：
• 每个 token 都保存为一条记录，包含类型和值。
• 可以使用结构体（如 TokenRecord）存储这些信息。
示例代码 (C 语言)：
typedef struct { TokenType tokenval; // Token 类型 char *stringval; // 字符串值 int numval; // 数字值 } TokenRecord;6. 为什么需要单独的 Lexical Analysis 阶段？
- 简化编译器设计：
• 将词法分析与语法分析分离，简化了语法分析器的任务。
- 提高效率：
• 使用正则表达式和有限状态机，词法分析可以高效地提取 token。
- 预处理输入：
• 忽略空格、注释等非必要字符，有助于后续阶段的处理。
- 模块化设计：
• LA 可以独立测试和优化，增强了编译器的可维护性。
总结
Lexical Analysis 是编译器前端的重要步骤，它负责将源代码转换成token 流，为后续的语法分析提供输入。其核心工作包括：
• 扫描源代码，跳过无关字符。
• 识别 token，并按类别和属性进行分类。
• 输出 token 流，传递给语法分析器进行进一步处理。
通过正则表达式和有限状态机，我们可以高效地实现词法分析器，同时保证编译器的模块化和可扩展性。
Procedures of a Compiler
Procedures of a Compiler
该图展示了编译器的主要阶段，包括从源代码到目标代码的整个转换过程。编译器通过一系列有序的步骤将源代码（Source Code）转换成高效的目标代码（Target Code），并且在过程中进行错误检测和优化。
1. Scanner (Lexical Analyzer)
• 功能：
• 词法分析阶段，扫描源代码输入，逐个字符处理，识别出token（词法单元）。
• 忽略空格、注释等无关字符。
• 输入：
• 源代码字符串。
• 输出：
• Token 流：例如，关键字、标识符、常量、操作符等。
• 相关表格：
• Literal Table：存储字面量常量，如字符串常量、数字等。
• Symbol Table：存储标识符（如变量名、函数名）的信息。
2. Parser (Syntax Analyzer)
• 功能：
• 语法分析阶段，检查 token 流是否符合语言的语法规则。
• 生成语法树（Syntax Tree）来表示程序的结构。
• 输入：
• Token 流（来自 Scanner）。
• 输出：
• 语法树：描述程序的结构和语法关系。
• 错误处理：
• 检测语法错误，并将错误信息传递到Error Handler。
3. Semantics Analyzer
• 功能：
• 语义分析阶段，检查程序的逻辑和语义是否正确。
The Function of LA (scanner)
o Task of analysing
o Read source code from left to right, generate ‘token’
o Input source code output ‘token’
o Lexical Analyser
o Also called ‘Scanner’
o A program that execute lexical analysing
The Function of LA (Lexical Analyzer or Scanner)
The Function of a Compiler
●Takes a source program in a source language
●Translates it into an equivalent target program in a target language
●Provides error messages