从 0 开始实现编程语言（一）：手写 jsonParser

乐观的摸一摸头的个人博客 / 175 / 1 / 创建于 3年前 / 更新于 3年前

简介

本篇作为先导将用一个简单的例子阐述词法分析和语法分析阶段的任务和实现。我们的任务是用php实现一个json_decode函数作为入门parser的例子，为了降低部分没有必要的复杂度，我们将不支持浮点/布尔/null类型的数据。如：

输入：{"a": [1, 2], "c": {"e": "f"}} 
输出：["a" => [1, 2], "c" => ["e" => "f"]]

为了完成这个工作，我们需要把任务先拆解，分为两部分：词法分析器和语法分析器。虽然说实现一个json parser分成两个部分是没必要的，但是待会儿你就能看到拆解完的实现有多简单。

词法分析器的实现

词法分析器的作用是将输入流转化为一个个token，在我们这里，输入就是json，输出就是一个个token，一个token就是一个单元。比如说：

a = b + 1

转化为token的对应关系如下：

a  => token{type: variable, value: a}
=  => token{type: assign,   value: }
b  => token{type: variable, value: b}
+  => token{type: minus,    value: }
1  => token{type: number,   value: 1}

每个token可以看作是一个带有type和value属性的对象，type用来表示他的类型，value则表示他真正的值。比如说在这里，$a首先是一个variable类型的token，但是只有一个type来代表它是不够的，因为变量名可能不一样，所以还需要一个value属性来存储它真正的名字，同理，数字类型的token也是如此，1被表示成了一个type为number，value为1的token。

回到我们的parser中，现在的目标是将json字符串转化为这样的token，先来看看json有哪些token：

{ "a" : "b", "c": [ 1 ] }

我们拆一下，有这么几种：

{
}
[
]
:
,
STRING
NUMBER

{、}、[、]、,、:这几个都是会出现在json中的特殊符号，我们把每一个都当成一种token。STRING类型的token则代表用双引号包裹的字符串，NUMBER则是代表数字。有了这些分类之后，我们可以开始动手实现词法分析程序了。

首先，定义一个lexer类。一般的，我们都会叫词法分析器lexer或scanner之类的：

// Lexer.php
class Lexer
{
    private $input; // 输入的字符串

    public function __construct(string $json)
    {
        $this->input = $json;
    }
}

为了让程序实现更简单，我们增加一些属性

class Lexer
{
    private $input; // 输入的字符串

    private $pos = -1;  // 指向当前要读取字符的位置

    private $c; // 当前的字符

    const EOF = -1; // 到达结尾

    public function nextToken(): array
    {
        // todo
        return [];
    }
}

我们将输入作为一个流，每次调用nextToken方法就会从这个流里面读取一个token，同时指针向后移动，读到结尾则返回EOF(end of file)。pos和c属性用来表示当前读到的位置和字符，EOF表示已经到结尾了。

private function readChar()
{
    if ($this->pos + 1 >= strlen($this->input)) {
        $this->c = self::EOF;
    } else {
        $this->c = $this->input[++$this->pos];
    }
}

继续增加辅助方法，readChar用来移动指针到下一个字符，并把当前的字符赋值给c属性，如果已经到结尾了，c会变成EOF。我们注意到，刚开始的pos属性默认值为-1，所以我们需要在构造方法里调用readChar方法将指针移到第一个字符:

public function __construct(string $json)
{
    $this->input = $json;
    $this->readChar();
}

json中可能还有空格或者换行之类的字符，我们希望也能支持，如果碰到这样的字符，直接跳过即可:

private function skipBlank()
{
    while (($this->c == ' ' || $this->c == "\t" || $this->c == "\n" || $this->c == "\r") && $this->c != self::EOF) {
        $this->readChar();
    }
}

nextToken方法的实现只需要我们根据当前字符去生成不同的token即可：

public function nextToken(): array
{
    $this->skipBlank(); // 跳过空白字符

    switch ($this->c) {
        case '{':
        case '}':
        case '[':
        case ']':
        case ':':
        case ',':
            $tok = $this->makeToken($this->c);
            $this->readChar();
            break;
        case self::EOF:
            $tok = $this->makeToken('eof');
            break;
        default:
            throw new Exception('unknown token '.$this->c);
    }

    return $tok;
}

