# Parser Combinator 是什么呢？ ↵

所谓「词法解析」就是将扁平的字符串转为某种带结构的构造，比如解析字符串的

"[1,23]"

使其变成 JS Array 对象

[1, 23]

，而 parser combinator 是一种写「词法解析」的通用范式，它将 parser 概括为判断字符串的第一个元素是否满足「规则」然后通过组合子的方式将这些「规则」构造成更复杂的「规则」最终得到完整的「词法解析」 —— 总之，利用这样的方式我们可以将下图里这样的表达式字符串转为某种描述表达式的 ADT：

XhrUnsent

基于这样的模式来写词法分析爽的不行（⬅️ 刚通宵完现在爽到根本没有困意）

具体直接看代码吧，曼妙无需多言（上次这么爽还是上次写 lisp 解释器的时候）

下面这个链接是 Moonbit 在线 VSCode Playground 分享代码，建议右侧运行并全屏使用（文件右键可以执行我上面的代码）

https://try.moonbitlang.cn/#dbe28e82

看完真的醍醐灌顶，深刻领教了

Combinator

体现的函数式思想，再配合 ADT 带上满血版模式匹配写 parser 爽到飞起，现在再看大学编译原理用 C 写的各种 for 循环然后 getChar 风格的词法解析就会感觉丑到无法入眼了。（以下是完整代码，再贴一遍233）

000enum Token {
001  Value(Int)
002  LParen;
003  RParen;
004  Plus;
005  Minus;
006  Multiply;
007  Divide;
008} derive(Debug)
009
010type Lexer[V] (String) -> Option[(V, String)]
011
012fn parse[V](self: Lexer[V], str: String) -> Option[(V, String)] {
013  (self.0)(str)
014}
015
016fn pchar(predicate: (Char) -> Bool) -> Lexer[Char] {
017  Lexer(fn (input) {
018    if input.length() > 0 && predicate(input[0]) {
019      let start = 1
020      Some((input[0], input.substring(~start)))
021    } else {
022      None
023    }
024  })
025}
026
027let symbol: Lexer[Token] = pchar(fn (input) {
028  match input {
029    '+' | '-' | '*' | '/' | '(' | ')' => true
030    _ => false
031  }
032}).map(fn {
033  '+' => Plus
034  '-' => Minus
035  '*' => Multiply
036  '/' => Divide
037  '(' => LParen
038  ')' => RParen
039})
040
041let whitespace: Lexer[Char] = pchar(fn (input) {
042  match input {
043    ' ' => true
044    _ => false
045  }
046})
047
048fn map[I, O](self: Lexer[I], f: (I) -> O) -> Lexer[O] {
049  Lexer(fn(input) {
050    let (value, rest) = self.parse(input)?
051    Some((f(value), rest))
052  })
053}
054
055fn and[V1, V2](self: Lexer[V1], parser2: Lexer[V2]) -> Lexer[(V1, V2)] {
056  Lexer(fn (input) {
057    let (value, rest) = self.parse(input)?
058    let (value2, rest2) = parser2.parse(rest)?
059    Some(((value, value2), rest2))
060  })
061}
062
063fn or[Value](self: Lexer[Value], parser2: Lexer[Value]) -> Lexer[Value] {
064  Lexer(fn (input) {
065    match self.parse(input) {
066      None => parser2.parse(input)
067      Some(_) as result => result
068    }
069  })
070}
071
072fn many[Value](self: Lexer[Value]) -> Lexer[List[Value]] {
073  Lexer(fn (input) {
074    let mut rest = input
075    let mut cumul = List::Nil
076    while true {
077      match self.parse(rest) {
078        None => break
079        Some((value, new_rest)) => {
080          rest = new_rest
081          cumul = Cons(value, cumul)
082        }
083      }
084    }
085    Some((cumul.reverse(), rest))
086  })
087}
088
089let zero: Lexer[Int] = pchar(fn { ch => ch == '0' })
090  .map(fn { _ => 0 })
091
092let one_to_nine: Lexer[Int] =
093  pchar(fn { ch => ch.to_int() >= 0x31 && ch.to_int() <= 0x39 })
094  .map(fn { ch => ch.to_int() - 0x30 })
095
096let zero_to_nine: Lexer[Int] =
097  pchar(fn { ch => ch.to_int() >= 0x30 && ch.to_int() <= 0x39 })
098  .map(fn { ch => ch.to_int() - 0x30 })
099
100// number = %x30 / (%x31-39) *(%30-39)
101let value: Lexer[Token] =
102  zero.or(
103    one_to_nine.and(
104      zero_to_nine.many()
105    ).map(fn {
106      ((i, ls)) => ls.fold_left(fn (acc, cur) {
107        acc * 10 + cur
108      }, init=i)
109    })
110  ).map(Token::Value)
111
112
113// 注意到输入流里有各种空格，因此完整 tokens 可以定义为下面这样:
114pub let tokens: Lexer[List[Token]] =
115  whitespace.many().and(value.or(symbol).and(whitespace.many()))
116    .map(fn { (_, (symbols, _)) => symbols })
117    .many()
118
119fn init {
120  let input = "  + 123 313 +- /*22"
121  let Some((result, _)) = tokens.parse(input)
122  debug(result.to_array())
123}

人只活在瞬间啊 ~