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のような関数を渡すことができるため、特別に引数としては用意していません。