private function makeToken($type, $value = ''): array
{
    return ['type' => $type, 'value' => $value];
}

这里要注意的是，如果我们到达结尾，需要返回一个type为eof的token，这样后续的语法分析程序才能知道已经到达了结尾。另外生成完token之后，当前指针也需要移动。

我们已经处理完了特殊字符的token，接下来还剩下STRING类型和NUMBER类型，先来看NUMBER，我们只要发现当前字符是数字类型的，则一直往后匹配到不是数字为止，把这个作为token返回，这里为了程序简单没考虑性能（不要在意这些细节）:

public function nextToken(): array
{
    $this->skipBlank();

    switch ($this->c) {
        ... 
        default:
            ...
            if ($this->isNumber($this->c)) {
                $tok = $this->makeToken('number', $this->matchNumber());
                break;
            }

            throw new Exception('unknown token '.$this->c);
    }

    return $tok;
}

private function matchNumber(): int
{
    $str = $this->c;
    $this->readChar();

    while ($this->isNumber($this->c)) {
        $str .= $this->c;
        $this->readChar();
    }

    return (int)$str;
}

private function isNumber($char)
{
    return preg_match('#^[0-9]$#', $char);
}

处理STRING类型的token也是类似，其实双引号中的字符有些可能需要转义（\n \r之类的字符），但这里先不考虑

public function nextToken(): array
{
    $this->skipBlank();

    switch ($this->c) {
        ...
        case '"':
            $tok = $this->makeToken('string', $this->matchStr());
            break;
        ...
    }

    return $tok;
}

private function matchStr(): string
{
    for ($this->readChar(), $str = ''; $this->c != '"' && $this->c !== self::EOF; $this->readChar()) {
        $str .= $this->c;
    }

    $this->expectChar('"');
    return $str;
}

private function expectChar($char)
{
    if ($this->c == $char) {
        $this->readChar();
        return;
    }

    throw new Exception('lexer error: expect '.$char.' but given '.$this->c);
}

这里增加了一个特殊的expectChar方法，这个方法用来吃掉一个期望的字符，如果不是期望的字符的话，报错。这里需要是因为字符串一定是以双引号结尾的，如果没有双引号，我们需要报错。

这样，词法分析程序就完成了，我们来点输入试一下

// Lexer_test.php
include "Lexer.php";
$l = new Lexer('"a" 1 , { } []:');

while (($tok = $l->nextToken())['type'] != 'eof') {
    print json_encode($tok)."\n";
}
// output
{"type":"string","value":"a"}
{"type":"number","value":1}
{"type":",","value":""}
{"type":"{","value":""}
{"type":"}","value":""}
{"type":"[","value":""}
{"type":"]","value":""}
{"type":":","value":""}

可以看到，程序可以很好的停止工作并且正确的跳过了空白和注释，token的type和value也是正确的。有了正确的词法分析程序，我们就可以进入下一步的parser阶段了

语法分析器的实现

语法分析器我们一般称之为parser，这个阶段一般完成的任务读取lexer产生的token，并检查语法规则是否正确，如果正确的话，可能会产生一颗语法树。这里暂时先不介绍语法树，我们把生成最终对象的任务放在这一步直接完成:

// Parser.php
class Parser
{
    /**
     * @var Lexer
     */
    private $l;

    // 当前token
    private $curToken;

    public function __construct(Lexer $l)
    {
        $this->l = $l;
    }
}

l属性是之前的Lexer对象，curToken表示当前的token，接下来定义一些辅助方法

private function nextToken()
{
    $this->curToken = $this->l->nextToken();
}

private function curTokenIs($tokenType)
{
    return $this->curToken['type'] === $tokenType;
}

private function expectCur($tokenType)
{
    if (!$this->curTokenIs($tokenType)) {
        throw new Exception('syntax error, expect '.$tokenType.' but given '.$this->curToken['type']);
    }

    $this->nextToken();
}

nextToken用来指向下一个token，curTokenIs方法用来判断当前token是不是我们期望的类型，expectCur跟Lexer中的expectChar类似：如果当前token是期望的token，那么吃掉，如果不是，则报错，这几个函数在我们接下来的实现中用的非常多，抽象出来是非常有必要的。

同样的，构造方法中需要初始化一下curToken:

