关于javascript:如何用javascripttypescript写一个解析组合子库parser-combinator

parser能够认为是将一段文本转换为ast的工具。

作为前端开发人员，咱们的生态圈早已充斥着各种parser工具，通过本篇文章，心愿你能学习到parser combinator的实现原理，更加理解函数式编程。在有必要的时候，轻松地通过parser combinator实现本人的parser。本篇文章在实现parser combinator库后，在开端会通过应用这个库来实现一个json parser。

在开始之前，咱们先说一下parser combinator相比parser generator的劣势：

不必学习一门新的语言，如出名的parser generator: ANTLR,pegjs,nearley等，开发者首先要会BNF，而后还要学习各自的语法。而应用parser combinator，开发者能够应用他们最相熟的主语言
因为parser generator是通过一门语言生成代码（即生成parser），所以不易debugger和类型查看。
更弱小的表达能力，parser combinator领有宿主语言的所有表达能力。

咱们先写一个简略匹配的parser，直观感触下。须要阐明的是，编译原理中的语法分析通常分为LL算法和LR算法，解析组合子实质上应用的就是LL算法，即通过向前看字符，自顶而下的剖析，生成语法树。

function text(expected) {
  return function textParser(input){
    if (input.startsWith(expected)) {
      return expected;
    } else {
      return console.error(`expect ${expected}`);
    }
  }
}

text这个函数能够结构出匹配字符串的函数，如果匹配胜利就返回匹配到的字符，如果失败就打印出失败信息。

这是一个非常简单的parser构造函数，如果咱们心愿能匹配html,css,javascript中的任意字符应该怎么解决呢?

function oneOf(...ps){
  return function (input, state){
    let pResult = null
    for(let p of ps){
      pResult = p(input)
      if(pResult) return pResult
      continue
    }
  }
}
const matchLang = oneOf(text("html"), text("css"), text("javascript"))

const matched = matchLang("css")  // css

这里咱们通过oneOf函数和text函数即可结构出更弱小的匹配函数。

咱们整个解析组合子库的工作形式就是如上所示，通过一系列结构parser的函数组合，产生更弱小的parser。

下面的只是开胃菜，心愿大家有一个简略的理解，上面开始咱们的结构之旅。

上面的代码为了更加强壮和更好的可读性，都是应用typescript书写，但类型不是很简单，对typescript不相熟的同学不必放心

如果你将下面的示例复制粘贴，并运行，你会发现打印出“expect html”这个字符串，这是因为咱们的textParser中，如果匹配失败，就很简略地打印出了谬误的信息。所以首先咱们来定义parser执行胜利和失败的函数：

const SUCCESS = Symbol('success')
const MISMATCH = Symbol('mismatch')

function success<A>(value: A, state: ParserState): ParserResult<A>{
  return {
    type: SUCCESS,
    value,
    state: state
  }
}

function mismatch<A>(state: ParserState): ParserResult<A>{
  return {
    type: MISMATCH,
    state: state,
  }
}

下面的state保留了咱们parser执行的上下文信息，在咱们text函数结构出的函数中，如果匹配胜利，咱们只是简略的返回，但在理论的场景中，咱们的parser执行函数会持续地向前看，所以咱们须要保留一些上下文信息，对应的类型如下：

type UserState = object

interface ParserState{
  position: number;
  expectedTokens: string[];  // 谬误提醒时能够用
  userState: UserState;
}

type ParserResult<A> =  
  | { type: typeof SUCCESS, state: ParserState, value: A }
  | { type: typeof MISMATCH, state: ParserState }

向前看咱们须要挪动向前看第一个字符的指针，对应的函数如下：

function advance(state: ParserState, length: number): ParserState{
  return  length === 0 
    ? state 
    : {
        ...state,
        position: state.position + length,
        expectedTokens: []
      }
}

同时，当匹配谬误的时候，咱们心愿能展现期待匹配的字符：

function expect(state: ParserState, expected: string | string[]){
  return {
    ...state,
    expectedTokens: state.expectedTokens.concat(expected)
  }
}

当初来革新咱们的text函数:

