ABNF Parser の実装

token

最も基本的な、パターン(正規表現)を受け取ったら、そのパターンを文字列の先頭から取り出し、結果を返す形が以下のようになる。

const ok = true

// a => token(/^a/)
export function token(reg) {
  return (rest) => {
    const result = reg.exec(rest)
    if (result === null) {
      return {ok: false, rest}
    } else {
      const value = result[0]
      return {ok, value, rest: rest.substr(value.length)}
    }
  }
}

使い方はこうなる。

token(/^a/)("abcde")
// { ok: true, value: 'a', rest: 'bcde' }

このパターンを変えることで、一番基本の部分 (ALPHA / DIGIT) などはこれを用いて実装できる。

// ALPHA = A-Z / a-z
const alpha = token(/^[a-zA-Z]/)

// DIGIT = "0"/"1"/"2"/"3"/"4"/"5"/"6"/"7"/"8"/"9"
const digit = token(/^[0-9]/)

alt

ABNF における Alternatives (OR) は以下のように使われる。

BIT  =  "0" / "1"

実装は以下のようになる。

// (a / b) => alt([a(), b()])
export function alt(fns) {
  return (rest) => {
    for (let i = 0; i < fns.length; i ++) {
      const result = fns[i](rest)
      if (result.ok) {
        return result
      }
    }
    return {ok: false, rest}
  }
}

これは、先の token() のような高階関数のリストを受け取り、最初に成功したところで終了している。

// ALPHA / DIGIT
const alpha_digit = alt([alpha, digit])
alpha_digit("aaa")
// { ok: true, value: 'aaa', rest: '' }
alpha_digit("111")
// { ok: true, value: '111', rest: '' }
alpha_digit("?")
// { ok: false, rest: '?' }

list

複数の token が順番に並ぶように合成する際に利用する。

CRLF  =  CR LF

実装は以下。

// (a b c) => list([a(), b(), c()])
export function list(fns) {
  return (rest) => {
    const value = []
    const orig  = rest
    for (let i = 0; i < fns.length; i ++) {
      const result = fns[i](rest)
      if (result.ok === false) {
        return {ok: false, rest: orig}
      }
      value.push(result.value)
      rest = result.rest
    }
    return {ok, value, rest}
  }
}

使い方は以下。

// CRLF  =  CR LF
const crlf = list([token(/\r/), token(/\n/)])
crlf("\r\n")
// { ok: true, value: [ '\n', '\r' ], rest: '' }

repeat

ABNF の繰り返しは以下のように使われる。

NUMBER = 1*DIGIT

• 1* は 1 回以上
• 1*10 は 1 回以上 10 回未満

といった具合だ。これを 0 回以上 1 回未満とみなせば、 Optional も手に入る。

実装は以下のようになる。

// *(a b) => repeat(0, Infinity, list([a(), b()]))
export function repeat(min, max, fn) {
  return (rest) => {
    const value = []
    const found = 0
    const orig  = rest
    while(true) {
      const result = fn(rest)
      if (result.ok) {
        value.push(result.value)
        rest = result.rest
        if (value.length === max) break
      } else {
        break
      }
    }

    if (value.length < min) {
      return {ok: false, rest: orig}
    } else {
      return {ok, value, rest}
    }
  }
}

使い方はこうだ。

(仕様上上限がなくても、実装上適当な上限を指定する)。

// NUMBER = 1*DIGIT
const number = repeat(1, 1024, digit)

number("0123")
// { ok: true, value: [ '0', '1', '2', '3' ], rest: '' }

ABNF 実装

token(), list(), alt(), repeat() があると、あとはこれを組み合わせていくだけだ。

例えば最初の Structured Filed Values の一例の場合

sf-list       = list-member *( OWS "," OWS list-member )
list-member   = sf-item / inner-list

こんな感じになる。

const sf_list = list([
  list_member(),
  repeat(0, 1024, list([
    ows(),
    token(/,/),
    ows(),
    list_member()
  ]))
])

const list_member = alt([
  sf_item,
  inner_list
])

これを書き下していきながら、一番下層の token() まで実装しきれば、パース自体はできあがる(実際には下から書くが)。

あとはパースしながら、例えば数字を parseInt() したり、 Dict を Map や Object に詰めたり、多少の最適化(CRLF = CR / LF を token(/\r\n/) にする)などを適宜入れる、などの処理を間にはさみながら組み上げれば良い。

組み上げた結果は、以下のようになる。

• Jxck/structured-field-values
  • https://github.com/Jxck/structured-field-values/blob/master/bnf/bnf.js

こうした処理を高度に抽象化したものがツールとして提供されていたりもするが、この考え方だけ覚えておけば、どんな言語でも RFC の ABNF 程度であれば実装が可能になるだろう。

そして、この実装の過程で処理ができない ABNF が出てくれば、そこで ABNF 側のバグを見つけることができるというわけだ。この実装によって見つかった SFV の Issue もある。