C#词法分析器之转换DFA详解

什么是词法分析？

词法分析(Lexical Analysis)是编译器中的一个步骤，也称为扫描器(Scanner)。词法分析的主要任务是将程序中的代码转换成一个个Token（标记）。Token是指单词或符号等，是编译器中的最小单位。

词法分析器的输入是源代码，识别出其中的每个Token，每个Token包括 Token种类 和 Token值 两个部分。如：

int a = 1;

其中的Token可以分别识别为：

<keyword, int> <identifier, a> <assign, => <int_constant, 1> <semicolon, ;>

什么是DFA？

DFA（Deterministic Finite Automaton）即确定有限状态自动机，它是一种计算模型的抽象概念，可以识别输入的字符串是否符合所定义的规则。

DFA可以表示为一个五元组：

(D, Σ, δ, s, F)

其中：

• D：有限状态集合
• Σ：输入字符集合
• δ：转移函数，即从一个状态根据输入字符转移到下一个状态
• s：起始状态
• F：终止状态集合

根据输入字符，每次可以从一个状态转移到另一个状态，直至输入结束并到达终止状态，判断输入的字符串是否符合规则。

DFA在词法分析中的应用

DFA可以用于词法分析器中，识别出源代码中的各个Token。可以构建多个DFA来检查源代码中的关键字、标识符、数字、运算符、分隔符等Token，从而实现对源代码的Token解析。

以下是一个构建数字识别DFA的示例：

1. 首先，定义该DFA的五元组：

D = {S0, S1, S2, S3}
Σ = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '.', 'e'}
s = S0
F = {S1, S2, S3}

其中，D是状态的集合，Σ是输入符号的集合，s是初始状态，F是接受状态的集合。

1. 然后，定义状态和状态之间的转移函数：

δ(S0, '0') = S1
δ(S0, '1'-'9') = S2
δ(S1, '0'-'9') = S3
δ(S2, '0'-'9') = S2
δ(S2, '.') = S3
δ(S2, 'e') = S2
δ(S3, '0'-'9') = S3
δ(S3, 'e') = S2

1. 最后，根据该DFA，识别输入的字符串是否为数字。例如，对于输入 "3.14"，从状态S0开始，按照输入字符依次转移：

S0 -> S2 (input: 3)
S2 -> S3 (input: .)
S3 -> S2 (input: 1)
S2 -> S3 (input: 4)

最终到达S3状态，字符串 "3.14" 被识别为数字。

如何构建词法分析器

构建词法分析器，通常做法是：

1. 定义输入字符集合
2. 定义各种Token类型及其匹配的正则表达式
3. 构建DFA
4. 实现DFA的转移函数
5. 从起始状态开始，按照输入字符进行状态转移，直至到达终止状态，识别出Token，并返回Token的类型及值

参考 https://www.cnblogs.com/bjwu/p/9674199.html

示例1：识别关键字

假设我们要实现一个只能识别 if 和 else 关键字的词法分析器，具体步骤如下：

1. 定义输入字符集合：即所有的小写字母、数字、下划线
2. 定义关键字类型为 keyword
3. 定义 if 和 else 的正则表达式：(if)|(else)
4. 构建DFA：
5. 定义五元组：
   • D = {S0, S1, S2, S3, S4}
   • Σ = {a-z, 0-9, _}
   • s = S0
   • F = {S3, S4}
6. 定义状态之间的转移函数：
   • δ(S0, 'i') = S1
   • δ(S1, 'f') = S2
   • δ(S2, Σ) = S3（即到达终止状态 S3，识别出 if）
   • δ(S0, 'e') = S1
   • δ(S1, 'l') = S2
   • δ(S2, 's') = S4
   • δ(S4, 'e') = S3（即到达终止状态 S3，识别出 else）
   • 其他状态转移情况均指向 S0
7. 实现DFA的转移函数：如下示例代码

