Home About Contact
Parser Combinator , TypeScript , Deno

「改善版2024）Kotlin でパーサーコンビネータを実装する HtmlWriter の導入」のコードを TypeScript にする（その１）

改善版2024）Kotlin でパーサーコンビネータを実装する HtmlWriter の導入で書いたコードを TypeScript に書きかえます。

環境

$ deno -version
deno 1.44.1

HtmlBlock の移植

Kotlin版 の HtmlBlock を どうのように TypeScript で表現するか？

元のコード(Kotlin)はこれ:

sealed class HtmlBlock {
    data class Just(val c: Char): HtmlBlock()
    object Nothing: HtmlBlock()
}

JavaScript や TypeScript には Char という型はないようなので、 ここでは、１文字を表す Moji という type を定義して、それを Kotlin の Char 相当と見なすことにします。

type Moji = { c: string }

c は string なので実際は１文字以上の文字列をセットすることができるのですが、 ここでは、c には１文字しか入れないこととします。

これで Char 型がない問題を解決したので、HtmlBlock を TypeScript で表現します。

type JustHtmlBlock = { m: Moji }
type NothingHtmlBlock = {}

type HtmlBlock = JustHtmlBlock | NothingHtmlBlock

HtmlBlock は JustHtmlBlock か NothingHtmlBlock である、と。 これで Koltin の sealed クラスの代用表現とします。

パーサー と HtmlWriter の定義

Kotlin版のパーサーの定義はこれ:

typealias Parser = (List<Char>)->HtmlWriter

data class ParseResult(val ok: Boolean, val xs: List<HtmlBlock>)

class HtmlWriter(val cs: List<Char>, val r: ParseResult) {
    constructor(cs: List<Char>): this(cs, ParseResult(true, listOf()))

    val parse:(Parser)->HtmlWriter = { p->
        val w = p(cs)
        HtmlWriter(w.cs, appendResult(this.r, w.r))
    }
}

TypeScript 版はこのようにしました。

type Parser = (ms: Moji[]) => HtmlWriter

type ParseResult = {
    ok: boolean
    xs: HtmlBlock[]
}

type HtmlWriter = {
    ms: Moji[]
    r: ParseResult
    parse: (p: Parser) => HtmlWriter
}

なんかいい感じです。わかりやすくなった。

htmlWriter 関数

Moji[] と ParserResult から HtmlWriter を作り出す関数 htmlWriter を用意。

const parseResult = (ok: boolean, xs: HtmlBlock[]): ParseResult => {
    return {ok: ok, xs: xs}
}

const htmlWriter = (ms: Moji[], r: ParseResult): HtmlWriter => {
    const appendResult = (r1: ParseResult, r2: ParseResult)=> {
        if( r1.ok && r2.ok ){
            return parseResult(true, r1.xs.concat(r2.xs))
        } else {
            return parseResult(false, r1.xs.concat(r2.xs))
        }
    }

    return {
        ms: ms,
        r: r,
        parse: (p: Parser): HtmlWriter => {
            const w = p(ms)
            return htmlWriter(w.ms, appendResult(r, w.r))
        }
    }
}

「改善版2024）kotlin でパーサーコンビネータを実装する HtmlWriter の導入」のコードを Vanilla JS に書きかえのコードをそのまま TypeScript に書きかえただけです。

Vanilla JS 版はこれ。型が記述されていないから内容を読み取るのが難しい。

const parseResult = (ok, xs)=> {
    return {ok: ok, xs: xs}
}

const htmlWriter = (cs, r)=> {
    const appendResult = (r1, r2)=>{
        if( r1.ok && r2.ok ){
            return parseResult(true, r1.xs.concat(r2.xs))
        } else {
            return parseResult(false, r1.xs.concat(r2.xs))
        }
    }

    return {
        cs: cs,
        r: r,
        parse: (p)=> {
            const w = p(cs)
            return htmlWriter(w.cs, appendResult(r, w.r))
        }
    }
}

letter パーサー

アルファベット１文字をパースするパーサー letter を定義。

補助関数を先に定義。

