これは楽しいPEG.jsでパーサーづくり

javascriptで簡単にパーサーがつくれてしますみたいです。その名もPEG.js

ここで実際に使って実行もできてしまいます。

ということでそのサンプルコードをちょっと読んでみました。

/*
 * Simple Arithmetics Grammar
 * ==========================
 *
 * Accepts expressions like "2 * (3 + 4)" and computes their value.
 */

Expression
  = head:Term tail:(_ ("+" / "-") _ Term)* {
      var result = head, i;

      for (i = 0; i < tail.length; i++) {
        if (tail[i][1] === "+") { result += tail[i][3]; }
        if (tail[i][1] === "-") { result -= tail[i][3]; }
      }

      return result;
    }

Term
  = head:Factor tail:(_ ("*" / "/") _ Factor)* {
      var result = head, i;

      for (i = 0; i < tail.length; i++) {
        if (tail[i][1] === "*") { result *= tail[i][3]; }
        if (tail[i][1] === "/") { result /= tail[i][3]; }
      }

      return result;
    }

Factor
  = "(" _ expr:Expression _ ")" { return expr; }
  / Integer

Integer "integer"
  = [0-9]+ { return parseInt(text(), 10); }

_ "whitespace"
  = [ \t\n\r]*

簡単な四則演算のパーサーのようです。

基本は

型の名前 = マッチさせるパターン

です。

一番下から見てみましょう。

_ "whitespace"
  = [ \t\n\r]*

“_”をスペース文字にマッチさせているのがこの部分です。

=の後はregular expressionが来ます。
これで _ と書けば "スペース　\t \n \r が0個以上"にマッチします。

Integer "integer"
  = [0-9]+ { return parseInt(text(), 10); }

次は数字とプラス記号をIntegerと定義します。
ここではパターンの後に{…}で実行されるjavascriptを書いています。
その際マッチした文字をtext()で取得しています。

このようにマッチしたらjavascriptを実行できるのは便利ですね。

Factor
  = "(" _ expr:Expression _ ")" { return expr; }
  / Integer

次はFactorとして数字のInteger又はカッコに囲まれたExpression(この上で定義されている)にマッチします。
ここではマッチしたExpressionをexprと名付けて{}内のjavascriptでその名前を使っています。
これでカッコで囲まれたExpressionはカッコを取り除かれてかえってきます。

Expression
  = head:Term tail:(_ ("+" / "-") _ Term)* {
      var result = head, i;

      for (i = 0; i < tail.length; i++) {
        if (tail[i][1] === "+") { result += tail[i][3]; }
        if (tail[i][1] === "-") { result -= tail[i][3]; }
      }

      return result;
    }

Term
  = head:Factor tail:(_ ("*" / "/") _ Factor)* {
      var result = head, i;

      for (i = 0; i < tail.length; i++) {
        if (tail[i][1] === "*") { result *= tail[i][3]; }
        if (tail[i][1] === "/") { result /= tail[i][3]; }
      }

      return result;
    }

次はExpressionとTermです。
ここではhead: tail:と書いて最初に…最後に…というパターンを作っています。
まずはTermを見てみましょう。
head:Factor tail:(_ ("*" / "/") _ Factor)*
というパターンです。
最初にFactorがあり最後に　"スペース掛けるか割る記号スペース Factor が0個以上"ある時にマッチします。
そしてマッチした結果はtailに配列として格納されるので後の{}内でそれにあったjavascriptを実行します。
headには最初に来た数字かカッコ内の計算結果が入っているので

if (tail[i][1] === "*") { result *= tail[i][3]; }

このコードでもしtail配列の1番目が掛ける記号ならtail配列の3番目をheadに掛けることになります。

if (tail[i][1] === "/") { result /= tail[i][3]; }

これは同じく割算をします。

最後にExpressionはこの下で定義された全て(数字、カッコ内の計算結果、掛け算)をとって
それを足し算か引き算しその結果を返します。
これで簡単な計算機のパーサーができあがりました。