snake parser

snake parser は JavaScript 製のパーサジェネレータです。 構造を持ったテキストを入力として JavaScript 上でデータを得たいときに使用します。 データとは、文字列や数値、オブジェクト、配列等で構成された構造的な値を指します。 テキストからデータを取り出すためには、どのように取り出すかを記述した文法が必要です。 snake parser は文法を入力として、パースするための JavaScript コード(パーサ)を出力します。 パーサはjsファイルに書き出して使用できます。

ブラウザ上で試すことができます。
https://carrotflakes.github.io/snake-parser/

特徴

• データをどのように取り出すかを文法の中に自然に記述可能
• Packrat パーサの一種
• 左再帰をそのまま表現可能(ただし、使うと遅い)

npm install

あなたのアプリケーションで snake parser が生成したパーサを使用したい場合はグローバルインストールをしてください。 もし、アプリケーションの実行時に snake parser を使用したい場合はローカルインストールをしてください。

グローバルインストール

% npm install -g snakeparser

ローカルインストール

$ cd your/project
$ npm install snakeparser

snakeparser コマンド

グローバルインストール後、 snakeparser コマンドが使用可能になります。以下のように使用します。

$ snakeparser [文法ファイル [出力パス]]

文法ファイルは文法を記述したテキストファイルです。出力パスに JavaScript コードが生成されます。 出力パスを省略すれば、文法ファイルの拡張子を .js にしたものが出力パスに設定されます。 また文法ファイルと出力パスを両方省略すれば標準入力から文法を受け取って標準出力からコードを出力するようになります。 出力コードの内容は、変数 module.export への関数の代入になります。 snakeparser コマンドにオプションとして --export-var 変数名 (または -e 変数名)を与えると、代入する変数名を変更できます。

JavaScript API

以下は、 Node.js 内で snake parser を使用する例です。

var SnakeParser = require('snakeparser');

// Your grammar
var grammar = 'start = `+("a" | "b")';

// Build parser
var parserSource = SnakeParser.buildParser(grammar);
var parser = eval(parserSource);

// Use parser
console.log(parser("abab"));
// => abab

require('snakeparser') によって得られたオブジェクトは buildParser 関数を持っています。 buildParser 関数は文法を入力すると、パーサのソースコードを文字列として返します。 eval でソースコードを評価して、パーサを関数として取得してください。

得られたパーサは文字列を入力としてパースし、文法で規定された返り値を返します。 パースに失敗した場合はエラーを throw します。

文法

基本

文法は以下のように記述します。

// 初期化コード
{
    ...
}

// ルールの定義
start = rule1

rule1 "rule" = ...

rule2<x, y> = ...

最初に初期化コードを定義します。 初期化コードはパーサに直接埋め込まれる JavaScript のコードです。 パースを行うたびに最初に実行され、そこで宣言した変数や関数はルール内の JavaScript を実行する過程で参照できます。 初期化コードが不要であれば {} ごと省略することができます。
次にルールを ルール名 ["エラー名"] = パージング表現 の形で定義します。 ルールは初期化コードより下に記述して下さい。 ルール名は [a-zA-Z_][a-zA-Z0-9_]* の正規表現を満たすものが使えます。 エラー名はパースが失敗したときに、どこで失敗したのかを通知するために使われます。エラー名は省略可能です。 ルール名 <引数1, 引数2, ...> = ... のようなルールは引数付きルールと呼ばれます。詳しくは後述します。 start は最初に呼び出されるルールです。必ず定義して下さい。 文法記述の中では JavaScript のように、//, /* */でコメントを書き込むこともできます。
文法内の JavaScript コードでは、この文書で許可していない $ を含む変数名を使用しないで下さい。パーサ内で使用されている変数と衝突する可能性が有ります。
初期化コードや一部のパージング表現で使われる JavaScript コード内では、文字列やコメントの中も含めて { と } が正しく対応していなければいけません。例えば、{ return "}"; } はエラーになります。

パージング表現

パージング表現とはどのようにパースするかを指示するものです。 パージング表現には入力文字列を消費したり、返り値（データ）を返す機能があります。 また、パージング表現によっては失敗することもあります。 以下がパージング表現のすべてです。

マッチング

'A' "A"

文字列 A と入力文字列を比較します。一致すればその文字列分、入力文字列を消費して成功になります。一致しなければ失敗です。

[A]

文字の集合を表します。 [] で囲まれた文字のいずれかと入力文字列が一致すれば成功です。入力文字列は1文字消費されます。 例えば、 [abcd] は a b c d の入力で成功します。 また [abcd] のように文字コードが連続している場合、 [a-d] と書くことが可能です。

[^A]

[A] の否定です。 [^abcd] は a b c d 以外の入力で成功します。

.

任意の1文字を消費して成功します。ただし、入力文字列が空の場合失敗になります。

量化

?A

パージング表現 A でのパースを試行します。パースに成功しても失敗しても ?A は成功です。

*A

パージング表現 A を失敗するまで繰り返します。*A は必ず成功します。

+A

パージング表現 A を失敗するまで繰り返します。１回以上成功しないと +A は失敗になります。

n*A

n は0以上の数値です。 A を n 回繰り返したものと同値です。

n,m*A

