Typescriptでパーサコンビネータを書いてみる

Typescriptは静的に型付があるので安全ではあるのですが、JavascriptではJSON.parseなどの結果を動的にたどることができたのに対してTypescriptでは静的型にして返す必要があり、Javascriptを書くときと比べて煩わしさがあったりします。Typescriptで自由な形のJsonを扱えるようになりたいと思っていましたので、いっその事自分でパーサコンビネータを書いてそれからJsonのパーサを生成できるようにしたいと思います。 パーサコンビネータの実装について調べたところ@kmizu氏のJavaによるパーサコンビネータ実装の記事が参考になったので、まずはこれをTypescriptで書き直したいと思います。

パーサコンビネータとは

パーサコンビネータは、単純な部品（パーサ）の組み合わせ（コンビネーション）で構文の解析を行うもののようです。例えば特定の文字が含まれている、連続しているなどの判定を行う単純な部品を作成しておいてそれを組み合わせればJsonやxmlの解析が行えるようになるといったものです。似たものにパーサジェネレータがありますが、パーザジェネレータはホスト側のプログラミング言語の別の構文で書かれた定義ファイルを読み取り、そこからホスト側のプログラミング言語で書かれたパーザを自動生成するものでSQLが馴染み深いかと思います。

文字判定のパーザを実装する

まず、パーサのインターフェースを実装します。

export interface Parser<T> {
    parse(input: string ):ParseResult<T>;
}

このインターフェースを実装した文字判定のパーザを実装するのですが、次はパーザの結果が成功か失敗かを判定するクラスを作成します。

export interface ParseResult<T> {}

export class ParseSuccess<T> implements ParseResult<T> {
    value: T;
    next: string;

    constructor(value: T, next: string){
        this.value = value
        this.next = next
    }

    public toString(): string{
        return "Success(" + this.value + ", " + this.next + ")";
    }
}

export class ParseFailer<T> implements ParseResult<T> {
    message: string;
    next: string;

    constructor(message: string, next: string){
        this.message = message
        this.next = next
    }

    public toString(): string{
        return "Failer(" + this.message + ", " + this.next + ")";
    }
}

それから文字列判定のパーザを実装します。

export class StringParser implements Parser<string> {
    literal: string;
    public constructor(literal: string) {
        this.literal = literal;
    }
  
    getLiteral():String{
      return this.literal;
    }

    parse(input: string):ParseResult<String> {
        if(input.startsWith(this.literal)){
            return new ParseSuccess(this.literal, input.substring(this.literal.length))
        }
        return new ParseFailer("expect: " + this.literal, input);
    }
}

パーザ生成用関数は一つのファイルでまとめておきます。

export function string(literal:string) {
    return new StringParser(literal)
}

こうする事で ParserGen.string("Hello, ") のようにする事でパーザの生成が行えます。ParserGenの部分は import * as ParserGen from '../parser/parser-genrator' のようにimportするときに指定します。 実際に動かしてみると以下のように文字列の判定が行えます。

    const str1 = "Hello, world!"
    
    const helloParser = ParserGen.string("Hello, ")
    const worldParser = ParserGen.string("world")
    console.info(helloParser.parse(str1))
    console.info(worldParser.parse(str1))

ParseSuccess {value: "Hello, ", next: "world!"} ParseFailer {message: "expect: world", next: "Hello, world!"} 正常に動いています。

0回以上の文字の連続を判定する

文字の連続は以下のように判定できます。

export class ContinueParser implements Parser<any> {
    parser: Parser<any>

    constructor(parser: Parser<any>) {
        this.parser = parser
    }

  
    parse(input: string) :ParseResult<Array<any>> {
        var next: string  = input
        const values: Array<any> = new Array()
        while(true) {
            const previous = next;
            const result = this.parser.parse(next);
            if(result instanceof ParseSuccess) {
                values.push(result.value);
                next = result.next
            } else {
                return new ParseSuccess(values, previous);
            }
        }
    }
}

1回以上の文字連続を判定する場合はparse関数の実装を少し修正すれば行えるかと思います。 それから、パーザ生成の関数を書きます。

export function many( parser: Parser<any>) {
    return new ContinueParser(parser)
}

動作確認は以下のようになります。

    const str2 = "Hello, Hello, world!"
    const helloParser = ParserGen.string("Hello, ")
    const helloContinuesParser = ParserGen.continues(helloParser)

    console.info(helloContinuesParser.parse(str2))

ParseSuccess {value: Array(2), next: "world!"} パースに成功しています。

2つのパーザの連続を扱えるようにする

2つのパーザの連続を扱える場合はいかにようになります。

export class SeqParser implements Parser<[any, any]> {
    lhs: Parser<any>
    rhs: Parser<any>

