从零构造现代语言编译器(1): 词法分析

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class NumericLiteralToken {
 public:
  auto Text() const -> llvm::StringRef { return text; }

  static auto Lex(llvm::StringRef source_text)
      -> llvm::Optional<NumericLiteralToken>;

  auto GetRadixPoint() -> int { return radix_point; }

  auto GetExponent() -> int { return exponent; }

 private:
  NumericLiteralToken() {}

  llvm::StringRef text;

  // '.'字符的偏移量
  int radix_point;

  // 'e'或'p'字符的偏移量
  int exponent;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

auto NumericLiteralToken::Lex(llvm::StringRef source_text)
    -> llvm::Optional<NumericLiteralToken> {
  NumericLiteralToken result;

  // 判断source_text是否为空以及第一个字符是否为数字
  if (source_text.empty() || !IsDecimalDigit(source_text.front())) {
    return llvm::None;
  }

  bool seen_plus_minus = false;
  bool seen_radix_point = false;
  bool seen_potential_exponent = false;

  // 由于之前已经确认过首字符，这里索引从1开始
  int i = 1;
  for (int n = source_text.size(); i != n; ++i) {
    char c = source_text[i];
    if (IsAlnum(c) || c == '_') {
      // 只支持小写的 'e'，如果存在该字符且发现点号以及未探索
      // 到加减号则记录exponent索引位置，否则继续下一轮循环
      if (IsLower(c) && seen_radix_point && !seen_plus_minus) {
        result.exponent = i;
        seen_potential_exponent = true;
      }
      continue;
    }

    // 当前字符为 '.' 时，记录radix_point
    if (c == '.' && i + 1 != n && IsAlnum(source_text[i + 1]) &&
        !seen_radix_point) {
      result.radix_point = i;
      seen_radix_point = true;
      continue;
    }

    // 当前字符为 '+' 或 '-' 时，记录seen_plus_minus
    if ((c == '+' || c == '-') && seen_potential_exponent &&
        result.exponent == i - 1 && i + 1 != n &&
        IsAlnum(source_text[i + 1])) {
      assert(!seen_plus_minus && "should only consume one + or -");
      seen_plus_minus = true;
      continue;
    }
    break;
  }

  // 返回探索到的字符串，以当前i的值为索引切分子串
  result.text = source_text.substr(0, i);
  // 记录 '.' 偏移
  if (!seen_radix_point) {
    result.radix_point = i;
  }
  // 记录 'e' 或 'p' 偏移
  if (!seen_potential_exponent) {
    result.exponent = i;
  }

  return result;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class NumericLiteralToken::Parser {
 public:
  Parser(NumericLiteralToken literal);

  auto IsInteger() -> bool {
    return literal.radix_point == static_cast<int>(literal.Text().size());
  }

  auto GetRadix() const -> int { return radix; }

  auto GetMantissa() -> llvm::APInt;

  auto GetExponent() -> llvm::APInt;

 private:
  NumericLiteralToken literal; // 存储对应字面量

  // 基数默认为10，可以为 2 或 10 或 16
  int radix = 10;

  // 词法结构：[radix] int_part [. fract_part [[ep] [+-] exponent_part]]
  llvm::StringRef int_part; // 整数部分
  llvm::StringRef fract_part; // 小数部分
  llvm::StringRef exponent_part; // 指数部分

  // 对应数据是否需要清除`_`或`.`符号，默认为false
  bool mantissa_needs_cleaning = false;
  bool exponent_needs_cleaning = false;

  // 在`exponent`部分后面发现了`-`符号
  bool exponent_is_negative = false;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

NumericLiteralToken::Parser::Parser(NumericLiteralToken literal)
    : literal(literal) {
  int_part = literal.text.substr(0, literal.radix_point);
  if (int_part.consume_front("0x")) {
    radix = 16;
  } else if (int_part.consume_front("0b")) {
    radix = 2;
  }

  fract_part = literal.text.substr(literal.radix_point + 1,
                                   literal.exponent - literal.radix_point - 1);

  exponent_part = literal.text.substr(literal.exponent + 1);
  if (!exponent_part.consume_front("+")) {
    exponent_is_negative = exponent_part.consume_front("-");
  }
}

1
2
3
4

auto IsInteger() -> bool;
auto GetRadix() const -> int;
auto GetMantissa() -> llvm::APInt;
auto GetExponent() -> llvm::APInt;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

static auto ParseInteger(llvm::StringRef digits, int radix, bool needs_cleaning)
    -> llvm::APInt {
  llvm::SmallString<32> cleaned; // 预分配32个字节的字符串
  if (needs_cleaning) {
    cleaned.reserve(digits.size()); // 根据目标大小重建长度
    std::remove_copy_if(digits.begin(), digits.end(),
                        std::back_inserter(cleaned),
                        [](char c) { return c == '_' || c == '.'; });
    digits = cleaned;
  }

  llvm::APInt value;
  if (digits.getAsInteger(radix, value)) {
    llvm_unreachable("should never fail");
  }
  return value;
}

1
2
3
4
5
6

auto NumericLiteralToken::Parser::GetMantissa() -> llvm::APInt {
  // 如果为整数从int_part为结尾，否则以fract_part为结尾
  const char* end = IsInteger() ? int_part.end() : fract_part.end();
  llvm::StringRef digits(int_part.begin(), end - int_part.begin());
  return ParseInteger(digits, radix, mantissa_needs_cleaning);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

auto NumericLiteralToken::Parser::GetExponent() -> llvm::APInt {
  llvm::APInt exponent(64, 0); // 创建64位值为0的exponent对象。
  // 如果存在指数部分，就进入这个分支。
  if (!exponent_part.empty()) {
    // 解析指数部分。这个函数会将字符串形式的指数转换为整数。其中，
    // 第一个参数是指数部分，第二个参数10是代表十进制，第三个参数
    // 表示解析过程中是否需要进行清理。
    exponent = ParseInteger(exponent_part, 10, exponent_needs_cleaning);

    // 检查指数的符号位是否被设置，或者指数的位宽是否小于64。
    // 如果满足这些条件之一，就需要扩展指数的位宽。
    if (exponent.isSignBitSet() || exponent.getBitWidth() < 64) {
      // 扩展指数的位宽。新的位宽至少为64，如果原来的位宽+1大于64，
      // 那么就使用原来的位宽+1。扩展后，新增的位都被设置为0。
      exponent = exponent.zext(std::max(64U, exponent.getBitWidth() + 1));
    }

    // 如果指数是负数，就需要取反。
    if (exponent_is_negative) {
      exponent.negate(); // 取反操作。
    }
  }

  // 计算小数部分的字符数量，这个数量会影响实际的指数大小。
  int excess_exponent = fract_part.size();
  // 如果基数是16，即如果是十六进制的数，那么每一个小数部
  // 分的字符都会减少4个指数（因为一个十六进制的字符等于4个二进制位）。
  if (radix == 16) {
    excess_exponent *= 4; // 将小数部分的字符数量乘以4。
  }
  exponent -= excess_exponent; // 从指数中减去小数部分的字符数量。
  // 如果原来的指数是负数，但是计算后的指数变为非负，那么就进入这个分支。
  if (exponent_is_negative && !exponent.isNegative()) {
    // 扩展指数的位宽，新增的位被设置为0。
    exponent = exponent.zext(exponent.getBitWidth() + 1);
    // 设置指数的符号位，使得指数变为负数。
    exponent.setSignBit();
  }
  return exponent;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

auto StringLiteral::Lex(llvm::StringRef source_text)
    -> std::optional<StringLiteral> {
  int64_t cursor = 0;
  const int64_t source_text_size = source_text.size();

  // 确定前缀中的#数量。
  while (cursor < source_text_size && source_text[cursor] == '#') {
    ++cursor;
  }
  const int hash_level = cursor;

  const std::optional<Introducer> introducer =
      Introducer::Lex(source_text.substr(hash_level));
  if (!introducer) {
    return std::nullopt;
  }

  cursor += introducer->prefix_size;
  const int prefix_len = cursor;

  // 初始化终结符和转义序列标记。
  llvm::SmallString<16> terminator(introducer->terminator);
  llvm::SmallString<16> escape("\\");

  // 整终结符和转义序列的大小。
  terminator.resize(terminator.size() + hash_level, '#');
  escape.resize(escape.size() + hash_level, '#');

  /// TODO: 在找到终结符之前检测多行字符串字面量的缩进/反缩进。
  for (; cursor < source_text_size; ++cursor) {
    // 快速跳过不感兴趣的字符。
    static constexpr CharSet InterestingChars = {'\\', '\n', '"', '\''};
    if (!InterestingChars[source_text[cursor]]) {
      continue;
    }

    // 多字符的终结符和转义序列都以可预测的字符开始，
    // 并且不包含嵌入的、未转义的终结符或换行符。
    switch (source_text[cursor]) {
      case '\\':  // 处理转义字符。
        if (escape.size() == 1 ||
            source_text.substr(cursor + 1).startwith(escape.substr(1))) {
          cursor += escape.size();
          // 单行字符串且转义字符是换行符。
          if (cursor >= source_text_size || (introducer->kind == NotMultiLine &&
                                             source_text[cursor] == '\n')) {
            llvm::StringRef text = source_text.take_front(cursor);
            return StringLiteral(text, text.drop_front(prefix_len), hash_level,
                                 introducer->kind,
                                 /*is_terminated=*/false);
          }
        }
        break;
      case '\n':
        // 单行字符串。
        if (introducer->kind == NotMultiLine) {
          llvm::StringRef text = source_text.take_front(cursor);
          return StringLiteral(text, text.drop_front(prefix_len), hash_level,
                               introducer->kind,
                               /*is_terminated=*/false);
        }
        break;
      case '"':
      case '\'':
        if (source_text.substr(cursor).startswith(terminator)) {
          llvm::StringRef text =
              source_text.substr(0, cursor + terminator.size());
          llvm::StringRef content =
              source_text.substr(prefix_len, cursor - prefix_len);
          return StringLiteral(text, content, hash_level, introducer->kind,
                               /*is_terminated=*/true);
        }
        break;
      default:
        // 对于非终结符，不执行任何操作。
        break;
    }
  }
  return StringLiteral(source_text, source_text.drop_front(prefix_len),
                       hash_level, introducer->kind,
                       /*is_terminated=*/false);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// 计算给定文本中最后一行的缩进（即最后一行前面的水平空白字符序列）。
static auto ComputeIndentOfFinalLine(llvm::StringRef text) -> llvm::StringRef {
  int indent_end = text.size(); // 从文本的末尾开始，逐字符向前检查。
  for (int i = indent_end - 1; i >= 0; --i) {
    if (text[i] == '\n') { // 如果遇到换行符\n，则该位置之后的所有字符都是最后一行的缩进。
      int indent_start = i + 1;
      return text.substr(indent_start, indent_end - indent_start);
    }
    if (!IsSpace(text[i])) { // 如果遇到非空格字符，则更新缩进的结束位置。
      indent_end = i;
    }
  }
  // 如果没有找到换行符，这意味着给定的文本不包含换行符，这是一个错误情况。
  llvm_unreachable("Given text is required to contain a newline.");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// 简单字符串字面量:
var simple: String = "example";

// 块状字符串字面量:
var block: String = '''
    The winds grow high; so do your stomachs, lords.
    How irksome is this music to my heart!
    When such strings jar, what hope of harmony?
    I pray, my lords, let me compound this strife.
        -- History of Henry VI, Part II, Act II, Scene 1, W. Shakespeare
    ''';

// 块状字符串字面量带有文件类型指示器:
var code_block: String = '''cpp
    #include <iostream>
    int main() {
        std::cout << "Hello world!";
        return 0;
    }
    '''

1
2
3
4
5
6
7
8

// 带有换行转义序列的原始简单字符串字面量:
var newline: String = "line one\nline two";

// 带有字面量`\n`的原始简单字符串字面量，不是换行:
var raw: String = #"line one\nstill line one"#;

// 带有换行转义序列的原始简单字符串字面量:
var raw_newline: String = #"line one\#nline two"#;

1

var String: lucius = "The strings, my lord, are false.";

1
2

// 三个相邻的简单字符串字面量`""`、`"abc"`和`""`是无效的。
var String: block = """abc""";

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

// 所有块状字符串字面量默认包含一个尾随换行符。
var String: newline_example = '''
  This is a block string literal. Its first character is 'T' and its last character is
  a newline. It contains another newline character between 'is' and 'a'.
  ''';

// 可以使用转义字符'\'来抑制换行符
var String: suppressed_newlines = '''
  This is another block string literal. The newline character here \
  is suppressed, along with the trailing newline here.\
  ''';

// 这个块状字符串字面量是无效的，因为'closing'后面的'''终止了字面量，但它不在行的开头。
var String: invalid = '''
  error: closing ''' is not on its own line.
  ''';

1
2
3
4
5

// 这是一个块状字符串字面量。它的前两个字符是空格，它的最后一个字符是换行符。它有一个文件类型为'c++'。
var String: starts_with_whitespace = '''c++
    int x = 1; // 这一行以两个空格开始。
    int y = 2; // 这一行以两个空格开始。
  ''';

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

var String: fret = "I would 'twere something that would fret the string,\n" +
                   "The master-cord on's \u{2764}\u{FE0F}!";

// 这个字符串包含两个字符（在编码为UTF-8之前）：
// U+1F3F9 (弓和箭) 后跟 U+0032 (数字二)
var String: password = "\u{1F3F9}2";

// 这个字符串不包含换行符。
var String: type_mismatch = '''
  Shall I compare thee to a summer's day? Thou art \
  more lovely and more temperate.\
  ''';

var String: trailing_whitespace = '''
  This line ends in a space followed by a newline. \n\
      This line starts with four spaces.
  ''';

1
2
3
4
5
6
7
8
9

var String: x = #'''
  这是字符串的内容。'T'是字符串的第一个字符。
  ''' <-- 这不是字符串的结尾。
  '''#;
  // 但前面的那行确实结束了字符串。
// OK, 最后一个字符是\
var String: y = #"Hello\"#;
var String: z = ##"Raw strings #"nesting"#"##;
var String: w = #"Tab is expressed as \t. Example: '\#t'"#;