资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

【编译原理】词法分析（编译器、转移图、正则表达式）

创作时间:

作者:

@小白创作中心

【编译原理】词法分析（编译器、转移图、正则表达式）

引用

CSDN

https://blog.csdn.net/ChenZHIHAO_y/article/details/141998893

词法分析是编译器前端的重要组成部分，它将源代码文本分解成一系列标记（tokens），这些标记代表了源代码中的各种语法元素，如关键字、标识符、常量、运算符等。本文将详细介绍词法分析的原理和实现方法，包括转移图的构造、正则表达式的应用以及有限状态自动机（FA）的原理。

编译器的阶段

编译器通常由多个阶段组成，其中词法分析是前端处理的第一个步骤。整个编译过程可以概括为：

源程序→前端→中间表示→后端→目标程序

前端

词法分析器的作用是将源代码的字符流转换为单词流。例如，对于以下代码片段：

if (x > 5)
    y = "hello";
else
    z = 1;

词法分析器会将其分解为以下词法单元：

IF - 关键词，表示条件语句的开始。
GT - 运算符，表示“大于”。
INT(5) - 整数常量，值为5。
RPAREN - 右括号，表示条件表达式的结束。
LPAREN - 左括号，表示条件表达式的开始。
IDENT(x) - 标识符，代表变量x。
SEMICOLON - 分号，表示语句的结束。
IDENT(y) - 标识符，代表变量y。
ASSIGN - 赋值运算符，用于将值赋给变量。
STRING("hello") - 字符串常量，值为"hello"。
ELSE - 关键词，表示条件语句的“否则”部分。
INT(1) - 整数常量，值为1。
IDENT(z) - 标识符，代表变量z。
ASSIGN - 赋值运算符，用于将值赋给变量。
SEMICOLON - 分号，表示语句的结束。
EOF - 文件结束标记，表示源代码的结束。

这些词法单元随后会被语法分析器使用，以构建抽象语法树（AST），这是源代码的树状结构表示，用于后续的编译或解释执行。

手工构造法

词法分析器通常采用手工编码的方式实现，通过定义状态机来识别和解析源代码中的各种语法元素。

转移图

转移图是一种有限状态机（FSM），用于识别和解析特定的语法元素。例如，以下转移图描述了一个用于识别关系运算符的FSM：

初始状态（start）：从初始状态开始，FSM读取第一个字符。
状态转移和动作：

当读取到 < 时，FSM进入一个新的状态，并再次读取下一个字符。
如果下一个字符是 =，则返回 LE（小于等于）。
如果下一个字符是 >，则返回 NE（不等于）。
如果读取到其他字符，则回退到上一个字符，并返回 LT（小于）。
当读取到 = 时，FSM再次读取下一个字符。
如果下一个字符是 =，则返回 EQ（等于）。
如果读取到其他字符，则回退到上一个字符，并返回 EQ（等于）。
当读取到 > 时，FSM进入一个新的状态，并再次读取下一个字符。
如果下一个字符是 =，则返回 GE（大于等于）。
如果读取到其他字符，则回退到上一个字符，并返回 GT（大于）。

状态转移图：转移图通过状态和转移边来描述FSM的行为。每个状态都有一个或多个转移边，这些转移边由输入字符触发。每个状态也可能有一个或多个动作，这些动作在转移时执行。
回退机制：当FSM在某个状态读取到一个不符合预期的字符时，它会回退到上一个字符，并返回相应的关系运算符。
动作：每个动作都返回一个关系运算符，如 LE、NE、LT、EQ、GE、GT。

伪代码解释：

token nextToken() {
    char c = getChar(); // 读取第一个字符
    switch(c) {
        case '<':
            c = getChar(); // 读取下一个字符
            switch(c) {
                case '=':
                    return LE; // 返回小于等于
                case '>':
                    return NE; // 返回不等于
                default:
                    rollback(); // 回退到上一个字符
                    return LT; // 返回小于
            }
        case '=':return EQ; // 返回等于
        case '>':
            c = getChar(); // 读取下一个字符
            if (c == '=') {
                return GE; // 返回大于等于
            } else {
                rollback(); // 回退到上一个字符
                return GT; // 返回大于
            }
        default:
            return other; // 处理其他字符
    }
}

标识符的转移图

这个FSM用于解析程序代码中的标识符，例如变量名、函数名等。标识符通常由字母、数字、下划线组成，且不能以数字开头。

初始状态：从初始状态开始，FSM读取第一个字符。
状态转移和动作：

当读取到一个字母（a-z或A-Z）或下划线（_）时，FSM进入一个新的状态，并继续读取下一个字符。
如果读取到其他字符，则返回标识符（ID）并结束解析。

循环读取：在新状态中，FSM继续读取字符，直到读取到的字符不再是字母、数字或下划线。这个过程是一个循环，直到遇到一个不符合条件的字符。
动作：当FSM读取到一个符合条件的字符序列后，它会返回一个标识符（ID）。

伪代码解释：

token nextToken() {
    char c = getChar(); // 读取第一个字符
    switch(c) {
        case 'a', 'b', ..., 'z', 'A', ..., 'Z', '_':
            c = getChar(); // 读取下一个字符
            while(c == 'a' || c == 'b' || ... || c == 'z' || c == 'A' || ... || c == 'Z' || c == '0' || ... || c == '9' || c == '_') {
                c = getChar(); // 继续读取下一个字符
            }
            return ID; // 返回标识符
        default:
            return other; // 处理其他字符
    }
}

关键字表算法

这个FSM用于解析程序代码中的关键字，关键字是编程语言中预定义的、具有特殊意义的标识符，如 “if”、“else”、“while” 等。

初始状态：从初始状态开始，FSM读取第一个字符。
状态转移和动作：

当读取到一个字母（a-z或A-Z）或下划线（_）时，FSM进入状态1。
在状态1，如果读取到的字符是i，则转移到状态2。
在状态2，如果读取到的字符是f，则转移到状态3。
在状态3，如果读取到的字符是字母、数字或下划线，则继续读取下一个字符，直到读取到一个非这些字符的字符。
如果在任何状态中读取到的字符不是预期的字符，FSM将返回到状态other并返回ID（标识符）。

结束状态：在状态3，如果读取到的字符不是字母、数字或下划线，FSM将确认已经读取到完整的关键字 “if” 并返回关键字。
动作：当FSM读取到一个符合条件的字符序列后，它会返回相应的关键字或标识符。

伪代码解释：

token nextToken() {
    char c = getChar(); // 读取第一个字符
    if (isLetter(c) || c == '_') {
        c = getChar(); // 读取下一个字符
        if (c == 'i') {
            c = getChar(); // 读取下一个字符
            if (c == 'f') {
                c = getChar(); // 继续读取下一个字符
                while (isLetter(c) || isDigit(c) || c == '_') {
                    c = getChar(); // 继续读取下一个字符
                }
                if (!isLetter(c) && !isDigit(c) && c != '_') {
                    return "if"; // 返回关键字 "if"
                }
            }
        }
    }
    return ID; // 返回标识符
}