Parser 0.1

囲碁の棋譜フォーマット SGF の構文解析処理 (parsing / syntactic analysis) を作る前段階として、 前回作成した字句解析 (lexical analysis) のクラス Lex を利用した、簡単な数式の構文解析のクラス Parser を作成し、 単体テストのフレームワーク Jasmine によりテストしてみました。

実数の四則演算を EBNF (Extended Backus–Naur Form) の構文で書き表すと以下のようになります。 EBNF では、= は定義、, は連結、| は選択、. は終端、() はグループ化、[] は省略可能、{} は0回以上の繰り返しを表します。 

expression = term, {('+' | '-'), term}.
term = factor, {('*' | '/'), factor}.
factor = ('(', expression, ')') | real | integer.
real = ((integer, '.') | ('.', digit)), {digit}.
integer = ['-'], digit, {digit}.
digit = '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'.
今回はこの構文をもとに構文解析プログラム (parser) を作り簡単なキーボード入力式の電卓を作成しました。

実行結果

Calculator

ドキュメント

JsDoc Toolkit で作成したドキュメントはこちら。

ソース

今回使用している HTML と JavaScript のソースコードです。

parsertest01.html

このソースコードは Jasmine のサンプル SpecRunner.html から大部分を持ってきました。前半はスタイルシートとスクリプトを読み込んでいる部分です。 
<head>
<meta charset="UTF-8">
<title>JavaScriptでプログラミング - Parser 0.1</title>

<link type="text/css" rel="stylesheet" href="lib/jasmine-1.3.1/jasmine.css">
<link type="text/css" rel="stylesheet" href="css/spec.css">
<link type="text/css" rel="stylesheet" href="css/shCoreEclipse.css">
<link type="text/css" rel="stylesheet" href="css/shThemeEclipse.css">
<script type="text/javascript" src="js/XRegExp.js"></script>
<script type="text/javascript" src="js/shCore.js"></script>
<script type="text/javascript" src="js/shBrushJScript.js"></script>
<script type="text/javascript" src="js/shBrushXml.js"></script>
<script type="text/javascript" src="js/shBrushCss.js"></script>
<script type="text/javascript" src="lib/jasmine-1.3.1/jasmine.js"></script>
<script type="text/javascript" src="lib/jasmine-1.3.1/jasmine-html.js"></script>

<!-- include source files here... -->
<script type="text/javascript" src="js/parser01/source01.js"></script>
<script type="text/javascript" src="js/parser01/lex02.js"></script>
<script type="text/javascript" src="js/parser01/parser01.js"></script>

<!-- include spec files here... -->
<script type="text/javascript" src="js/parser01/lexspec02.js"></script>
<script type="text/javascript" src="js/parser01/parserspec01.js"></script>
後半は Jasmine によるテスト結果を HTML 上で展開するレポーターと呼ばれる部分です。前回から変更ありません。 
<script type="text/javascript">
  SyntaxHighlighter.all();
  (function() {
    var jasmineEnv = jasmine.getEnv();
    jasmineEnv.updateInterval = 1000;

    var htmlReporter = new jasmine.HtmlReporter();
    jasmineEnv.addReporter(htmlReporter);
    jasmineEnv.specFilter = function(spec) {
      return htmlReporter.specFilter(spec);
    };

    var currentWindowOnload = window.onload;
    window.onload = function() {
      if (currentWindowOnload) {
        currentWindowOnload();
      }
      execJasmine();
    };

    function execJasmine() {
      jasmineEnv.execute();
    }

  })();
</script>

parser01.js

クラス Expression のソースコードです。数式の構文解析を行うパーサーです。クラス Lex を継承しています。 リンク先をご覧下さい。

lex02.js

クラス Lex のソースコードです。字句解析のためのツールです。クラス Source を継承しています。 リンク先をご覧下さい。

source01.js

クラス Source のソースコードです。字句解析クラス Lex よりソースバッファの管理部分を独立させました。 リンク先をご覧下さい。

lexspec02.js

