编译原理(3)词法分析基本概念

词法分析（Lexical Analysis）是编译过程的第一个核心阶段，又称 “扫描”（Scanning）。其本质是将源程序中无结构的字符流，按编程语言规则转换为结构化的 “词法单元”，同时过滤无用信息、检查字符级错误，为后续语法分析提供标准化输入。理解其基本概念是掌握编译原理的起点。词法分析涉及 4 个核心术语，它们共同描述了 “字符流如何变成词法单元” 的过程：词法分析的所有操作都围绕以下 3

陌路20

872人浏览 · 2025-11-04 15:56:17

陌路20 · 2025-11-04 15:56:17 发布

词法分析基本概念：编译的 “字符→单词” 转换基础

词法分析（Lexical Analysis）是编译过程的第一个核心阶段，又称 “扫描”（Scanning）。其本质是将源程序中无结构的字符流，按编程语言规则转换为结构化的 “词法单元”，同时过滤无用信息、检查字符级错误，为后续语法分析提供标准化输入。理解其基本概念是掌握编译原理的起点。

核心术语：理解词法分析的基础定义

词法分析涉及 4 个核心术语，它们共同描述了 “字符流如何变成词法单元” 的过程：

术语	定义	示例（以`int num = 5 + 3;`为例）
字符流（Character Stream）	源程序的原始形态，由连续字符组成（包括字母、数字、符号、空格、换行等）	`['i','n','t',' ','n','u','m',' ','=',' ','5',' ','+',' ','3',';']`
词法单元（Token）	语言中 “最小的、不可再分的语义单位”（相当于自然语言的 “单词”），是词法分析的输出	`(关键字int)、(标识符num)、(赋值符=)、(整数5)、(加号+)、(整数3)、(分号;)`
模式（Pattern）	每个 Token 对应的 “字符构成规则”，描述 Token 的合法字符序列（相当于 “单词的拼写规则”）	标识符的模式：“字母 / 下划线开头，后跟字母 / 数字 / 下划线”；整数的模式：“1 个或多个数字”
词素（Lexeme）	Token 对应的具体字符序列（源程序中的 “字面量”），是 Token 的实例	Token`(标识符)`对应的词素是`"num"`，Token`(整数)`对应的词素是`"5"`

词法分析的 3 个核心目标

词法分析的所有操作都围绕以下 3 个目标展开，最终为编译后续阶段扫清字符级障碍：

1.结构化转换：字符流→Token 流按语言规则拆分连续的字符流，生成有明确语义的 Token 序列。例如将intnum=5+3;拆为int（关键字）、num（标识符）、=（赋值符）、5（整数）、+（加号）、3（整数）、;（分号），让后续语法分析无需关注字符细节，只需处理 “单词” 级别的逻辑。

2.信息提取与过滤

提取 Token 属性：对有具体语义的 Token（如整数、标识符），记录附加信息（如5的数值、num的变量名），供语义分析、代码生成使用。

过滤无用字符：移除不影响程序语义的字符，包括空格、制表符（\t）、换行（\n）、注释（// 单行注释、/* 多行注释 */），减少后续阶段的干扰。

3.字符级错误检查识别语言字符集外的非法字符（如 C 语言中出现@、￥），或不符合 Token 模式的字符序列（如123a，数字后接字母），输出清晰的错误信息（如 “行 2：非法字符 '@'”“行 3：非法常量 '123a'”），帮助开发者定位问题。

常见 Token 类型：语言的 “基础词汇表”

不同编程语言的 Token 类型略有差异，但核心分类一致，以下是适用于 C、Java、Python 等主流语言的通用类型，覆盖 90% 以上场景：

