构建一个 Human Resource Machine 编译器 - 词法分析

(Thanks to Doubao for translating. See original at this page. 感谢豆包的翻译, 原文见此页面。如有差异，请以英文版为准。如果中文使你困惑看不懂，也请读英文版。)

这是Human Resource Machine 编译器系列的一篇文章。

逐字解析原始程序几乎是不可能的。你很快就会发现自己在难以预测且多样的标识符名称中挣扎，并且处理字符串可能效率低下。这就是词法分析的概念自然发挥作用的地方。

在词法分析过程中，程序被转换为标记。关键字是简单的标记，但其他标记可能携带元数据，例如整数值或变量名。词法分析器是编译器的第一个组成部分。

将语言转换为标记相当简单。对于像这样的语言，一个人可以只用一杯咖啡的时间就写出一个词法分析器。

一个简单的手写词法分析器

一个简单的方法是直接扫描文本。对于像“>”这样的运算符，如果下一个字符不是另一个可组合的运算符，它可以立即被映射为一个标记。如果是，在将它们映射为标记之前，匹配会扩展到下一个字符。对于关键字，如果整个单词匹配，它就会被转换为一个标记。只包含数字的数字显然是整数标记。括号也很容易标记化。注释和空格直接被跳过。由于我们的语言不包括字符串，这个过程变得更加容易。

回顾我们的语言

import lang_mod;

// only single line comments allowed
init floor[1] = 1; // init floor[id] sets the initial value for a box on the floor
init floor[0] = 0;
init floor_max = 10;

// A function is defined, which takes an argument. 
// Only one or zero argument is allowed.
function countdown(a) {
    for (let i = a, i >= 0, --i) {
        if (a % 2 == 0) {
            continue;
        }
        outbox(i);
    }

    return a;
}

// sub marks a no-return function
sub no_return_func() {
    // and it does nothing
}

// the program starts here
sub start() {
    // a loop construct
    // int(true) = 1, int(false) = 0, boolean and int are basically the same thing
    // bool(1) = true, bool(0) = false, bool(anything except 0) = true
    while (true) {
        // inbox and outbox
        let a = inbox();
        let b = inbox();
        if (a > b) {
            outbox(a);
        } else {
            outbox(b);
        }
        let c = a * b;
        let num = countdown(a);
        floor[2] = num;
        floor[3] = floor[b] + c;
        outbox(c);
    }
}

让我们来实现这个简单的词法分析器。

from enum import Enum, auto

# Define token types
class TokenType(Enum):
    IMPORT = auto()
    IDENTIFIER = auto()
    NUMBER = auto()
    ASSIGN = auto()
    SEMICOLON = auto()
    COMMA = auto()
    LPAREN = auto()
    RPAREN = auto()
    LBRACKET = auto()
    RBRACKET = auto()
    LBRACE = auto()
    RBRACE = auto()
    FUNCTION = auto()
    SUB = auto()
    FOR = auto()
    WHILE = auto()
    IF = auto()
    ELSE = auto()
    RETURN = auto()
    LET = auto()
    OPERATOR = auto()
    INIT = auto()
    FLOOR = auto()
    FLOOR_MAX = auto()
    END_OF_INPUT = auto()

# Define keywords
keywords = {
    "import": TokenType.IMPORT,
    "function": TokenType.FUNCTION,
    "sub": TokenType.SUB,
    "for": TokenType.FOR,
    "while": TokenType.WHILE,
    "if": TokenType.IF,
    "else": TokenType.ELSE,
    "return": TokenType.RETURN,
    "let": TokenType.LET,
    "init": TokenType.INIT,
    "floor": TokenType.FLOOR,
    "floor_max": TokenType.FLOOR_MAX
}

# Operator characters and combinations
operators = {'+', '-', '*', '/', '>', '<', '=', '!', '++', '--', '>=', '<=', '==', '!=', '&&', '||'}

def is_operator(char):
    return char in '+-*/><=!'

def is_whitespace(char):
    return char in ' \t\n\r'

def is_digit(char):
    return '0' <= char <= '9'

def is_identifier_start(char):
    return char.isalpha() or char == '_'

def is_identifier_part(char):
    return char.isalnum() or char == '_'