n、 m は 0 <= n <= m を満たす数値です。 パージング表現 A を失敗するまで最大 m 回繰り返します。成功回数が n 以上ならばこのパースは成功です。

制御

A

ルール A のパージング表現を呼び出します。

A<X, Y, ...>

引数付きルール A を参照します。

&A

パージング表現 A でパースします。パースに成功しても、それによる入力文字列の消費をキャンセルします。 一般に肯定先読みと呼ばれます。

!A

パージング表現 A でパースを試み、成功すれば !A は失敗です。失敗すれば !A は成功になります。 A による入力文字列の消費はありません。 一般に否定先読みと呼ばれます。

A|B

パージング表現 A でパースします。A が失敗ならば、 パージング表現 B でパースします。

A B

パージング表現 A でパースします。A が成功すれば、次にパージング表現 B でパースします。

(...)

括弧の中をひとまとまりに扱います。

返り値

`A

A で消費した文字列を返り値とします。

{...}

括弧内の A:B や A:=B をプロパティとするオブジェクトを返り値にします。

A:B "A":B

{...} によってオブジェクトが作られるとき、パージング表現 B の返り値を、文字列 A をキーとしてオブジェクトに格納します。B の返り値がない場合、undefined が格納されます。

A:=B "A":="B"

{...} によってオブジェクトが作られるとき、文字列 B を、文字列 A をキーとしてオブジェクトに格納します。

@A

パージング表現 A の中では複数の返り値を返すことが可能です。その複数の返り値を1つの配列として返り値にします。

A->M

M は JavaScript の関数名です。パージング表現 A の返り値を関数 M に与えた結果を返り値とします。関数は初期化コード内で宣言された関数とトップレベルで宣言されている関数が使用できます。
関数 M 内では、与えられたオブジェクトあるいは配列が同一ルール内で生成されたものではない場合、変更を加えてはいけません。例えば、次のような場合は意図しない結果になる可能性が有ります。

{
  function baz(obj) {
    obj.bar += "!";
    return obj;
  }
}
start = foo -> baz fail | foo -> baz
foo = { bar:=yo }
fail = []

A->{C}

C は JavaScript の関数のボディ部分です。 function($) {C} のような関数が存在するとして、パージング表現 A の返り値をその関数に与えた結果を返り値とします。
e.g. A->{return parseInt($);}
A->M と同様に、オブジェクトあるいは配列への変更に注意してください。

A-?M

M は JavaScript の関数名です。パージング表現 A の返り値を関数 M に与えた結果が偽と評価されるとき A-?M は失敗になります。関数は初期化コード内で宣言された関数とトップレベルで宣言されている関数が使用できます。関数内では、与えられたオブジェクトあるいは配列に変更を加えてはいけません。

A-?{C}

C は JavaScript の関数のボディ部分です。 function($) {C} のような関数が存在するとして、パージング表現 A の返り値をその関数に与えた結果が偽と評価されるとき A-?{C} は失敗になります。C 内では、与えられたオブジェクトあるいは配列に変更を加えてはいけません。

A-|

パージング表現 A の返り値を捨てます。

~A

パージング表現 A の返り値を文字列として結合します。言い換えれば、@A -> {return $.join("");} と等価です。

\V

V は Number, String, Boolean, null, Array, Object で構成される JavaScript の値です。V がそのまま返り値になります。
e.g. \123 \"Hello" \true \null \[1,2,3] \{a: 1, b: 2}

$input $pos $row $column

これらのパージング表現はそれぞれ、入力文字列、現在のパース位置、現在のパース位置の行番号(0からはじまる番号)、現在のパース位置の列番号(1からはじまる番号)を返します。

Note: $row および $column は計算コストがかかるため、$pos で代用することを推奨します。

引数付きルール

ルール名の後に <Prm1[, Prm2 ...]> と書くと、そのルールは引数付きルールになります。 Prm1, Prm2 はルール名と同じ命名規則の識別子です。 引数付きルールの参照は Rule<Arg1[, Arg2 ...]> のように書きます。Arg1, Arg2 はパージング表現です。
引数付きルールとは、例えるなら関数のようなものです。 twice<arg> = arg arg のようなルールのボディ部分では arg というルールが参照可能です。 arg はその引数付きルールの参照によって変わります。 twice<"こんにちは"> と参照すれば arg はパージング表現 "こんにちは" になります。 つまり、twice<"こんにちは"> は "こんにちは" "こんにちは" と同値になります。
引数付きルールは再帰可能です。 a<x> = "!" ?a<x> のように定義することができます。 a<x> = "!" ?<"-"x> のように、再帰するごとに x が変化していくものは宣言できません。 再帰する引数付きルールを特に再帰引数付きルールと呼びます。

文法記述例

次の文法は + と * と () と整数で構成された数式を計算します。 (1+2)*3 を入力すると 9 が出力されます。

{
  function additive($) {
    return $.left + $.right;
  }
  function multiplicative($) {
    return $.left * $.right;
  }
  function integer($) {
    return +$;
  }
}

start
  = additive

additive
  = {
      left:multiplicative
      "+"
      right:additive
    } -> additive
  | multiplicative

multiplicative
  = {
      left:primary
      "*"
      right:multiplicative
    } -> multiplicative
  | primary

primary
  = integer
  | "(" additive ")"

integer "integer"
  = `+[0-9] -> integer