Token 类型	说明（语义 / 作用）	典型示例词素	对应 Token（类型 + 属性）
关键字（Keyword）	语言预留的特殊 Token，有固定语义（不可作为用户标识符）	int、if、for、return、class	(KEYWORD_INT, 无)、(KEYWORD_IF, 无)
标识符（ID）	用户自定义的名称（用于命名变量、函数、类等）	num、sum、userName、func123	(ID, "num")、(ID, "userName")
常量（Constant）	固定值（数值、字符、字符串、布尔值等）	5、3.14、'A'、"hello"、true	(NUM_INT, 5)、(STR, "hello")、(BOOL, true)
运算符（Operator）	实现运算或逻辑判断的符号（算术、关系、逻辑、赋值等）	+、*、==、&&、=、!	(PLUS, "+")、(EQ, "==")、(ASSIGN, "=")
分隔符（Separator）	用于分隔语句、表达式、参数的符号	;、,、()、{}、[]、.	(SEMICOLON, ";")、(LPAREN, "(")、(DOT, ".")

关键提醒：关键字与标识符的区别 —— 关键字是 “编译器预定义的固定词汇”（如int），标识符是 “用户自定义的名称”（如num），词法分析需优先识别关键字（避免将int误判为标识符）。

核心实现思想：有限状态自动机（FSM）

词法分析的底层逻辑依赖有限状态自动机（Finite State Machine, FSM），这是一种按 “状态转移” 规则识别字符序列的数学模型，其中确定有限状态自动机（DFA） 因 “无歧义、执行高效” 成为工业级实现的首选。

DFA 的核心逻辑

DFA 将 Token 的识别过程抽象为 “状态转移”：

状态：包括初始状态（等待识别新 Token）、中间状态（已读取部分字符，正在匹配 Token）、终止状态（已识别完整 Token）、出错状态（字符无法匹配任何 Token 模式）。

转移：根据当前状态和输入字符，转移到下一个状态（如在 “初始状态” 读取字母，转移到 “标识符中间状态”）。

示例：标识符（ID）的 DFA 识别流程

以 “标识符模式：字母 / 下划线开头，后跟字母 / 数字 / 下划线” 为例，DFA 状态转移如下：

当前状态	输入字符类型	转移后状态	说明（识别进度）
S0（初始状态）	字母 / 下划线（如`n`）	S1（中间状态）	启动标识符匹配，记录首字符
S0（初始状态）	数字 / 非法字符（如`5`、`@`）	出错状态	标识符不能以数字 / 非法字符开头
S1（中间状态）	字母 / 数字 / 下划线（如`u`、`3`）	S1（中间状态）	继续匹配后续字符
S1（中间状态）	分隔符 / 运算符（如`=`、`;`）	S2（终止状态）	识别完整标识符，生成 Token
S2（终止状态）	-	回到 S0	输出当前 Token，准备识别下一个

实际执行：读取n（S0→S1）→ 读取u（S1→S1）→ 读取m（S1→S1）→ 读取=（S1→S2）→ 生成 Token(ID, "num")，回到 S0 处理=。

词法分析的地位：编译流程的 “第一块基石”

词法分析是编译的 “入口阶段”，其输出（Token 流）是后续所有阶段的输入，直接影响编译的正确性：

衔接语法分析：语法分析接收 Token 流，验证 Token 的排列是否符合语法规则（如int num = 5 + ;中+后缺少操作数，语法分析报错）。
衔接语义分析：语义分析使用 Token 的属性（如num的变量名、5的数值），检查类型匹配（如int num = 3.14;类型不匹配）。
简化后续阶段：将无结构的字符流转换为结构化 Token 流，让语法分析、语义分析无需处理字符级细节（如空格、注释），专注于更高层次的逻辑。

总结

词法分析的基本概念围绕 “字符流→Token 流” 的转换展开，核心是理解 4 个术语（字符流、Token、模式、词素）、3 个目标（结构化转换、信息处理、错误检查）、常见 Token 类型及 DFA 实现思想。它是编译器 “读懂” 代码的第一步，也是后续语法分析、语义分析等阶段的基础，没有准确的词法分析，整个编译流程将无法正确推进。