    constructor(lhs: Parser<any>, rhs: Parser<any>) {
        this.lhs = lhs
        this.rhs = rhs
    }

  
    parse(input: string) :ParseResult<any> {
        const lresult:ParseResult<any>  = this.lhs.parse(input);
        if(lresult instanceof ParseSuccess) {
            const value1:ParseResult<any> = lresult.value
            var next = lresult.next
            const rresult:ParseResult<any>  = this.rhs.parse(next);
            if(rresult instanceof ParseSuccess) {
                const value2:ParseResult<any> = rresult.value
                return new ParseSuccess<[any, any]>([value1, value2],
                    rresult.next
                );
            } else if(rresult instanceof ParseFailer) {
                return new ParseFailer<any>(next + " is not match", rresult.message);
            } else {
                return new ParseFailer<any>(next + " is not match", input);
            }
        } else {
            return new ParseFailer<any>(next + " is not match", input);
        }
    }
}

やっていることは単純で左側のパーザが成功したら右側のパーザも実行するというものになります。 パーザ生成の関数も用意します。

export function seq( lps: Parser<any>, rps: Parser<any>) {
    return new SeqParser(lps, rps)
}

動きを確認してみます。

    const str2 = "Hello, Hello, world!"
    const helloParser = ParserGen.string("Hello, ")
    const worldParser = ParserGen.string("world")
    const manyHelloWorld = ParserGen.seq(ParserGen.continues(helloParser), worldParser)
    
    console.info(manyHelloWorld.parse(str2))

ParseSuccess {value: Array(2), next: "!"}

2つのパーザの連続をさらに組み合わせることはできますが、パーザの生成が大変になるかもしれないのでその場合は3つのパーザの連続を実装する方が良いかもしれないです。

    const str = "Hello(world)"
    const manySeqParser = ParserGen.seq(ParserGen.seq(ParserGen.seq(ParserGen.string("Hello"), ParserGen.string("(")), ParserGen.string("world")), ParserGen.string(")"))
    console.info(manySeqParser.parse(str))

Success(Hello,(,world,), )

3つのパーザの連続を扱えるようにする

2つのパーザの連続を組み合わせだけだと配列などの判定が面倒になると思いますので3つのパーザを組み合わせれるようにしてみます。

import {Parser} from './parser'
import {ParseResult, ParseSuccess, ParseFailer} from './parser-result'

export class TripleParser implements Parser<[any, any, any]> {
    fhs: Parser<any>
    shs: Parser<any>
    ths: Parser<any>

    constructor(fhs: Parser<any>, shs: Parser<any>, ths: Parser<any>) {
        this.fhs = fhs
        this.shs = shs
        this.ths = ths
    }
  
    parse(input: string) :ParseResult<any> {
        const fresult:ParseResult<any>  = this.fhs.parse(input);
        if(fresult instanceof ParseSuccess) {
            const value1:ParseResult<any> = fresult.value
            var next = fresult.next
            const sresult:ParseResult<any>  = this.shs.parse(next);
            if(sresult instanceof ParseSuccess) {
                const value2:ParseResult<any> = sresult.value
                next = sresult.next
                const tresult:ParseResult<any>  = this.ths.parse(next);
                if(tresult instanceof ParseSuccess) {
                    const value3:ParseResult<any> = tresult.value
                    next = tresult.next
                    return new ParseSuccess<[any, any, any]>([value1, value2, value3],tresult.next);
                } else {
                    return new ParseFailer<any>(next + " is not match", input);
                }
            } else {
                return new ParseFailer<any>(next + " is not match", input);
            }
        } else {
            return new ParseFailer<any>(next + " is not match", input);
        }
    }
}

それからパーザ生成の関数を実装します。

export function bracket( fps: Parser<any>, sps: Parser<any>, tps: Parser<any>) {
    return new TripleParser(fps, sps, tps)
}

これでHello(world)のようなカッコで囲むものは以下のように判定できます。

    const str = "Hello(world)"
    const manySeqParser = ParserGen.seq(ParserGen.string("Hello"), ParserGen.bracket(ParserGen.string("("), ParserGen.string("world"), ParserGen.string(")")))
    console.info(manySeqParser.parse(str))

ParseSuccess {value: Array(2), next: ""} 実際に触ってみると、カッコなどで囲む前提の構文の場合は3つのパーざを組み合わせれるようにしたほうが扱いやすくなることが分かります。

Optionのパーザを実装する

Optionは以下のように実装します。

import {Parser} from './parser'
import {ParseResult, ParseSuccess, ParseFailer} from './parser-result'

export class OptionParser implements Parser<[any]> {
    ps: Parser<any>

    constructor(ps: Parser<any>) {
        this.ps = ps
    }

    parse(input: string) :ParseResult<any> {
        const psresult:ParseResult<any>  = this.ps.parse(input);
        if(psresult instanceof ParseSuccess) {
            const value1:ParseResult<any> = psresult.value
            return new ParseSuccess<any>(value1,psresult.next);    
        } else {
            return new ParseSuccess<any>(null,input);
        }
    }
}

それからパーザの生成関数を追加します。