function text(expected) {
  return function textParser(input, state){
    if (input.startsWith(expected)) {
      return success(expected, advance(state, expected.length));
    } else {
      return mismatch(expect(state, expected))
    }
  }
}

为了使咱们的api应用上更加地敌对不便，咱们再次革新text函数，让text函数返回一个parser对象：

function text(expected: string): Parser<string> {
  return new Parser(function textParser(input, state) {
    if (input.startsWith(expected, state.position)) {
      return success(expected, advance(state, expected.length));
    } else {
      return mismatch(expect(state, expected, false));
    }
  });
}

Parser是一个类，它的构造函数承受一个函数，在咱们的text函数中就是理论执行匹配的函数，而后Parser有一个parse函数，这是开始parse时执行的函数。

interface ParserFun<A> {
  (input: string, state: ParserState): ParserResult<A>;
}

const initialState: ParserState = {
  position: 0,
  expectedTokens: [],
  userState: {},
};

class Parser<A> {
  public _parse: ParserFun<A>;

  constructor(parse: ParserFun<A>) {
    this._parse = parse;
  }
  
  parse(input: string, userState = {}) {
    return this._parse(input, { ...initialState, userState });
  }
}

当初咱们只有text函数能结构出根本的匹配函数，且只能匹配字符，为了裁减咱们的能力，咱们写一个匹配正则的函数：

function regex(re: RegExp, expected?: string | string[]):   Parser<string>{
  const anchoredRegex = new RegExp(`^${re.source}`)
  return new Parser(function(input: string, state: ParserState){
    const m = anchoredRegex.exec(input.slice(state.position))  
    if(m == null){
      return mismatch(expect(state, re.source))
    }
    const matchedText = m[0]
    return success(matchedText, advance(state, matchedText.length))
  })
}

在理论匹配的过程中，咱们往往须要将匹配到的字符串改为另外一个构造，咱们增加map和mapTo函数：

export class Parser<A> {
  public _parse: ParserFn<A>;
  constructor(parse: ParserFn<A>){
    this._parse = parse
  }
  parse(input: string, userState = {}){
    return this._parse(input, { ...initialState, userState })
  }  
  map<B>(fn: (x: A) => B): Parser<B>{
    return new Parser((input: string, state: ParserState) => {
      const pResult = this._parse(input, state)
      if(pResult.type !== SUCCESS) return pResult
      return {
        ...pResult,
        value: fn(pResult.value)
      }
    })
  }
 
  mapTo<B>(b:B): Parser<B>{
    return this.map(_ => b)
  }
}

如果咱们想执行多个匹配函数，并解决他们的后果呢？

export function apply<TS extends any[], R>(f: (...args: TS) => R, ...ps: ParserMap<TS>){
  return new Parser(function(input: string, state: ParserState) {
    let results: TS = [] as any
    for(let p of ps){
      let pResult = p._parse(input, state)
      if(pResult.type !== SUCCESS){
        return pResult
      }
      results.push(pResult.value)
      state = pResult.state
    }
    return success(f(...results), state)
  })
}

看下面的代码可能有些形象，咱们来举一个理论的apply例子，如果咱们想匹配一个字符串，但想疏忽它前面的空白字符：

function first<A, B>(a: Parser<A>, b: Parser<B>): Parser<A>{
  return apply((firstArg, secondArg) => firstArg, a, b)
}

const token = word => first(text(word), regex(/\s*/))

让咱们把下面的模式做的更通用一些：

type MaybeParser = string | RegExp | Parser<string>

function first<A, B>(a: Parser<A>, b: Parser<B>): Parser<A>{
  return apply((firstArg, secondArg) => firstArg, a, b)
}

function second<A, B>(a: Parser<A>, b: Parser<B>): Parser<B>{
  return apply((firstArg, secondArg) => secondArg, a, b)
}
function liftP(a: MaybeParser): Parser<string>{
  if(typeof a === "string") return text(a)
  if(a instanceof RegExp) return regex(a)
  return a
}

function lexeme(junk: MaybeParser) {
  const junkP = liftP(junk)
  return (p: MaybeParser) => first(liftP(p), junkP)
}

const token = lexeme(/\s*/)

如果咱们想匹配布尔值，咱们就能够这样用：

