レガシーコード生産ガイド

私に教えられることなら

再帰下降構文解析の練習

githubのアカウントとリポジトリを作ってみた

phaendal/making-script-engine · GitHub

構文解析器生成器、を作ろうとしたけど、まったくイメージがわかない、というかわかってないことがわかったので、まずは手で再帰下降構文解析をしてみることにした。簡単なものから、ということでただの四則演算。

その前に使いやすい様に字句解析のときのコードをライブラリにした。

JavaScriptで字句解析 - レガシーコード生産ガイド

これを

making-script-engine/LexerGenerator.js at b42f486c3e73bec1a94980659b10b2fd762f5b62 · phaendal/making-script-engine · GitHub

こう。 これで少しは使いやすくなった。

var LexerGenerator  = require('./LexerGenerator.js');

var TOKENS = [
    { type: "SPACES",    re: "\\s+" }, 
    { type: "L-PAREN",   re: "\\\(" },
    { type: "R-PAREN",   re: "\\\)" },
    { type: "NUMBER",    re: "-?[0-9]+"},
    { type: "BINOP",     re: "\\+|-|\\*|\\/" }
];

var tokens,
    lexer = LexerGenerator(TOKENS, {
        usible_token_from: 2
    });

//lexer.clear();
tokens = lexer.parse(contents);

このように使う。

さて四則演算。まずはLL法?とやらでやってみようと思ったんだけど、「2週間でできる!スクリプト言語の作り方」の方がピンとこなかったので、「明快入門 コンパイラインタプリタ開発」という本の説明を読み、なんとなくのイメージを作りコードにした。後者はそのまま後置記法に直していくんだけど、前者の構文解析木生成と再帰のevalをやってみたかったので、2週間の方に戻って304ページあたりを読みながら挑戦。

最初はルートのオブジェクトを渡して、親と子ノードのリンクを貼って…とわけのわからないことになってて挫けかけた。しかし304ページのコードを眺めて、「再帰下降なのに自分のコード再帰してないじゃん!」と気づいて再帰に直したら簡単にできた。大まかなイメージは常にもっておかなくちゃだな。

making-script-engine/calc.js at b42f486c3e73bec1a94980659b10b2fd762f5b62 · phaendal/making-script-engine · GitHub

実行結果。LexerGenerator.jsとcalc.jsを使う。

$ node calc.js
3*4+5
expr: ((3 * 4) + 5)
result: 17
3+4*5
expr: (3 + (4 * 5))
result: 23
(3+5)*(4+6)
expr: ((3 + 5) * (4 + 6))
result: 80

うわー動いてる!めちゃくちゃ楽しい!! これの生成器を作るのはとても遠い道のりになりそうだけど、とりあえず楽しんでいきたい。

しかし、ちゃんと高等教育を受けた人たちは、こういう参考書とか一字一句丁寧に集中して読んでいけるんだろうか?自分はすぐに目が滑り始めて大変だ。もう諦めて、大まかなイメージが作れたら試行錯誤するようにしている。

広告を非表示にする