如何编写一个简单的 parser

发表于 | 分类于

背景

最近由于工作需要，接触了几个与代码解析（parse）相关的工具，

比如，@babel/parser，typescript，yaml，

读过一点源码，也在这些优秀工具之上，做过一些简单的工作。


本文就记录一下当前我对 “代码解析技术” 的浅显理解。

解析器

解析器（parser）的功能是，将一段字符串，转换成有结构的数据。

解析过程看起来很神秘，但其实并没有黑魔法。

人们之所以觉得编写 parser 是一件有难度的事情，主要是由以下几方面决定的。


其一，很多 parser 的编写教程，都太偏理论，

上来就讲上下文无关文法、递归可枚举语言、下推自动机，等等。

全部掌握这些概念，是一件耗时耗力的事情。


其二，解析技术本身就多种多样，适用于不同的待解析的场景，

比如，LL、LR、LALR、GLR 文法对应的解析器。

理解每一种解析器的实现方式，也是一件烧脑的事情。


其三，日常所用的编程语言都挺复杂的，所以它们的 parser 也就复杂，

TypeScript 语言的 parser 动辄也有上万行了。

一下子接触到这么大的代码量，阅读起来会非常困难。


然而，以上这些难度，其实并非 parser 本身造成的，

人们常用的、手写的递归下降 LL(k) 解析器，已经可以解决大多数问题了。

所以，在学习 parser 之前，得先不要被它吓倒。


这就好比下棋一样，称为象棋大师是挺难的，没有一定的智商是办不到的，

但是走棋规则并不难学，大家都能学会。

编译领域

如果我们打算投身于编译领域进行开发的话，其实 parser 只是很小的一部分业务，

大多数常用的语言，都已经有成熟的 parser 工具了，

所以很难会需要我们从零开始写一个 parser。


因此，编译相关的大部分工作内容，不在于怎么写 parser，

而在于，如何利用现有 parser 的产物，做上层建筑。

能手写一个简单的 parser 知道它的原理，能读懂或维护一个复杂的 parser 就足够了。


跟其他软件开发领域一样，编译领域所要关心的，同样是业务问题，

即，如何利用更底层的基础设施，添加一些业务逻辑，在各方资源的限定下，为上层提供可靠的服务。

并不会因为编译领域更贴近底层，就什么都得从头开始做。


所以从这个角度来看，parser 只是编译团队所负责的一块很小的业务，

除非有明确的业务场景，才会将编写 parser 作为一块独立的项目来推进。

极简主义

一个极简主义的 parser，其实并不难实现。

我写了一个 parser，包括注释在内，总共也就 200 多行代码。

源码在这里：github: list-parser


它用来解析这样的一段字符串，

1
2
3
4
5
6
7
(a 
  (
    (c)
    d
  )
 e-f
)

解析结果如下，

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
{
  "expr": {
    "list": [
      {
        "name": "Identifier",
        "pos": 2,
        "end": 3,
        "text": "a"
      },
      {
        "list": [
          {
            "list": [
              {
                "name": "Identifier",
                "pos": 14,
                "end": 15,
                "text": "c"
              }
            ]
          },
          {
            "name": "Identifier",
            "pos": 21,
            "end": 22,
            "text": "d"
          }
        ]
      },
      {
        "name": "Identifier",
        "pos": 28,
        "end": 31,
        "text": "e-f"
      }
    ]
  }
}

下面我来介绍它是怎么解析的，以及编写这种 parser 的套路是什么。

（1）代码结构

一个手写的递归下降语法解析器，代码结构一般是这样的，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const parse = (() => {
  let sourceCode;
  let pos;
  let end;
  let token;

  return parse;

  // ---- ---- ---- ---- ---- ---- ---- ---- ----

  function parse(code) { }

  // ---- ---- ---- ---- ---- ---- ---- ---- ----

  function nextToken() { }

  // ---- ---- ---- ---- ---- ---- ---- ---- ----

  function assert(nameList) { }

})();

首先，我们将私有变量都放到了一个立即执行的函数中（闭包），以避免污染全局空间，

这样做比将它们定义为 class 的私有变量，会更简洁一些，

例如对 token 进行赋值时，只需要 token = ... 就行了，不用 this.token = ...。


其次，这个立即执行的函数直接返回 parse 函数，

parse 调用的其他函数通过 function 定义，

不用箭头函数定义的原因，这些函数的名字都会被 “变量提升”，以支持互递归调用。