public Token GetNextToken()
{
    int state = 0;
    string lexeme = "";
    char c;

    while ((c = _sourceCode[_currentIndex++]) != '\0')
    {
        lexeme += c;

        switch (state)
        {
            case 0:
                if (c == 'i') state = 1;
                else if (c == 'e') state = 4;
                else return null;
                break;
            case 1:
                if (c == 'f') state = 2;
                else if (c == 'l') state = 3;
                else return null;
                break;
            case 2: // reach the end state
                if (c < 'a' || c > 'z' ) return new Token(TokenType.Keyword, "if");
                else return null;
            case 3:
                if (c == 's') state = 4;
                else return null;
                break;
            case 4: // reach the end state
                if (c < 'a' || c > 'z' ) return new Token(TokenType.Keyword, "else");
                else return null;
                break;
        }
    }

    return null;
}

示例2：识别数字

假设我们要实现一个只能识别整数和浮点数的词法分析器，具体步骤如下：

1. 定义输入字符集合：即所有数字字符
2. 定义数字类型为 numeric
3. 定义正则表达式：
4. 以数字开头的整数：[1-9][0-9]*
5. 以 0 开头的整数：0
6. 浮点数：[0-9]+(\.[0-9]+)?(e[+\-]?[0-9]+)?
7. 构建DFA：
8. 定义五元组：
   • D = {S0, S1, S2, S3, S4, S5, S6, S7}
   • Σ = {0-9}
   • s = S0
   • F = {S2, S3, S6}
9. 定义状态之间的转移函数：
   • δ(S0, '0') = S1
   • δ(S0, '1'-'9') = S2
   • δ(S1, Σ) = S5 （0 只能作为一位整数输入）
   • δ(S2, Σ) = S2
   • δ(S2, '.') = S3
   • δ(S2, 'e') = S6
   • δ(S5, Σ) = S5
   • δ(S3, Σ) = S4
   • δ(S4, Σ) = S4
   • δ(S4, 'e') = S6
   • δ(S6, '+'|'-'|Σ) = S7
   • δ(S7, Σ) = S7
10. 解释：
    • 初始状态(S0)读入 '0'，进入状态 S1
    • 初始状态(S0)读入 '1'~'9'， 进入状态 S2
    • 进入状态 S1，只能接受空输入，转移到状态 S5
    • 进入状态 S2，接受数字字符，作为整数部分，继续保持状态 S2
    • 进入状态 S2，第一次读入 '.'，进入状态 S3，开始读取小数部分
    • 进入状态 S3，继续接受数字字符，进入状态 S4
    • 进入状态 S4，继续接受数字字符，维持状态 S4
    • 进入状态 S4，遇到字符 'e' 进入状态 S6，开始读取指数部分
    • 进入状态 S5，只能接受空输入，输出整数结果
    • 进入状态 S6，读入符号或数字，进入状态 S7 进行判断
    • 进入状态 S7，需要接收数字字符输入，进行指数部分的匹配和判断
11. 实现DFA的转移函数：如下示例代码

public Token GetNextToken()
{
    int state = 0;
    string lexeme = "";
    char c;

    while ((c = _sourceCode[_currentIndex]) != '\0')
    {
        lexeme += c;
        _currentIndex++;

        switch (state)
        {
            case 0:
                if (c == '0') state = 1;
                else if (c >= '1' && c <= '9') state = 2;
                else return null;
                break;
            case 1:
                if (c >= '0' && c <= '9') return null;
                else return new Token(TokenType.Number, lexeme);
            case 2:
                if (c >= '0' && c <= '9') state = 2;
                else if (c == '.') state = 3;
                else if (c == 'e') state = 6;
                else return new Token(TokenType.Number, lexeme);
                break;
            case 3:
                if (c >= '0' && c <= '9') state = 4;
                else return null;
                break;
            case 4:
                if (c >= '0' && c <= '9') state = 4;
                else if (c == 'e') state = 6;
                else return new Token(TokenType.Number, lexeme);
                break;
            case 5:
                return new Token(TokenType.Number, lexeme);
            case 6:
                if (c == '+' || c == '-') state = 7;
                else if (c >= '0' && c <= '9') state = 8;
                else return null;
                break;
            case 7:
                if (c >= '0' && c <= '9') state = 8;
                else return null;
                break;
            case 8:
                if (c >= '0' && c <= '9') state = 8;
                else return new Token(TokenType.Number, lexeme);
                break;
        }
    }

    return null;
}

以上是构建C#词法分析器中转换DFA的详细攻略，希望能对大家有所帮助。