読者です 読者をやめる 読者になる 読者になる

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

私に教えられることなら

構文解析器生成器に取り掛かってみる

JavaScript Node.js

2週間でできる!スクリプト言語の作り方 での勉強の続き。 本では著者が作った(?)Parserライブラリを使っているのだけど、JavaなのでJavaScript版が必要になる。移植は面倒そうなのと、考えてみるのが楽しそうなので自作してみることにする。(ヤクの毛刈りだ…)

説明が長いのでてきとうに読んだところ、多分

  • (字句解析でトークンの列にしておく)
  • BNFからParserを作成する (generate)
  • Parserにトークンの列を読み込ませる (parse)
  • 抽象構文木(AST)を作る

という手順を踏めばよくて、作るライブラリは

の2段階にすれば良さそうだ。

まずはParserを生成するんだけど、本のParser生成時のソースがちょっと うおお… となる複雑さだったので、できるだけ書いてて楽そうなインターフェイスを先に考えてみた。

var parser = ParserGenerator();

parser
    .Rule("primary")
    .sep("NUMBER")
    .or()
    .sep("LPAREN").ast("expr").sep("RPAREN")

    .Rule("expr")
    .ast("primary")
    .or()
    .ast("expr").operator("BINOP").ast("expr")

    // ... BNFっぽい記述が続く ...

    .defOperators("OPERATOR")
    .add( // ... オペレータの定義 ...
    )
;

これならまあ、あまり嫌な気分にはならなさそうだ。 とりあえずとして、今日はBNFっぽい記述のところから各ルールの構造を作り、toBNFメソッドBNFっぽく出力できるようにしてみた。

まずジェネレータ

(function (global) {
    var MODULE_NAME = "ParserGenerator";

    var interfaces = {},
        exports = function () {
            var parser,
                f = function () {}
            ;
            f.prototype = interfaces;
            parser = new f();
            return parser;
        };

    interfaces.Rule = function (rule) {
        this.target_rule = rule;

        // ルールが既にある場合はターゲットに指定して終わり
        if (this.rules && this.rules[rule]) {
            return this;
        }

        // ルールの登録先が無い場合は作る
        if (!this.rules) { 
            this.rules = {}; 
        }

        // ルールが無いので作る
        this.rules[rule] = {
            name: rule,
            last_index: 0,
            terms: []
        };

        return this;
    };

    interfaces.addTerm = function (class_name, type) {
        var target = this.target_rule,
            rule   = this.rules[target],
            terms
        ;
        
        if (!rule.terms[rule.last_index]) {
            rule.terms.push([]);
        }
        terms = rule.terms[rule.last_index];

        // ここでsepからトークンを判断して追加する
        terms.push({
            class: class_name,
            type:  type
        });

        return this;
    };

    interfaces.sep = function (sep) {
        return this.addTerm("sep", sep);
    };

    interfaces.ast = function (ast) {
        return this.addTerm("ast", ast);
    };

    interfaces.or = function () {
        var target = this.target_rule,
            rule   = this.rules[target]
        ;

        rule.last_index += 1;

        return this;
    };

    //TODO
    interfaces.operator = function () {
        return this.addTerm("op", "OP");
    };

    // TERMINATION OF CASCADE
    
    interfaces.toBNF = function () {
        var bnf = "",
            rules = this.rules        
        ;

        // それぞれのASTについて
        Object.keys(rules).forEach(function (key) {
            var rule_name = key,
                term_patterns = rules[rule_name].terms,
                r_term_patterns = []
            ;

            // ルール名
            bnf += key + ": ";

            // 各終端を文字列化
            term_patterns.forEach(function (terms) {
                var terms_s = [];
                terms.forEach(function (term) {
                    //TODO 各typeで表示すべき文字を変更(カッコなど)
                    terms_s.push(term.type);
                });
                r_term_patterns.push(terms_s.join(" "));
            });

            bnf += r_term_patterns.join(" | ");
           

            //TODO とりあえず今は 1行1ルール
            bnf += "\n";
        });

        return bnf;
    };

    global[MODULE_NAME] = exports;
})(this);

使用例

(function (global) {
    var parser = global.ParserGenerator();

    parser
        .Rule("primary")
        .sep("LPAREN").ast("expr").sep("RPAREN")
        .or()
        .sep("NUMBER")

        .Rule("expr")
        .ast("primary")
        .or()
        .ast("expr").operator().ast("expr")

        .Rule("block")
            .sep("LBRACK").sep("RBRACK")
        .or()
            .sep("LBRACK").ast("statement").sep("RBRACK")
            .sep("SEMICOLON").ast("block")
        .or()
            .sep("LBRACK").ast("statement").sep("RBRACK")

    
        .Rule("simple")
        .ast("expr")

        .Rule("satatement")
        .sep("IF").ast("expr").ast("block")
        .or()
        .sep("IF").ast("expr").ast("block").sep("ELSE").ast("block")
        .or()
        .ast("simple")
    ;

    // \nで改行したい場合、console.logは\nをエスケープしてしまうので、
    // stdout.writeで直接出力する
    process.stdout.write(parser.toBNF());
})(this);

結果

primary: LPAREN expr RPAREN | NUMBER
expr: primary | expr OP expr
block: LBRACK RBRACK | LBRACK statement RBRACK SEMICOLON block | LBRACK statement RBRACK
simple: expr
satatement: IF expr block | IF expr block ELSE block | simple

感想

  • Generatorのこういう作り方、thisが大量でちょっとイライラするので、クロージャ使った方が良さそう。一回の実行でGenerator大量に作るわけでもないし。
  • BNFがあってるか自信ないのでBNF自体の勉強しなければ。
  • ここからが大変そう。
  • ちょっと日記に貼るには長すぎるコードになってきたので、gitとかpastebinとかそういうものを使おう。
広告を非表示にする