const jTrue = token("true").mapTo(true)
const jFalse = token("false").mapTo(false)
const jBoolean = oneOf(jTrue, jFalse)

咱们把本篇结尾提到的oneOf函数革新：

function oneOf<A>(...ps: Parser<A>[]): Parser<A>{
  return new Parser((input: string, state: ParserState) => {
    let pResult: ParserResult<A>;
    let expected = state.expectedTokens
    for(let p of ps){
      pResult = p._parse(input, state)
      if(pResult.type !== SUCCESS) continue
      return pResult
    }
    return mismatch(expect(state, expected))
  })
}

在正则表达式中，*示意匹配0次或屡次，在词法剖析和语法分析中，这种模式也是很常见的，让咱们来实现这种模式。结构这种parser的函数，咱们命名为many，这是咱们本篇文章中绝对比拟难的一个函数。

要实现many，咱们先剖析下many有哪些状况：

一个都没匹配
匹配一个本人
匹配多个本人

通过后面first函数的结构教训，咱们很容易想到应用apply函数，进行多个parser的串联匹配，并在其中做递归，但一个要害的点是，某一步匹配失败后，应该返回空数组，咱们有上面的代码：

const EMPTYARRAY: any[] = []

class Parser<A> {
  public _parse: ParserFn<A>;
  constructor(parse: ParserFn<A>){
    this._parse = parse
  }
  parse(input: string, userState = {}){
    return this._parse(input, { ...initialState, userState })
  } 
  orElse(p: Parser<A>): Parser<A>{
    return oneOf(this, p)
  }  
}  

function pure<A>(value: A): Parser<A>{
  return new Parser((input, state) => {
    return success(value, state)
  })
}

function lazy<A>(getP: () => Parser<A>){
  let p: null | Parser<A> = null
  return new Parser((input, state) => {
    if(p == null) p = getP()
    return p._parse(input, state)
  })
}

function many<A>(p: Parser<A>): Parser<A[]>{
  const manyP: Parser<A[]> = apply((p, list) => [p, ...list], p, lazy(() => manyP).orElse(pure(EMPTYARRAY)))
  return manyP.orElse(pure(EMPTYARRAY))
}

这里的lazy函数，能够帮忙你应用还未声明的变量，当然其实many函数的构造方法有多种，你也能够这样：

const EMPTYARRAY: any[] = []

class Parser<A> {
  public _parse: ParserFn<A>;
  constructor(parse: ParserFn<A>){
    this._parse = parse
  }
  parse(input: string, userState = {}){
    return this._parse(input, { ...initialState, userState })
  } 
  orElse(p: Parser<A>): Parser<A>{
    return oneOf(this, p)
  }  
  chain<B>(fn: (x: A) => Parser<B>): Parser<B>{
    return new Parser((input: string, state: ParserState) => {
      const pResult = this._parse(input, state)
      if(pResult.type !== SUCCESS) return pResult
      const p2 = fn(pResult.value)
      return p2._parse(input, pResult.state)
    })
  }  
}  

function pure<A>(value: A): Parser<A>{
  return new Parser((input, state) => {
    return success(value, state)
  })
}

function many<A>(p: Parser<A>): Parser<A[]>{
  const manyP: Parser<A[]> = p.chain(x => oneOf(manyP, pure([])).map(xs => {
    return [x].concat(xs)
  })).orElse(pure(EMPTYARRAY))
  return manyP
}

这里的代码次要是为了展现chain这个函数，chain这个函数很有用，它承受一个函数，函数接管以后parser执行之后的后果，产生第二个parser，而后执行第二个parser的parse，通过chain，咱们能够动静地决定下一步的匹配形式。

其实通过下面的学习，能够发现咱们的组合子库的框架曾经搭建实现，如果想裁减它的能力，咱们只须要通过裁减根底的函数，或者将函数间进行组合，就能产生更弱小的parser。

当初让咱们以json parser为例，进行一次实战吧。

首先咱们来实现json的根本类型，依据规范https://www.json.org/json-en….，有如下代码：

function unquote(s: string) {
  return s.substring(1, s.length - 1);
}

