Nimでパーサーコンビネータを実装したので、紹介もかねてパーサーコンビネータの解説をしてみたいと思います。

パーサーコンビネータとは

パーサーコンビネータとは、1つの関数として実装された複数のパーサーを受け取り、1つの新しいパーサーを返すような関数のことです。

import akorda

let acceptA = acceptChar[string]({'a'})
let acceptB = acceptChar[string]({'b'})
let acceptAB = acceptA & acceptB

echo acceptAB.parse("ab").isAccepted
# output: true

acceptCharは、set[char]を受け取って、それに含まれる文字をacceptするような関数を返す関数です。
上の例において、パーサーコンビネータは&という演算子です。
この演算子は、左側のパーサーが入力文字列をn文字acceptして終了したとき、右側のパーサーにn文字ずらして入力文字列を渡すようなパーサーを返すパーサーコンビネータになります。

この文法をBNFで表現すると、次のようになります。

<A> ::= "a"
<B> ::= "b"
<AB>::= <A> <B>

渡したパーサーのいずれかでacceptされるパーサーを作るコンビネータもあります。

import akorda

let acceptA = acceptChar[string]({'a'})
let acceptB = acceptChar[string]({'b'})
let acceptAorB = acceptA | acceptB

echo acceptAorB.parse("a").isAccepted
# output: true

この文法をBNFで表現すると、次のようになります。

<A> ::= "a"
<B> ::= "b"
<AB>::= <A> | <B>

任意の繰り返しを表現するコンビネータもあります。

import akorda

proc parseInt(prev: ParseResult[int], next: ParseResult[int]): ParseResult[int] =
  if isFailed(next):
    return next
  result.shallowCopy(next)
  result.parseObj = parseInt(next.val)

let digit = acceptChar[int]({'0'..'9'})
let number = repeat[int](digit, 1) $- parseInt

echo acceptAB.parse("12345678").parseObj
# output: 12345678

repeat関数がそのコンビネータです。この文法をBNFで表現すると、以下のようになります。

<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<number>::= <digit> | <number> <digit>

$-演算子はakorda特有の記法で、パーサーに対して何らかのアクションを付加することができます。この例では、acceptされた数字をintに変えてParseResultのparseObjに入れるという操作をしています。

論理的には、これだけで任意の文法を表すことができますが、Nimの言語仕様上の問題で表現できない文法があります。たとえば、以下の文法を表現することはできません。

<list> ::= "[" <list-content> "]"
<list-content> ::= <list-item> | <list-content> <list-item>
<list-item> ::= <list> | <number> | <string> | <symbol>

<number>, <string>, <symbol>は、任意の非終端記号です。
なぜ、この文法がakordaで表現できないのかというと、<list-item>が<list>に循環的に依存しているからです。循環的な依存関係をNimはうまく扱うことができません。(正確には、できなくはないがかなりめんどくさそう)

akordaの実装

akordaを利用して、以下のような文法を表現してみます。

<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<number>::= <digit> | <number> <digit>
<operator> ::= "+" | "-" | "*" | "/"
<expr> ::= <number> | <number> <operator> <number>

この文法は、以下のように表現できます。

import akorda

proc parseInt(prev: ParseResult[int], next: ParseResult[int]): ParseResult[int] =
  if isFailed(next):
    return next
  result.shallowCopy(next)
  result.parseObj = parseInt(next.val)

proc compute(handle: proc (a, b: int): int): ParserHandler[int] =
  (
    proc (prev: ParseResult[int], next: ParseResult[int]): ParseResult[int] =
      if isFailed(next):
        return next
      result.shallowCopy(next)
      result.parseObj = handle(prev.parseObj, next.parseObj)
  )

let intLit = repeat[int](acceptChar[int]({'0'..'9'}), 1) $- parseInt
let opAdd = acceptChar[int]({'+'})
let opSub = acceptChar[int]({'-'})
let opMul = acceptChar[int]({'*'})
let opDiv = acceptChar[int]({'/'})