const ngHtmlWriter = (ms: Moji[]): HtmlWriter => {
    return htmlWriter(ms, parseResult(false, []))
}
const okHtmlWriter = (ms: Moji[], xs: HtmlBlock[]): HtmlWriter => {
    return htmlWriter(ms, parseResult(true, xs))
}

letter 関数。

const head = (ms: Moji[]): Moji => { return ms[0] }
const tail = (ms: Moji[]): Moji[] => { return ms.slice(1) }

type ToHtmlBlock = (m: Moji) => HtmlBlock

const letter = (toHtmlBlock: ToHtmlBlock): Parser=> {
    const re = /[a-zA-Z]/

    const p = (ms: Moji[]): HtmlWriter => {
        if( ms.length<1 ){
            return ngHtmlWriter(ms)
        } else {
            const m = head(ms)
            if( re.exec(m.c) ){
                return okHtmlWriter(tail(ms), [toHtmlBlock(m)])
            } else {
                return ngHtmlWriter(ms)
            }
        }
    }

    return p
}

Kotlin版 letter :

typealias ToHtmlBlock = (Char)->HtmlBlock

fun letter(toHtmlBlock: ToHtmlBlock): Parser {
    val p: Parser = { cs->
        if( cs.isEmpty() ){
            ngHtmlWriter(cs)
        } else {
            val c = cs.first()
            val matchResult = "[a-zA-z]".toRegex().find( "${c}" )
            if( matchResult!=null ){
                okHtmlWriter(cs.drop(1), listOf(toHtmlBlock(c)))
            } else {
                ngHtmlWriter(cs)
            }
        }
    }

    return p
}

ほぼ違いがない。

zeroOrMore パーサー

０回以上繰り返しパーサーを適用するパーサー zeroOrMore :

type Pair<T,R> = {
    first: T
    second: R
}

const zeroOrMore = (parser0: Parser): Parser=> {
    const f = (parser: Parser, ms: Moji[], acc: HtmlBlock[]): Pair<Moji[], HtmlBlock[]> => {
        if( ms.length==0 ){
            return { first: ms, second: acc }
        } else {
            const w = parser(ms)
            if( w.r.ok ){
                return f(parser, w.ms, acc.concat(w.r.xs))
            } else {
                return { first: ms, second: acc }
            }
        }
    }

    return (ms0: Moji[]): HtmlWriter => {
        const pair = f(parser0, ms0, [])
        return okHtmlWriter(pair.first, pair.second)
    }
}

TypeScript では tailrec 指定できない。 大きなテキストを処理すると、スタックオーバーフローになるのであろうか？

Kotlin版 zeroOrMore :

fun zeroOrMore(parser0: Parser): Parser {
    tailrec fun f(parser: Parser, cs: List<Char>, acc: List<HtmlBlock>): Pair<List<Char>, List<HtmlBlock>>{
        return if( cs.size==0 ){
            Pair(cs, acc)
        } else {
            val w: HtmlWriter = parser(cs)
            if( w.r.ok ){
                f(parser, w.cs, acc + w.r.xs)
            } else {
                Pair(cs, acc)
            }
        }
    }

    val p: Parser = { cs0->
        val (cs1, xs1) = f(parser0, cs0, listOf())
        okHtmlWriter(cs1, xs1)
    }

    return p
}

HelloWordl! をパース

const text = "HelloWorld!"

const toJustHtmlBlock: ToHtmlBlock = (m: Moji): HtmlBlock => {
    return { m: m }
}

const p = zeroOrMore( letter(toJustHtmlBlock) )

const mojiList = toMojiList(text)
const initParseResult = parseResult(true, [])
const result = htmlWriter(mojiList, initParseResult).parse( p )
console.log(result)

toMojiList 関数はこのポストの最後を参照。

実行する。