public function __construct(Lexer $l)
{
    $this->l = $l;
    $this->nextToken();
}

接下来就是最重要的parse方法：

public function parse(): array
{
      // todo
      return [];
}

为了实现parse方法，我们先来分析一下json的结构：

json   => array | object

array  => [ (val)? (',' val)* ]

object => { (kvpair)? (',' kvpair)* }

kvpair => STRING ':' val

val    => json | NUMBER | STRING

=>符号表示可推导出，|符号表示或者，?表示0或者1个，*表示任意多个，kvpair表示键值对。其他的{ } [ ] , : NUMBER STRING都是前面提到的token

我们先来考虑第一条规则，json是个array或者object，我们可以根据当前的token类型来判断：

public function parse(): array
{
    if ($this->curTokenIs('[')) {
        $result = $this->parseArr();
        // parseArr会匹配到最后一个]，如果之后的token不是eof，说明语法错误
        $this->expectCur('eof'); 
        return $result;
    } elseif ($this->curTokenIs('{')) {
        $result = $this->parseObj();
        // parseObj会匹配到最后一个}，如果之后的token不是eof，说明语法错误
        $this->expectCur('eof'); 
        return $result;
    }

    throw new Exception('syntax error');
}

private function parseArr(): array
{
    // todo
    return [];
}

private function parseObj(): array
{
    // todo
    return [];
}

怎么样，是不是看起来很简单？接下来我们只要补充完parseArr和parseObj就大功告成了。先来看parseArr

private function parseArr(): array
{
    $this->nextToken(); // skip [

    if ($this->curTokenIs(']')) { // 空数组
        $this->nextToken(); // skip ]
        return [];
    }

    $arr = [];
    $arr[] = $this->parseVal();

    while (!$this->curTokenIs(']')) {
        $this->expectCur(','); // skip ,
        $arr[] = $this->parseVal();
    }

    $this->expectCur(']');
    return $arr;
}

private function parseVal()
{
    // todo
}

接下来我们再来补充parseVal方法，从之前的语法规则我们可以看到val是一个json或者字符串或者数字，我们只要把情况都列出来即可，要注意的是返回之前要消耗当前token：

private function parseVal()
{
    if ($this->curTokenIs('[')) {
        // val可能是个数组，可以复用之前已经实现的方法，这就是典型的递归下降
        return $this->parseArr();
    } elseif ($this->curTokenIs('{')) {
        // 同样，val也可能是个对象
        return $this->parseObj();
    } elseif ($this->curTokenIs('string') || $this->curTokenIs('number')) {
        $val = $this->curToken['value'];
        $this->nextToken(); // skip current
        return $val;
    }

    throw new Exception('syntax error');
}

到这里，就只剩下parseObj方法了，依葫芦画瓢:

private function parseObj(): array
{
    $this->nextToken(); // skip {

    if ($this->curTokenIs('}')) {
        $this->nextToken(); // skip }
        return [];
    }

    $obj = [];
    $this->parseKvPair($obj);

    while (!$this->curTokenIs('}')) {
        $this->expectCur(','); // skip ,
        $this->parseKvPair($obj);
    }

    $this->expectCur('}');
    return $obj;
}

private function parseKvPair(&$obj)
{
    // todo
}

这里parseKvPair需要往数组中追加值，为了简单性，直接传引用。

private function parseKvPair(&$obj)
{
    $key = $this->curToken['value'];
    $this->expectCur('string');
    $this->expectCur(':');
    $obj[$key] = $this->parseVal();
}

感受到递归的威力了吗？我们这里采用的parse方法叫递归下降，简单的解释就是将一个任务拆分成多个子任务，同时任务之间又有递归调用。最后，我们再写个简单的测试验证一下:

include "Lexer.php";
include "Parser.php";

$tests = [
    '{}',
    '[]',
    '{"a":1}',
    '["a","b"]',
    '{"a":[1,2], "b":{"c":"d", "e":["g"]}}'
];

foreach ($tests as $k => $json) {
    $actual = (new Parser(new Lexer($json)))->parse();
    $expect = json_decode($json, true);
    if ($actual != $expect) {
        print "expect ".json_encode($expect)." but given ".json_encode($actual)." at test {$k}\n";
        exit();
    }
}

print "test pass\n";
// output
test pass