Jison入門!!! - プログラムモグモグ

最近, Jisonを使おうとしている人をちらほら見るので, ちょっと入門的なやつを書いてみる.

定義(てけとー

Jisonというのは, JavaScriptで書かれたパーサーを吐くことができる, パーサジェネレーターの一つ

現在Jisonは https://github.com/zaach/jison で入手可能です.

色々説明したいけど, 構文解析とかLALRとか説明しだしたら, ~~ボロが出る~~難しいので, ...

取り敢えずJisonのexampleを試してみよう!!!

まずは, narwhalをインストールしましょう

https://github.com/280north/narwhal
から落として, PATHを通す.
narwhalと叩いてJavaScriptのインタラクティブな環境が立ち上がったら多分OK.
(というかnarwhalの詳しいことは僕はよく分からない...)

Jisonのgitリポジトリをローカルにcloneしよう!

$ git clone git://github.com/zaach/jison.git
$ cd jison/

(git入れてなくてもzipで落として解凍すれば使えるよ)

exampleフォルダがあるので, 早速, 試してみよう.

$ cd example/
$ cat calculator.jison

/* description: Parses end executes mathematical expressions. */

/* lexical grammar */
%lex
%%

\s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?\b  return 'NUMBER'
"*"                   return '*'
"/"                   return '/'
"-"                   return '-'
"+"                   return '+'
"^"                   return '^'
"!"                   return '!'
"%"                   return '%'
"("                   return '('
")"                   return ')'
"PI"                  return 'PI'
"E"                   return 'E'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

/* operator associations and precedence */

%left '+' '-'
%left '*' '/'
%left '^'
%right '!'
%right '%'
%left UMINUS

%start expressions

%% /* language grammar */

expressions
    : e EOF
        { typeof console !== 'undefined' ? console.log($1) : print($1);
          return $1; }
    ;

e
    : e '+' e
        {$$ = $1+$3;}
    | e '-' e
        {$$ = $1-$3;}
    | e '*' e
        {$$ = $1*$3;}
    | e '/' e
        {$$ = $1/$3;}
    | e '^' e
        {$$ = Math.pow($1, $3);}
    | e '!'
        {{
          $$ = (function fact (n) { return n==0 ? 1 : fact(n-1) * n })($1);
        }}
    | e '%'
        {$$ = $1/100;}
    | '-' e %prec UMINUS
        {$$ = -$2;}
    | '(' e ')'
        {$$ = $2;}
    | NUMBER
        {$$ = Number(yytext);}
    | E
        {$$ = Math.E;}
    | PI
        {$$ = Math.PI;}
    ;


$ narwhal ../bin/jison ./calculator.jison

jisonに, calculator.jisonファイルを渡してあげると, calculator.jsファイルが同じディレクトリに出来ます

calculator.js , できたかな?

$ cat calculator.js
/* Jison generated parser */
var calculator = (function(){
var parser = {trace: 
function trace() {
}
,
yy: {},
#####   省略   #####

$ narwhal calculator.js
Error: Usage: calculator.js FILE

ああ, ファイルを指定するのか...

$ echo '100 * (1 + 2)' > caltest.txt
$ narwhal calculator.js caltest.txt
300
$ echo '10!' > caltest.txt
$ narwhal calculator.js caltest.txt
3628800

(∩´∀｀)∩ﾜｰｲ
取り敢えず, これ (calculator.jison) が動いたら, Jisonが使えるんじゃないかって思えてくる, よね!!!

ん, まぁコンソールでは動く事, 分かったけど...

Jisonの吐いたJavaScriptファイルをHTMLで使いたいんだけど

大丈夫!!!

ちょっとテストを書いてみましょう

先ほどのcalculator.jsと同じところにcalculator.htmlとして次のように書いてみます

<!DOCTYPE HTML> 
<html lang="en"> 
<head> 
  <meta charset="UTF-8"> 
  <title>jisonによる計算機</title> 
  <script src="./calculator.js" type="text/javascript"></script> 
  <script type="text/javascript"> 
    onload = function () {
      var exprTextArea = document.getElementById('expression'),
          resultTextArea = document.getElementById('result'),
          expr,
          ans;
      exprTextArea.addEventListener('keydown', function () {
        setTimeout(function () {
          expr = exprTextArea.value;
          try {
            ans = calculator.parse(expr);          //  ←←  ここ重要だから覚えておきな!!!!
            resultTextArea.innerText = ans;
          } catch (e) {
            resultTextArea.innerText = e;
          }
        }, 20);
      });
    }
  </script> 
</head> 
<body> 
  <textarea id="expression" rows="20" cols="50"></textarea> 
  <textarea id="result" rows="20" cols="50"></textarea> 
  <br /> 
  数式を入れてください
</body> 
</html>

ブラウザーで開いてみて, 左のtextareaに書いた式の結果がちゃんと計算できてたらOK.

fc2の方にもサンプルをアップしておくよ!
http://itchyny.web.fc2.com/calculator/

わーい, たのしぃーー!!!

構文解析は???

計算機ができたのはいいけど, 計算木も作りたいよね ← !!!

ってことで, こういうふうに書いてみるよ!

$ cat calculator2.jison

%lex
%%

\s+                   /* skip whitespace */
[0-9]+("."[0-9]+)?\b  return 'NUMBER'
"*"                   return '*'
"/"                   return '/'
"-"                   return '-'
"+"                   return '+'
"^"                   return '^'
"!"                   return '!'
"%"                   return '%'
"("                   return '('
")"                   return ')'
"PI"                  return 'PI'
"E"                   return 'E'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

/* operator associations and precedence */

%left '+' '-'
%left '*' '/'
%left '^'
%right '!'
%right '%'
%left UMINUS

%start expressions

%% /* language grammar */

expressions
    : e EOF { return $1; }
    ;

e
    : e '+' e            {$$ = new Add($1, $3);}
    | e '-' e            {$$ = new Sub($1, $3);}
    | e '*' e            {$$ = new Mul($1, $3);}
    | e '/' e            {$$ = new Div($1, $3);}
    | e '^' e            {$$ = new Pow($1, $3);}
    | e '!'              {$$ = new Factorial($1);}
    | e '%'              {$$ = new Percentage($1);}
    | '-' e %prec UMINUS {$$ = new Minus($2);}
    | '(' e ')'          {$$ = $2;}
    | NUMBER             {$$ = Number ($1);}
    | E                  {$$ = E;}
    | PI                 {$$ = PI;}
    ;

$ narwhal ../bin/jison/ ./calculator2.jison
$

すぐに計算しちゃわずに, オブジェクトを作るんだよ!
例えば,

function Add (x, y) { this.left = x; this.right = y; }

みたいに定義しておくと, 左辺と右辺が入るよ!

で, オブジェクトが返ってくるから, 再帰でぐるぐる回ってみたらいいんじゃないかな!!
ってことで, サンプルはこちら↓
http://itchyny.web.fc2.com/calculator2/

ちょっと説明を加えておくよ

hoge.jisonをjisonで処理すると, hoge.jsファイルができるよ
その中の, hoge.parse関数を使うよ
jisonファイルに書く, %startに注意. パースはここから始まるよ
"{ $$ = ... ;}" を省略すると, $1の値がフォールするよ (多分
トークンを読み込むための｢正規表現｣が特徴ある形だから, サンプルを参考にしたほうがいいよ

jsparser

JisonはCoffeeScriptの処理系にも使われてるくらいだから, 色々できるんだよ!!!

自分がJisonで, (二ヶ月ほど前に) 作ったものは, これ↓
http://itchyny.web.fc2.com/jsparser/

JavaScriptのパーサーも作れちゃうんだね!!! *1

みんなもJisonで遊んでみよう!!!

楽しいですよ!!! よ! よ! ＞ω＜ﾉｼ

*1:実は, 正規表現周りでサボっているところがあって, var x = 1 / 2 / 3; みたいな式が処理できませんorz. でも, セミコロン挿入の処理は割と頑張ったから, それで燃え尽きた.