$ deno run --check --allow-read --allow-write main.ts
Check file:///home/moca/1019-ind-and-parser/parser-ts/main.ts
{
  ms: [ { c: "!" } ],
  r: {
    ok: true,
    xs: [
      { m: { c: "H" } },
      { m: { c: "e" } },
      { m: { c: "l" } },
      { m: { c: "l" } },
      { m: { c: "o" } },
      { m: { c: "W" } },
      { m: { c: "o" } },
      { m: { c: "r" } },
      { m: { c: "l" } },
      { m: { c: "d" } }
    ]
  },
  parse: [Function: parse]
}

できました。

letter が /a-zA-Z/ にマッチするだけなので最後の ! はパースされずに残ります。

まとめ

コード全体を掲載します。

// main.ts

const stringToArray = (text: string): string[] => { return Array.from(text) }
const head = (ms: Moji[]): Moji => { return ms[0] }
const tail = (ms: Moji[]): Moji[] => { return ms.slice(1) }

const toMojiList = (text: string): Moji[] => {
    return stringToArray(text).map((c: string)=> {
        const m: Moji = { c: c }
        return m
    })
}


type Moji = {
    c: string
}

type JustHtmlBlock = {
    m: Moji
}
type NothingHtmlBlock = {}

type HtmlBlock = JustHtmlBlock | NothingHtmlBlock


type Parser = (ms: Moji[]) => HtmlWriter

type ParseResult = {
    ok: boolean
    xs: HtmlBlock[]
}

type HtmlWriter = {
    ms: Moji[]
    r: ParseResult
    parse: (p: Parser) => HtmlWriter
}



const parseResult = (ok: boolean, xs: HtmlBlock[]): ParseResult => {
    return {ok: ok, xs: xs}
}

const htmlWriter = (ms: Moji[], r: ParseResult): HtmlWriter => {
    const appendResult = (r1: ParseResult, r2: ParseResult)=> {
        if( r1.ok && r2.ok ){
            return parseResult(true, r1.xs.concat(r2.xs))
        } else {
            return parseResult(false, r1.xs.concat(r2.xs))
        }
    }

    return {
        ms: ms,
        r: r,
        parse: (p: Parser): HtmlWriter => {
            const w = p(ms)
            return htmlWriter(w.ms, appendResult(r, w.r))
        }
    }
}

const ngHtmlWriter = (ms: Moji[]): HtmlWriter => {
    return htmlWriter(ms, parseResult(false, []))
}
const okHtmlWriter = (ms: Moji[], xs: HtmlBlock[]): HtmlWriter => {
    return htmlWriter(ms, parseResult(true, xs))
}


type ToHtmlBlock = (m: Moji) => HtmlBlock

const letter = (toHtmlBlock: ToHtmlBlock): Parser=> {
    const re = /[a-zA-Z]/

    const p = (ms: Moji[]): HtmlWriter => {
        if( ms.length<1 ){
            return ngHtmlWriter(ms)
        } else {
            const m = head(ms)
            if( re.exec(m.c) ){
                return okHtmlWriter(tail(ms), [toHtmlBlock(m)])
            } else {
                return ngHtmlWriter(ms)
            }
        }
    }

    return p
}

type Pair<T,R> = {
    first: T
    second: R
}

const zeroOrMore = (parser0: Parser): Parser=> {
    const f = (parser: Parser, ms: Moji[], acc: HtmlBlock[]): Pair<Moji[], HtmlBlock[]> => {
        if( ms.length==0 ){
            return { first: ms, second: acc }
        } else {
            const w = parser(ms)
            if( w.r.ok ){
                return f(parser, w.ms, acc.concat(w.r.xs))
            } else {
                return { first: ms, second: acc }
            }
        }
    }

    return (ms0: Moji[]): HtmlWriter => {
        const pair = f(parser0, ms0, [])
        return okHtmlWriter(pair.first, pair.second)
    }
}


const text = "HelloWorld!"

const toJustHtmlBlock: ToHtmlBlock = (m: Moji): HtmlBlock => {
    return { m: m }
}

const p = zeroOrMore( letter(toJustHtmlBlock) )

const mojiList = toMojiList(text)
const initParseResult = parseResult(true, [])
const result = htmlWriter(mojiList, initParseResult).parse( p )
console.log(result)

以上です。