def scanner(code):
    tokens = []
    i = 0
    length = len(code)

    while i < length:
        char = code[i]

        # Skip whitespace
        if is_whitespace(char):
            i += 1
            continue

        # Handle comments
        if char == '/' and i + 1 < length and code[i + 1] == '/':
            while i < length and code[i] != '\n':
                i += 1
            continue

        # Handle numbers
        if is_digit(char):
            start = i
            while i < length and is_digit(code[i]):
                i += 1
            tokens.append((TokenType.NUMBER, int(code[start:i])))
            continue

        # Handle identifiers and keywords
        if is_identifier_start(char):
            start = i
            while i < length and is_identifier_part(code[i]):
                i += 1
            word = code[start:i]
            token_type = keywords.get(word, TokenType.IDENTIFIER)
            tokens.append((token_type, word))
            continue

        # Handle operators
        if is_operator(char):
            if i + 1 < length and is_operator(code[i + 1]):
                two_char_operator = char + code[i + 1]
                if two_char_operator in operators:
                    tokens.append((TokenType.OPERATOR, two_char_operator))
                    i += 2
                    continue
            tokens.append((TokenType.OPERATOR, char))
            i += 1
            continue

        # Handle brackets and punctuation
        if char == '(':
            tokens.append((TokenType.LPAREN, char))
        elif char == ')':
            tokens.append((TokenType.RPAREN, char))
        elif char == '{':
            tokens.append((TokenType.LBRACE, char))
        elif char == '}':
            tokens.append((TokenType.RBRACE, char))
        elif char == '[':
            tokens.append((TokenType.LBRACKET, char))
        elif char == ']':
            tokens.append((TokenType.RBRACKET, char))
        elif char == ',':
            tokens.append((TokenType.COMMA, char))
        elif char == ';':
            tokens.append((TokenType.SEMICOLON, char))
        elif char == '=':
            tokens.append((TokenType.ASSIGN, char))

        i += 1

    tokens.append((TokenType.END_OF_INPUT, ''))
    return tokens

你也可以在这里找到代码。

更好的方法……？

在检查匹配过程时，你会注意到一个字符可能会针对潜在的标记化被多次评估。为了优化这个过程，我们可以构建一个状态转换表，当遇到不匹配的字符时，直接跳转到下一个有效的标记。例如，如果我们有一个名为“floor1”的标识符，并且我们知道“floor”是一个关键字，我们可以创建一个简化的自动机来标记化它，如下图所示。

状态转换

让我们跳过数学术语，直接进入重点。虽然在数学上不那么精确，但这个解释更容易理解：

• 匹配过程可以抽象为一个“有限状态自动机”。
• 有限状态自动机等同于“正则表达式”，一种较弱的形式语言。

是的，用 lex！

通过为标记构建正则表达式，我们生成了有助于优化标记生成的自动机。手动编写转换表是不切实际的，所以我们依赖像“lex”这样的工具。在我们的实现中，我们将使用 GNU flex。

“flex”是一个生成扫描器的工具。本质上，我们向这个工具提供我们的标记定义，通常以正则表达式的形式。然后，这个工具生成一个自动机，它读取文本输入并输出标记。以下是一个 lex 定义文件的示例。大写的标签是我们定义的标记。

%{
// 一些前置声明
%}

%option nounistd
%option never-interactive
%option noyywrap
%option yylineno

%%
"//".*                          { __currentToken.preceding_metadata.emplace_back(TokenMetadata {.type=TokenMetadata::Comment,.value = std::make_shared<std::string>(yytext)}); return COMMENT; }

"import"                        { return IMPORT;  }
"return"                        { return RETURN;  }
"let"                           { return LET;     }
"init"                          { return INIT;    }
"floor"                         { return FLOOR;   }
"floor_max"                     { return FLOOR_MAX;}
"function"                      { return FUNCTION;}
"sub"                           { return SUBWORD;}

"if"                            { return IF;    }
"else"                          { return ELSE;  }
"while"                         { return WHILE; }
"for"                           { return FOR;   }
"break"                         { return BREAK;     }
"continue"                      { return CONTINUE;  }

">="                            { return GE; }
"<="                            { return LE; }
"=="                            { return EE; }
"!="                            { return NE; }
">"                             { return GT; }
"<"                             { return LT; }

"("                             { return OPEN_PAREN;   }
")"                             { return CLOSE_PAREN;  }
"{"                             { return OPEN_BRACE;   }
"}"                             { return CLOSE_BRACE;  }
"["                             { return OPEN_BRACKET; }
"]"                             { return CLOSE_BRACKET;}
","                             { return COMMA;        }