最后，一个 parser 总共包含了以下 3 个部分，

  • parse: 语法分析器，由互递归调用的一堆函数组成

  • nextToken: 词法分析器，读取下一个 token

  • assert: 解析过程中，对上下文进行断言，便于快速排查问题

（2）词法分析器

nextToken 实现了一个极简的词法分析器，

调用 nextToken() 就会向后扫描下一个 token，

如果需要向前看多个 token，只需将扫描结果保存一下就可以了。

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
/**
 * 向后扫描一个 token
 */
function nextToken() {
  while (true) {
    if (pos >= end) {
      return token = createToken('EndOfFile', pos, pos, null);
    }

    const ch = sourceCode.charAt(pos);
    switch (ch) {
      case '(':
        return token = createToken('LeftBracket', pos, ++pos, ch);
      case ')':
        return token = createToken('RightBracket', pos, ++pos, ch);

      case ' ':
      case '\n':
        ++pos;
        continue;

      default:
        if (isIdentifierStart(ch)) {
          return token = scanIdentifier();
        }
    }
  }
}

值得注意是，nextToken 会对变量 token 进行赋值，

所以，每次访问 token 都能获取当前词法分析器位置最新的 token。


整个分析器的业务逻辑并不复杂，无非就是一个一个的读取单个字符，

判断单个字符，或者后续的一串字符，能否构成一个 token。


扫描 identifier（标识符） 时也印证了这一点，

我们判断当前扫描的字符是否 isIdentifierStart（标识符开头），

如果是的话，就向后扫描，得到一个完整的 identifier token。

1
2
3
4
5
6
7
(a 
  (
    (c)
    d
  )
 e-f
)

对于我们要解析的语言来说，总共只有 4 种 token，跳过了空格和换行符，

  • 左括号：(

  • 右括号：)

  • 标识符：例如 a，c，d，e-f

  • 文件结尾（EOF: end of file）

（3）语法分析器

语法分析器，是由可互递归调用的多个函数组成的，以下是完整的语法分析器代码，

因为语言比较简单，所以语法分析器也就不会特别复杂。


  • parse 调用了 parseExpr

  • parseExpr 调用了 parseList

  • parseList 又调用了 parseExpr

1
2
3
4
5
6
7
(a 
  (
    (c)
    d
  )
 e-f
)

这个 list 的语言构成规则如下：

一个 list 是由 ( 和 ) 包围的 exprs 组成

一个 exprs 是一个多或多个 expr，

一个 expr 要么是 identifier，要么是 list。


或者记为，

1
2
3
list = '(' exprs ')'
exprs = expr | expr exprs
expr = identifier | list
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
function parse(code) {
  sourceCode = code;
  pos = 0;
  end = sourceCode.length;

  nextToken();
  assert(['Identifier', 'LeftBracket']);
  const expr = parseExpr();

  nextToken();
  assert(['EndOfFile']);

  return {
    expr,
  }
}

function parseExpr() {
  assert(['Identifier', 'LeftBracket']);

  if (token.name === 'Identifier') {
    return token;
  }

  assert(['LeftBracket']);
  const list = parseList();
  return list;
}

function parseList() {
  assert(['LeftBracket']);

  // 向后扫描 exprs 各项，放到列表中
  const results = [];
  while (true) {
    nextToken();
    assert(['RightBracket', 'Identifier', 'LeftBracket']);

    // 遇到右括号，说明当前层级的 exprs 处理完毕
    if (token.name === 'RightBracket') {
      break;
    }

    assert(['Identifier', 'LeftBracket']);
    const expr = parseExpr();
    results.push(expr);
  }

  return {
    list: results,
  }
}

语法分析器编写的办法，就是对着上述语法规则，手动 nextToken()，

向前看一个（或多个）token，递归的分层次处理问题。


其中，assert 起到了关键作用，便于我们在编写代码时，立即发现问题。

结语

以上就是一个 200 行左右的极简 parser 了，但麻雀虽小五脏俱全，

包含了一些常见的 parser 编写套路。


根据二八定律，一个实际 parser 中可能花费了 80% 的时间来处理剩下 20% 的问题。

比如，如何进行发现并显示错误的位置，如何增强解析过程的容错性，

如何组织代码，怎样按逻辑结构，将词法分析器和语法分析器剥离出去。


现实要解析的语言，往往也会更加复杂，所以词法和语法分析器也会变得很麻烦。

但这并不是 parser 本身难以编写造成的，而是因为场景复杂。


本文介绍了我在学习 parser 过程的一些体会。

单独拿出解析技术本身来看的吧，确实足够艰深和复杂，

但其实我们很难会遇到，所以日常工作中，会写一个极简的 parser 就足够了。