このソースでは Lex のテスト仕様を定義しています。Jasmine のサンプル PlayerSpec.js を参考にしています。今回メソッド sp, sq のテストを追加しました。 
describe("Lex 仕様 0.2", function() {
  var exp = "1+2=";
  var la;

  beforeEach(function() {
    la = new Lex(exp);	// Lexical Analiser
  });

  it("eod() は false を返す", function() {
    expect(la.eod()).toBeFalsy();
  });

  it("digit() は '1' を返す", function() {
    expect(la.digit()).toEqual('1');
  });

  it("upper() は null を返す", function() {
    expect(la.upper()).toBe(null);
  });

  it("lower() は null を返す", function() {
    expect(la.lower()).toBe(null);
  });

  it("sp() は null を返す", function() {
    expect(la.sp()).toBeFalsy();
  });

  it("sq() は null を返す", function() {
    expect(la.sq()).toBeFalsy();
  });

  it("ch('1') は '1' を返す", function() {
    expect(la.ch('1')).toEqual('1');
  });

  describe("3文字読んだ時点で、", function() {
    beforeEach(function() {
      la.rewind();
      la.digit();
      la.ch('+');
      la.digit();
    });

    it("eod() は false を返す", function() {
      expect(la.eod()).toBe(false);
    });

    it("digit() は null を返す", function() {
      expect(la.digit()).toBe(null);
    });

    it("upper() は null を返す", function() {
      expect(la.upper()).toBe(null);
    });

    it("lower() は null を返す", function() {
      expect(la.lower()).toEqual(null);
    });

    it("ch('=') は '=' を返す", function() {
      expect(la.ch('=')).toBe('=');
    });

  });

  describe("4文字読んだ時点で、", function() {
    beforeEach(function() {
      la.rewind();
      la.digit();
      la.ch('+');
      la.digit();
      la.ch('=');
    });

    it("eod() は true を返す", function() {
      expect(la.eod()).toBeTruthy();
    });

  });

});

parserspec01.js

このソースでは Parser のテスト仕様を定義しています。 
describe("Parser 仕様 0.1", function() {
 
  it("Expression(\"2-1\").expression() は 1 を返す", function() {
    var e = new Expression("2-1");
    expect(e.expression()).toEqual(1);
  });

  it("Expression(\"1.5+2.4\").expression() は 3.9 を返す", function() {
    var e = new Expression("1.5+2.4");
    expect(e.expression()).toEqual(3.9);
  });

  it("Expression(\"123*56\").expression() は 6888 を返す", function() {
    var e = new Expression("123*56");
    expect(e.expression()).toEqual(6888);
  });

  it("Expression(\"91/2\").expression() は 45.5 を返す", function() {
    var e = new Expression("91/2");
    expect(e.expression()).toEqual(45.5);
  });

  it("Expression(\"2.-1\").expression() は 1 を返す", function() {
    var e = new Expression("2.-1");
    expect(e.expression()).toEqual(1);
  });

  it("Expression(\"1+1\").expression() は 2 を返す", function() {
    var e = new Expression("1+1");
    expect(e.expression()).toEqual(2);
  });

  it("Expression(\"3-1+2\").expression() は 4 を返す", function() {
    var e = new Expression("3-1+2");
    expect(e.expression()).toEqual(4);
  });

  it("Expression(\"(3-1+2\").expression() は null を返す", function() {
    var e = new Expression("(3-1+2");
    expect(e.expression()).toEqual(null);
  });

  it("Expression(\"3-1+2\").term() は 3 を返す", function() {
    var e = new Expression("3-1+2");
    expect(e.term()).toEqual(3);
  });

  it("Expression(\"3*1/2\").term() は 1.5 を返す", function() {
    var e = new Expression("3*1/2");
    expect(e.term()).toEqual(1.5);
  });

  it("Expression(\"(3-1+2\").term() は null を返す", function() {
    var e = new Expression("(3-1+2");
    expect(e.term()).toEqual(null);
  });

  it("Expression(\"(2-1)*2\").factor() は 1 を返す", function() {
    var e = new Expression("(2-1)*2");
    expect(e.factor()).toEqual(1);
  });

  it("Expression(\"(2.-1)*2\").factor() は 1 を返す", function() {
    var e = new Expression("(2.-1)*2");
    expect(e.factor()).toEqual(1);
  });

  it("Expression(\"(-2.-1)*2\").factor() は -3 を返す", function() {
    var e = new Expression("(-2.-1)*2");
    expect(e.factor()).toEqual(-3);
  });

  it("Expression(\"(-2.-1*2\").factor() は null を返す", function() {
    var e = new Expression("(-2.-1*2");
    expect(e.factor()).toEqual(null);
  });

  it("Expression(\"3.5-1+2\").real() は 3.5 を返す", function() {
    var e = new Expression("3.5-1+2");
    expect(e.real()).toEqual(3.5);
  });

  it("Expression(\".5-1+2\").real() は .5 を返す", function() {
    var e = new Expression(".5-1+2");
    expect(e.real()).toEqual(.5);
  });

  it("Expression(\"-2.-1+2\").real() は -2. を返す", function() {
    var e = new Expression("-2.-1+2");
    expect(e.real()).toEqual(-2.);
  });

  it("Expression(\"2.\").real() は 2. を返す", function() {
    var e = new Expression("2.");
    expect(e.real()).toEqual(2.);
  });

  it("Expression(\"..3-1+2\").real() は null を返す", function() {
    var e = new Expression("..3-1+2");
    expect(e.real()).toEqual(null);
  });

  it("Expression(\"1.5+2\").integer() は 1 を返す", function() {
    var e = new Expression("1.5+2");
    expect(e.integer()).toEqual(1);
  });

  it("Expression(\".5+2\").integer() は null を返す", function() {
    var e = new Expression(".5+2");
    expect(e.integer()).toEqual(null);
  });

});

テスト結果