// 此处为了不便浏览学习，并没有齐全依照规范去写匹配正则
const jNumber = token(/-?\d+(\.\d+)?/).map(x => +x)
const jString = token(/"(?:[^"|\"|\b|\f|\r|\n|\t])*"/).map(unquote)
const jTrue = token("true").mapTo(true)
const jFalse = token("false").mapTo(false)
const jBoolean = oneOf(jTrue, jFalse)
const jNull = token("null").mapTo(null)

而后咱们来定义一个一般的json数据结构:

// 与下面的many函数一样，为了应用还未声明的变量，咱们应用lazy函数
const jValue: Parser<JValue> = lazy(() => oneOf<JValue>(jNumber, jString, jBoolean, jNull, jObject, jArray))

最初让咱们实现object类型和array类型：

class Parser<A> {
  public _parse: ParserFn<A>;
  constructor(parse: ParserFn<A>){
    this._parse = parse
  }
  parse(input: string, userState = {}){
    return this._parse(input, { ...initialState, userState })
  }  
  sepBy<B>(parser: Parser<B>): Parser<A[]>{
    const suffixes = many(second(parser, this))
    return oneOf(apply((x, xs) => [x, ...xs], this, suffixes), pure(EMPTYARRAY))
  }
  skip<B>(junk: Parser<B>): Parser<A>{
    return first(this, junk)
  } 
  ... // 其余函数
}

const pair = apply((key, value) => [key, value], first(jString, token(":")) , jValue)
const comma = token(",")
const pairs = pair.sepBy(comma).map(pairs2Object)

const jObject = apply((leftBracket, obj, rightBracket) => obj, token('{'), pairs,  token('}'))
const jArray = token("[").chain(() => jValue.sepBy(comma)).skip(token("]"))

json parser曾经组合胜利了，咱们怎么应用它们呢？咱们定义一个函数接管parser，执行这个parser的parse，如果胜利就返回后果，如果失败就打印出错误信息：

export function parse<A>(parser: Parser<A>, input: string){
  const res = parser.skip(eof).parse(input)
  if(res.type === SUCCESS) return res.value
  if(res.type === MISMATCH) {
    return console.error(`position ${res.state.position}, expect ${res.state.expectedTokens}`)
  }
}

其中skip(eof)是为了保障咱们的parser匹配到了最初一个字符，如果匹配到了最初一个字符，还没匹配实现，就返回mismatch

class Parser<A> {
  skip<B>(junk: Parser<B>): Parser<A>{
    return first(this, junk)
  }
  // ...其余函数
}
const eof = new Parser(function eofParser(input: string, state: ParserState){
  if(input.length > state.position){
    return mismatch(expect(state, "EOF"))
  }
  return success(null, state)
})

从下面的代码能够看出，当咱们有了一个解析组合子库后，实现一个json parser是很容易的。而且json parser中应用的很多函数，在匹配其余语言的时候，咱们能够间接复用。

为了便于学习和消化，咱们总结下下面呈现的函数类型，下面大部分函数都是parser的结构器，对于这种函数，咱们称为Constructor（与咱们的构造函数不同）。而对于将一个Constrctor转换为另外一种Constructor的函数，咱们称为Combinator。

咱们最根本的匹配Constructor就是text函数和regex函数，在这两个函数的根底上通过各种combinator（oneOf,map,apply）等，使咱们的parser更加的弱小，同时这些单个函数也易于测试。

当初咱们的解析组合子库，曾经能够反对json parser，但它还有一些问题：

1、它的性能不好，如果读过我的另一篇文章回溯法和记忆法，你会发现咱们当初的解析组合子库应用的就是回溯法，很容易做一些反复的计算。

2、咱们的错误信息，显然是不够敌对的。在生产环境中，当咱们匹配失败时，咱们应显示期待的字符串，理论的字符串，匹配到的地位。

而这两点就作为进一步实际，留给读者去实现了。

参考：

https://zhuanlan.zhihu.com/p/…
https://lihautan.com/json-par…
https://medium.com/@jnkrtech/…
https://gist.github.com/yelou…
https://www.json.org/json-en….

关于javascript:如何用javascripttypescript写一个解析组合子库parser-combinator

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于javascript:如何用javascripttypescript写一个解析组合子库parser-combinator

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复