let litAdd = intLit & opAdd & intLit $- compute(proc(a,b: int): int = a + b)
let litSub = intLit & opSub & intLit $- compute(proc(a,b: int): int = a - b)
let litMul = intLit & opMul & intLit $- compute(proc(a,b: int): int = a * b)
let litDiv = intLit & opDiv & intLit $- compute(proc(a,b: int): int = a div b)

let parser = litMul | litDiv | litAdd | litSub | intLit
let parsed = parser.parse("123+456")

echo parsed.parseObj
# output: 579

akorda内部において、パーサーは以下のような型で表現されています。

type
  ParseResult*[T] = object of RootObj
    success: bool
    pos*: Natural
    length*: Natural
    val*: string
    parseObj*: T

  Parser*[T] = proc(source: string, index: Natural, prev: ParseResult[T]): ParseResult[T]
  ParserHandler*[T] = proc(prev: ParseResult[T], next: ParseResult[T]): ParseResult[T]

ParseResultはパーサーが文字列を処理した結果を表すオブジェクトです。型引数Tは、ASTなどの型を指定します。
Parser型が表しているように、1つのパーサーは3つの引数をもち、ParseResult[T]を返す関数です。

さて、唯一の組み込みパーサーである、acceptCharの実装を示します。

template acceptChar*[T](acceptables: set[char]): Parser[T] =
  (
    proc (source: string, index: Natural, prev: ParseResult[T]): ParseResult[T] =
      if source.len-1 < index: # 入力文字列の終端を超えていたらUnaccepted
        ParseResult[T](success: false, pos: index)
      elif source[index] in acceptables: # acceptablesに含まれている文字であればAccepted
        ParseResult[T](success: true, pos: index, length: 1, val: source[index..index], parseObj: prev.parseObj)
      else: # それ以外ならUnaccepted
        ParseResult[T](success: false, pos: index)
  )

極めて単純な実装になっています。パーサーコンビネータのメリットがまさにこれで、複雑な文法を表現するために複雑な関数を直接書く必要がないのです。

ORコンビネータの実装も単純なものになっています。

template `|`*[T](left: Parser[T], right: Parser[T]): Parser[T] =
  (
    proc (source: string, index: Natural, prev: ParseResult[T]): ParseResult[T] =
      let leftResult = left(source, index, prev)
      if isAccepted(leftResult):
        return leftResult
      right(source, index, prev)
  )

左側のパーサーの結果がacceptedであればそれを直接返し、そうでなければ右側のパーサーの結果を返すというような実装です。

combineコンビネータの実装はそれよりも少し複雑ですが、それでも入力文字の位置をずらす処理が入っただけです。

template `&`*[T](left: Parser[T], right: Parser[T]): Parser[T] =
  (
    proc (source: string, index: Natural, prev: ParseResult[T]): ParseResult[T] =
      let res = left(source, index, prev)
      if isFailed(res):
        return res
      result = right(source, index + res.length, res)
      result.length += res.length
  )

左側のパーサーがunacceptedであればそれを直接返し、そうでなければacceptされた文字数分入力位置をずらして右側のパーサーに渡す、というような動作をします。

最後に、chainコンビネータの実装を示します。

template repeat*[T](target: Parser[T], least: Natural = 0, maximum: Natural = high(int)): Parser[T] =
  (
    proc (source: string, index: Natural, prev: ParseResult[T]): ParseResult[T] =
      var idx = index
      var parsed = ParseResult[T](
        success: true,
        pos: index)
      var prevR: ParseResult[T] = prev

      for i in 0..maximum:
        let res = target(source, idx, prevR)
        if isFailed(res):
          if i >= least:
            return parsed
          return res
        idx += res.length
        parsed.length = idx - index
        parsed.val = source[index..idx-1]
        parsed.parseObj = res.parseObj
        prevR = res
  )

やっていることはほとんどcombineコンビネータと一緒なのですが、渡されたパーサーがunacceptedになるまで繰り返すというのが異なります。
他のパーサーコンビネーターのライブラリでは、accumulatorを一緒に渡すことが多いのですが、akordaでは、任意の場所に$-演算子を用いてaccumulatorのような関数を渡すことができるため、特別に引数としては用意していません。

GitHubリポジトリ