November 7, 2016

一个Go实现的简化json解析器

此文献给迷之博

很早就有想法要去实现一个go的解析器,倒也不是非要用go实现,而是想要在语言解释的道路上走一两步。本文给出的只是我自己做出的一个json解析器的实现方法,不是这个问题或者类似问题的最佳实践,而且我也才疏学浅,也不敢班门弄斧,仅仅做一个参考。

(本文结合github上的完整代码共同食用,效果更佳哦https://github.com/ZhihaoJun/zjson

问题阐述

先对问题做一个阐述,json解析器要做到什么功能。

根据一个json规范格式下的字符串,构造一个预先定义的go内置struct的指针,承载同样的结构和数据

json的规范,我参考的是

http://json.org/

“预先定义的go内置struct”长这样

type JSON struct {
  Type   int
  Map    map[string]*JSON
  Arr    []*JSON
  Str    string
  Bool   bool
  Number int
}

其中Type是表示其类型,用int来表示枚举值,定义的值列表如下

const (
  JSONTypeMap = 1 << iota
  JSONTypeArray
  JSONTypeString
  JSONTypeBool
  JSONTypeNumber
  JSONTypeNull
)

(可能各位看官也注意到了,JSON结构体中Number是个整数值,你丫的json不是有小数的嘛,难道你要用int表示浮点数?咳咳,嗯,还真不是的,只利用了go标准库中的atoi函数偷了个懒,也真是不想解析那复杂的数值表示,以后如果有时间,再更吧~)

总体步骤

本文把实现这个解析器分为两步:

  1. 分解Token(词法分析)
  2. 构造JSON结构体(语法分析)

分解Token

这一步是很多编译器、解释器的很靠前的步骤,这一步最主要的作用就是减轻后面语法分析器的工作难度。它的主要工作是

将字符串变成一个Token的线性链表

而所谓的Token,我是这样定义的:

type Token struct {
  Type int
  Buf  []byte
  Bool bool
  Num  int
}

其中Type是表示类型的,所有的类型如下:

const (
  TokenTypeLeftBracket = 1 << iota
  TokenTypeRightBracket
  TokenTypeLeftSquareBracket
  TokenTypeRightSquareBracket
  TokenTypeComma
  TokenTypeColon
  TokenTypeString
  TokenTypeBool
  TokenTypeNull
  TokenTypeNumber
)

构造JSON结构体

接收一个Token的线性链表作为输入,输出分析后的JSON结构体指针

这一步语法分析是以上一步的输出作为输入的,这一步其本质是通过不同的token序列的组合表达出的语义来构造JSON结构体和数据。

往往采用一个比较简单的分析模式就是使用有限状态机来实现语法分析。

下面就来聊一聊这两步具体是怎么样的

分解Token

分解Token有很多种做法,像比较有名的词法分析器flex,采用的是让用户定义Token的正则表达式来识别token,这样做其实很方便也很直观,也是利用到了状态机的特性。而我这里为了简单起见,只是定义了一个词法分析接口,至于是不是正则还是其他的方式,则由实现接口的具体方法来决定。

type Lexer interface {
  Run([]byte) (int, *Token, error)
}

Lexer接口中的Run就是进行语法分析的函数,输入的表示剩下的字符串部分,使用byte数组而不是string,是为了避免string在传递、复制、分片中的各种麻烦。返回值表示的含义分别是:这一个读取了几个byte、分离出的token、产生的错误。

对于具体的分解器,他的逻辑代码就很简单:

type TokenSpliter struct {
  lexers []Lexer
}

func (ts *TokenSpliter) Run(s []byte) ([]*Token, error) {
  r := []*Token{}
  for i := 0; i < len(s); {
    for _, lexer := range ts.lexers {
      n, token, err := lexer.Run(s[i:])
      if n > 0 {
        if err != nil {
          return nil, err
        }
        
        // move to next token's start
        i += n
        if token != nil {
          r = append(r, token)
        }
        
        // only one lexer will work
        break
      }
    }
  }
  return r, nil
}

于是乎,现在就可以定义一堆lexers来实现具体的json分解器,所有token的lexer在github里core/lexers.go文件可以找到,这里就只简单说一说

比如识别字符串的:

type StringLexer struct {
}

func (sl *StringLexer) Run(s []byte) (int, *Token, error) {
  if s[0] != '"' {
    return 0, nil, nil
  }
  i := 1
  for i < len(s) && s[i] != '"' {
    i++
  }
  // if i == len(s) raise error
  token := &Token{
    Type: TokenTypeString,
    Buf:  s[1:i],
  }
  return i + 1, token, nil
}

代码比较容易理解,找到开头的双引号,再去找结束的双引号,中间部分就是需要拿出来的字符串内容(我在这里又偷了个懒,json中字符串是支持escape转义字符的,而我这里只是纯粹的那字符取出来没有做更多处理)

构造JSON结构体

我这里采用的是使用状态机来分析语法,首先我们要做一个通用状态机的实现,在此基础之上,再针对json的语法做语法分析器。

状态机其学名叫做有限状态机(finite-state machine 缩写:FSM),最基本的逻辑框架就是:状态机内有一个当前状态,通过接受外部的输入,在不同条件下,转换成另外一种状态,产生相应的输出或者副作用。于是通过一个状态表可以完全描述其行为:

状态转移

(图片截图自Wikipedia:有限状态机

所以通用状态机需要做的事情有以下几条:

  1. 保存状态
  2. 让用户定义转移条件
  3. 在转移到新状态时执行指定的代码

为了降低通用状态机框架的侵入程度(给予使用者最大程度的自由)采用了下面的实现方式

type TransitionFunc func(*FSM, int) error
type StateFunc func(*FSM, int) error

type FSM struct {
  state   int
  trans   map[int][]TransitionFunc
  stateFn map[int]StateFunc
}

func (fsm *FSM) Tick() {
  funcs := fsm.trans[fsm.state]
  for _, fn := range funcs {
    err := fn(fsm, fsm.state)
    if err != nil {
      log.Println("[error occured during transition]", err)
      continue
    }
  }
}

func (fsm *FSM) UpdateState(state int) {
  fsm.state = state
  if fsm.stateFn[fsm.state] != nil {
    err := fsm.stateFn[fsm.state](fsm, fsm.state)
    if err != nil {
      log.Println("[error occured on state]", err)
    }
  }
}

还有一些设置转移函数和状态函数没有列出来,不过都是一些帮助性函数。

  1. 在state中保存状态
  2. 在Tick的时候会找到对应状态的转移函数(至于是否更新状态完全交给用户去调用UpdateState,不做任何返回值上的协议隐喻)
  3. 在UpdateState时,调用相应状态的用户定义的函数

这个状态机框架功能很简单,不过足够json语法分析使用了

状态转移函数

此时有了状态机,我们需要的就是完成json语法分析的状态表。在json标准的主页上,语法的结构图,其实在某种程度上隐喻了状态转移图,但是一个非常大的区别在于语法图表示的是无限递归的结构,我们不可能在设计时列出无限长的状态转移表,所以需要更多的内态来表示递归结构,从而使无限长的状态转移表变成有限的可实现的状态表。这里采用的是用栈的方式来简化递归结构

type Parser struct {
  fsm        *FSM
  tokens     []*Token
  current    int
  jsonStack  []*JSON
  lastPop    *JSON
  tokenStack []*Token
}
  • tokens便是当前在分析的token列表
  • current表示当前分析到何处了
  • jsonStack便是用来保存JSON的递归结构的栈
  • lastPop是为了保存上一个出栈的JSON结构体
  • tokenStack是可以把前面遇到的过的token放入这里,起到暂存的作用

也可以理解成这是语法分析器工作的“环境”

下面给出完整的json语法状态转移表(表格在手机上可能看不清)

json语法分析状态转移表

当设计这个表格时,力求的是完整描述,而在实现上,我们可以采用很多小的技巧来实现这个状态机,让实现的代码尽可能的复用

例如下面的写法,value是对一些平凡的类型(字符串、数字、布尔值、null值、对象、数字)的统称,与json规范上语法图中的value一致,进入value和从value退出来的处理逻辑都是一致的,所以可以把它们合并在一个函数中实现,达到复用的效果(这里采用的是函数式的编程方式,也可以采用面向对象的编程方式,将这些函数全部绑定在Parser结构体上)

func (p *Parser) generateTransitionFunc(fn ExecuteFunc) TransitionFunc {
  return func(fsm *FSM, state int) error {
    return fn(p, fsm, state)
  }
}
valueIn := p.generateTransitionFunc(func(p *Parser, fsm *FSM, _ int) error {
  t := p.currentToken()
  switch t.Type {
  case TokenTypeString:
    fsm.UpdateState(stringState)
  case TokenTypeNumber:
    fsm.UpdateState(numberState)
  case TokenTypeBool:
    fsm.UpdateState(boolState)
  case TokenTypeNull:
    fsm.UpdateState(nullState)
  case TokenTypeLeftBracket:
    fsm.UpdateState(objectStartState)
  case TokenTypeLeftSquareBracket:
    fsm.UpdateState(arrayStartState)
  }
  return nil
})

valueOut := p.generateTransitionFunc(func(p *Parser, fsm *FSM, _ int) error {
  t := p.currentToken()
  switch t.Type {
  case TokenTypeRightBracket:
    fsm.UpdateState(objectEndState)
  case TokenTypeRightSquareBracket:
    fsm.UpdateState(arrayEndState)
  case TokenTypeComma:
    fsm.UpdateState(commaState)
  }
  return nil
})

因为逗号会出现在对象、数组中,它们分别对应的下一个状态是不同的,在对象中下一个状态应该是对象的键值,在数组中是下一个数组中的值。于是在一个状态转移函数中实现也是运用到了复用的思想

commaOut := p.generateTransitionFunc(func(p *Parser, fsm *FSM, state int) error {
  switch p.parent().Type {
  case JSONTypeMap:
    fsm.UpdateState(objectKeyState)
  case JSONTypeArray:
    return valueIn(fsm, state)
  }
  return nil
})

可以注意到这里同时复用了valueIn转移函数

状态函数

状态转移函数描述的是状态机如何转移状态的规则集,而状态函数则是状态机转换到这个状态后需要执行的功能代码

  • objectStart 当到这个状态时,创建一个Map类型的JSON结构体,并压入jsonStack
  • objectEnd 当到这个状态时,从jsonStack中pop出当前父节点
  • objectKey 当到这个状态时,将当前的token压入tokenStack
  • arrayStart 当到这个状态时,创建一个Array类型的JSON结构体,并压入jsonStack
  • arrayEnd 当到这个状态时,从jsonStack中pop出当前父节点
  • string 当到这个状态时,创建一个string类型的JSON结构体,放入Token中的字符串,如果父节点是Map类型的JSON则从tokenStack中pop出键值token,设置键值对,如果父节点是Array类型的则在父节点的数组中append这个string,如果父节点是空的,则将这个string的JSON结构体压入jsonStack,再pop出来,相当于刚刚进入string的上下文就立马结束了
  • number 处理方式类同与string
  • bool 处理方式类同于string
  • null 处理方式类同于string

当所有的token都遍历处理了一遍之后,parser中保存的lastPop就是最后的根JSON结构体,返回这个即可

parser的框架代码

func (p *Parser) Parse(tokens []*Token) *JSON {
  p.tokens = tokens
  p.current = 0
  p.fsm.Reset()
  for i := 0; i < len(tokens); i++ {
    log.Println("[current state]", stateToStr[p.fsm.state])
    p.fsm.Tick()
    p.next()
  }
  return p.lastPop
}

note 0 如果输入的是非法字符串

这里讨论的便是有语法问题的json字符串如何识别的问题。

语法问题可能出现在两处:

  • 词法出错
  • 语法出错

词法出错,可以通过修改相应的lexer来达到识别不正确的词法,及时的在返回值中返回error

语法出错,往往是token的组合顺序不对,下一个期望出现的token的类型不正确,这时状态机无法转换状态,也就对应着状态转移设计表格中空白的位置,于是可以在转移函数中添加switch的默认分支来处理语法错误的情况。