export function option(parser: Parser<any>) {
    return new OptionParser(parser)
}

これで動作が確認できます。

    const str = "Hello!  world"
    const fParser = ParserGen.seq(ParserGen.string("Hello"), ParserGen.option(ParserGen.string("!")))
    const sParser = ParserGen.continues(ParserGen.string(" "))
    const tParser = ParserGen.seq(ParserGen.string("world"), ParserGen.option(ParserGen.string("!")))
    console.info(ParserGen.seq(ParserGen.seq(fParser, sParser), tParser).parse(str))

ParseSuccess {value: Array(2), next: ""}

複数のパーザから一致するのもで判定する

Orパーザを実装します。配列の中から最初にパースに成功したものを結果として返すようにします。

import {Parser} from './parser'
import {ParseResult, ParseSuccess, ParseFailer} from './parser-result'

export class OrParser implements Parser<[Array<any>]> {
    psArray: Array<Parser<any>>
    constructor(psArray: Array<Parser<any>>) {
        this.psArray = psArray
    }

    parse(input: string) :ParseResult<any> {
        for(const i in this.psArray) {
            const psresult = this.psArray[i].parse(input)
            if(psresult instanceof ParseSuccess) {
                return new ParseSuccess<any>(psresult.value, psresult.next);    
            }
        }
        return new ParseFailer<any>(null,input);
    }
}

それからパーザの生成関数を追加します。

export function or(psArray: Array<Parser<any>>) {
    return new OrParser(psArray)
}

これで動作が確認できます。

    const str = "{hello}"
    const parser1 = ParserGen.bracket(ParserGen.string("["), ParserGen.string("hello"), ParserGen.string("]"))
    const parser2 = ParserGen.bracket(ParserGen.string("{"), ParserGen.string("hello"), ParserGen.string("}"))
    const ps = ParserGen.or(new Array(parser1, parser2))
    console.info(ps.parse(str))

ParseSuccess {value: Array(3), next: ""}

全ての文字列を解析できたか判定できるようにする

現在は前方が一致していたらパース成功と判定しているので全ての文字列を解析し切れているかどうかを判定できるようにします。

export class EndParser implements Parser<any> {
    public constructor() {}
    parse(input: string):ParseResult<String> {
        if(input == ""){
            return new ParseSuccess(null, input);
        }
        return new ParseFailer("expected: end, actual: " + input, input);
    }
}

export function end() {
    return new EndParser()
}

それで動作を確認します。

    const str = "hello, world!"
    const parser1 = ParserGen.string("hello")
    const parser2 = ParserGen.seq(parser1, ParserGen.end())
    console.info(parser1.parse(str))
    console.info(parser2.parse(str))

ParseSuccess {value: "hello", next: ", world!"}
ParseFailer {message: ", world! is not match", next: "expected: end, actual: , world!"}

特定の文字に一致しないものを抽出する

要素の値やkeyなど任意の値をとるものについてはストップワードが見つかるまで取り出せるようにしたいと思います。

// 特定の文字列以外を読み込む
export class StopWordParser implements Parser<Array<string>> {
    stopWords: Array<string>;
    public constructor(stopWords: Array<string>) {
        this.stopWords = stopWords;
    }

    words(input:string):string {
        const indexs = this.stopWords
          .map(s=>{return Number(input.indexOf(s))})
          .filter(i=>{return i >= 0})
          .sort((a:number, b:number) => {return a - b})
        
        switch (indexs.length) {
          case 0:
           return input
          default:
            return input.substring(0, indexs[0])
        }
    }


    parse(input: string):ParseResult<String> {
        const muchString = this.words(input)
        if (muchString.length > 0 ){
            return new ParseSuccess(muchString, input.substring(muchString.length))
        } else {
            return new ParseFailer<any>(" much stop word: " + this.stopWords.toString(), input);    
        }
    }
}

パーサを生成できるようにします。

export function stop(stopWords: Array<string>) {
    return new StopWordParser(stopWords)
}

これで以下のように文字列の解析が行えるようになります。

    const str = "hello: ['world', '!', '!']"

    const sqParer = P.string("'")
    const sqStop = P.stop(new Array("'"))
    const coParer = P.string(":")
    const coStop = P.stop(new Array(":"))
    const spSeq = P.continues(P.string(" "))
    const cmParer = P.string(",")

    const wordParse = P.bracket(sqParer, sqStop, sqParer)

    const arrayParse = P.bracket(
      P.string("[")
      , P.option(P.seq(
          wordParse, 
          P.continues(P.seq(
            P.bracket(spSeq, cmParer, spSeq), 
            wordParse))))
      ,P.string("]")
    )
    const attributePaser = P.seq(P.seq(coStop, coParer), P.seq(spSeq, arrayParse))
    console.info(attributePaser.parse(str))

ParseSuccess {value: Array(2), next: ""}

どうにかパースできているようです。とりあえずいま実装した機能で頑張ればJSONのパースはできそうな気がします。