"&&"                            { return AND;          }
"||"                            { return OR;           }

"++"                            { return ADDADD;       }
"--"                            { return SUBSUB;       }
"!"                             { return NOT;          }
"+"                             { return ADD;          }
"-"                             { return SUB;          }
"*"                             { return MUL;          }
"/"                             { return DIV;          }
"%"                             { return MOD;          }
"="                             { return EQ;           }
";"                             { return T;            }

"true"                          { __currentToken.boolean = true; return BOOLEAN; }
"false"                         { __currentToken.boolean = false; return BOOLEAN; }
[0-9]+                          { __currentToken.integer = atoi(yytext); return INTEGER; }
"'"[A-Za-z]"'"                  { __currentToken.integer = toupper(yytext[1]); __currentToken.is_char = true; return INTEGER; }

[A-Za-z_][A-Za-z0-9_]*          { __currentToken.identifier = std::make_shared<std::string>(yytext); return IDENTIFIER; }
[ \t]+                          { }
[\n\r]                          { __currentToken.preceding_metadata.emplace_back(TokenMetadata {.type=TokenMetadata::Newline}); return NEWLINE; }

.                               { return TOKEN_ERROR; }

%%

在“%%”之间的部分定义了标记。我们在“HRLToken.h”中定义了标记枚举，例如“IMPORT”、“RETURN”、“LET”等等。“flex”从这个“.l”词法源文件生成一个 C/C++文件，最终，我们可以简单地通过调用“yylex()”来使用它，它返回下一个标记 ID。

我们完整定义的“.l”文件可以在这里找到。

下面是我们标记化后的人力资源机器懒人编码语言程序。

IMPORT IDENTIFIER ;
INIT FLOOR OPEN_BRACKET INTEGER CLOSE_BRACKET EQ INTEGER ;
INIT FLOOR OPEN_BRACKET INTEGER CLOSE_BRACKET EQ INTEGER ;
INIT FLOOR_MAX EQ INTEGER ;
FUNCTION IDENTIFIER OPEN_PAREN IDENTIFIER CLOSE_PAREN OPEN_BRACE
  FOR OPEN_PAREN LET IDENTIFIER EQ IDENTIFIER, IDENTIFIER GE INTEGER, SUBSUB IDENTIFIER CLOSE_PAREN OPEN_BRACE
    IDENTIFIER OPEN_PAREN IDENTIFIER CLOSE_PAREN ;
    CLOSE_BRACE
  RETURN IDENTIFIER ;
  CLOSE_BRACE
SUBWORD IDENTIFIER OPEN_PAREN CLOSE_PAREN OPEN_BRACE
  CLOSE_BRACE
SUBWORD IDENTIFIER OPEN_PAREN CLOSE_PAREN OPEN_BRACE
  WHILE OPEN_PAREN BOOLEAN CLOSE_PAREN OPEN_BRACE
    LET IDENTIFIER EQ IDENTIFIER OPEN_PAREN CLOSE_PAREN ;
    LET IDENTIFIER EQ IDENTIFIER OPEN_PAREN CLOSE_PAREN ;
    IF OPEN_PAREN IDENTIFIER GT IDENTIFIER CLOSE_PAREN OPEN_BRACE
      IDENTIFIER OPEN_PAREN IDENTIFIER CLOSE_PAREN ;
      CLOSE_BRACE
    ELSE OPEN_BRACE
      IDENTIFIER OPEN_PAREN IDENTIFIER CLOSE_PAREN ;
      CLOSE_BRACE
    LET IDENTIFIER EQ IDENTIFIER MUL IDENTIFIER ;
    LET IDENTIFIER EQ IDENTIFIER OPEN_PAREN IDENTIFIER CLOSE_PAREN ;
    FLOOR OPEN_BRACKET INTEGER CLOSE_BRACKET EQ IDENTIFIER ;
    FLOOR OPEN_BRACKET INTEGER CLOSE_BRACKET EQ FLOOR OPEN_BRACKET IDENTIFIER CLOSE_BRACKET ADD IDENTIFIER ;
    IDENTIFIER OPEN_PAREN IDENTIFIER CLOSE_PAREN ;
    CLOSE_BRACE
  CLOSE_BRACE
END