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

28次阅读

共计 10067 个字符，预计需要花费 26 分钟才能阅读完成。

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
发表至： javascript
2020-12-12
 0
JavaScript数据结构与算法—— 栈
js中你知道有几种-字符串转-数组呢
vue路由
前端程序员应该往全栈方向发展吗？坚守前端怎么样呢？