- 词法分析器的构造步骤
词法分析器是编译程序的基础模块，其构造逻辑基于正规式与有限自动机理论，具体构造步骤如下：
- 第一步：使用正规式描述语言的单词构成规则
针对目标语言中的各类单词（如标识符、关键字、常数、运算符等），用正规式精确描述其结构模式。例如，标识符可表示为[a-zA-Z][a-zA-Z0-9]*。 - 第二步：为每个正规式构造非确定有限自动机（NFA）
利用汤普森构造法（Thompson’s Construction），将每个正规式转换为对应的 NFA，该自动机能够识别由该正规式定义的语言。 - 第三步：将 NFA 转换为等价的确定有限自动机（DFA）
使用子集构造法（Subset Construction），将 NFA 确定化为 DFA，消除非确定性，使得每一步状态转移唯一。 - 第四步：对 DFA 进行最小化处理
合并等价状态，减少状态数量，得到一个状态最少的等价 DFA，提升运行效率。 - 第五步：基于最小化 DFA 构建词法分析器
将最终的 DFA 编码实现为程序模块，输入字符流，输出识别出的单词符号（token），供后续语法分析使用。
- 语法分析的核心内容
语法分析的任务是根据语法规则验证词法单元（token）序列是否构成合法的程序结构，并在发现不符时报告语法错误。其核心内容包括：
- 上下文无关文法（CFG）
形式定义为 G = (V_N, V_T, P, S)，其中 V_N 是非终结符集合，V_T 是终结符集合，P 是产生式规则集合，S 是开始符号。它是描述大多数编程语言语法结构的基础工具。 - 规范推导（最右推导）
在推导过程中，每次选择句型中最右边的非终结符进行替换，这种推导方式称为规范推导，是自底向上语法分析（如LR分析）的理论基础。 - 短语、直接短语与句柄
- 短语：在一个句型中，若某个子串是由某一非终结符通过若干步推导得到的，则该子串称为该非终结符的一个“短语”。
- 直接短语：若某子串是由某一非终结符通过一步推导得到的，则称为“直接短语”。
- 句柄：一个句型的最左直接短语称为句柄，是自底向上语法分析中归约操作的对象，代表当前应归约的部分。
![]()
