JavaScriptで構文解析：npm Lex-BNF で任意の言語を定義する
photo credit: Morton1905 Austria. Wien. Pieter Breugel d. Ä. Oil on oak panel, 114 x 155 cm. via photopin (license)
JavaScriptで、テキストの構文を定義して、その文法に従った解析、評価を支援する npm モジュール lex-bnf を正式にリリースしましたのでご紹介。 ユーザー入力のコマンドや計算式の解釈など、ちょっとしたテキストの解析器を実装するために使えますよ。
特徴
- いわゆるコンパイラコンパイラではありません。JavaScriptでテキストの構文解析を行い、JavaScriptで評価を行うためのモジュールです。
- 構文定義は BNF（バッカス=ナウア記法）的に行います。
- 再帰下降パーサーによって構文解析。
- 構文解析に先立って基本的な字句解析（identifier, number-literal, punctuator, and white-space)。
- 再帰下降パーサーによる解析時に、無限再帰に陥ってしまう「左再帰」問題には、繰り返し指定子を導入することで解決しています。
- 構文定義に合わせて、ユーザーの評価関数を定義します。評価関数によってインタプリタはモチロン、中間言語へのコンパイラも記述できます（今の所、コンパイラの支援機能はありません）
構文定義方法
以降で構文定義の方法を説明してみますが、詳細はかなり長くなりそうなので、雰囲気だけ掴んでみてください（徐々に加筆します）
基本
言語の構文はlex-bnf がエクスポートする Language クラスのインスタンスとして定義します。
このクラスのコンストラクタで、以下3つのstaticプロパティを使用して、BNFのようなデータ構造を記述します。
syntax- 文法を定義するための関数。戻り値は構文の「項(term)」を表します。第一引数に項の名称(文字列)、第二引数では、項の名称（=非終端記号）か終端記号の二次元配列によって構文のルールを定義します。第三引数には規則の条件によっては省略可能な評価関数（後述）を指定します。終端記号は次の2つのプロパティで定義します。項の名称は別の文法を参照し、構文定義内に含まれていなくてはなりません。literal- 文字リテラル（定数）の定義するための関数です。第一引数にアルファベットとアンダースコアだけを含む任意の長さの文字列を指定します。数字や区切り文字を含ませてはいけません（そういえば関数内でチェックしてませんわ汗）。numlit- 数字リテラルの終端記号を表す定数。数字リテラルは数字だけを含む任意の長さの文字列です。
※ 簡潔に記述するために、これらプロパティは独立した定数としてスプレッド構文で取り出しておいたほうが便利です。
calc.js： - 四則演算式の文法定義（冒頭部分を抜粋；全体は下の方に掲載）
"use strict"; const Language = require("lex-bnf"); const {syntax, literal: lit, numlit} = Language; // Defines syntax of language by BNF-like definition and evaluator. const calc = new Language([ syntax("calc", [["expression"]]), // The evaluator is omittable when the rules contains only one // term such as `additive-expression` below. syntax("expression", [["additive-expression"]]), // （略）
繰り返し記号
規則に現れる項の名前の末尾に*をつけると、その項が繰り返されることを意味します。
項の繰り返しは、項を再帰的に参照することで定義できますが、規則の左端で再帰を行う左再帰では、構文解析時に無限再帰に陥りますので使えません（概念としては左再帰で定義可能）。 規則の右端で再起する右再帰では式の評価順序が「右から左」となってしまいますので、式によっては正しい結果が得られません。
このため、左再帰が必要である場合は、繰り返し記号を使用して以下のように定義しなくてはなりません。
以下のサンプルでは左再帰を回避するために繰り返し記号を使っています。
// 省略 syntax("additive-expression", [ ["multiplicative-expression", "additive-expression-rest*" /* ← */ ], ], (term) => { /*評価関数（中略）*/}), syntax("additive-expression-rest", [ [lit("+"), "multiplicative-expression"], [lit("-"), "multiplicative-expression"], ], (term) => term.contents()), syntax("multiplicative-expression", [ ["unary-expression", "multiplicative-expression-rest*"], ], // 省略
// 省略 syntax("additive-expression", [ ["additive-expression", "multiplicative-expression"], ["multiplicative-expression"], ], (term) => { /*評価関数（中略）*/}), syntax("multiplicative-expression", [ ["multiplicative-expression", "unary-expression"], ["unary-expression"], ], // 省略
以下は右再帰の例。 左から右へ評価される計算式のような構文では、式によっては正しい計算結果が得られない場合があります。 あまりないと思いますが、右から左へ評価される文法では問題なし。
// 省略 syntax("additive-expression", [ ["multiplicative-expression", "additive-expression"], ["multiplicative-expression"], ], (term) => { /*評価関数（中略）*/}), syntax("multiplicative-expression", [ ["multiplicative-expression", "unary-expression"], ["unary-expression"], ], // 省略
参考
サンプル：四則演算計算機
シンプルな計算機を実装したサンプルプログラムです。 コマンドラインから指定した計算式の結果を表示します。
以下2つのソースファイルで構成しています。
どちらのファイルもリポジトリの sample ディレクトリにあります。
ここではこれらを使って、構文定義の方法を説明しています。
calc.js- 四則演算の構文定義。eval-expr.js- 四則演算計算機
実行するには、git リポジトリをclone してから node sample/eval-expr.js '<式>' とします。
式はシングルコーテーションでくくったほうが良いです。Bashで * や括弧が特別な意味を持っていますので。
実行例）
~ $ cd Git ~/Git $ git clone https://github.com/takamin/lex-bnf.git ~/Git $ cd lex-bnf ~/lex-bnf $ node sample/eval-expr.js '(1 + 2) * (3 - 4) / 5' -0.6
calc.js - 四則演算の構文定義
このファイルで、+、-、*、/ と括弧が使える四則演算式の構文定義を行っています。
"use strict"; const Language = require("lex-bnf"); const {syntax, literal: lit, numlit} = Language; // Defines syntax of language by BNF-like definition and evaluator. const calc = new Language([ syntax("calc", [["expression"]]), // The evaluator is omittable when the rules contains only one // term such as `additive-expression` below. syntax("expression", [["additive-expression"]]), syntax("additive-expression", [ // The trailing `*` is a repetition specifier. // It can avoid an infinite recursion leading from // left-recursion. ["multiplicative-expression", "additive-expression-rest*"], ], /** * evaluate 'additive-expression' * @param {Term} term result of parsing 'additive-expression' * @return {number} A result of the calculation. */ (term) => { // get no whitespace tokens const terms = [].concat(...term.contents()); let acc = terms[0]; for(let i = 1; i < terms.length; i += 2) { const ope = terms[i]; const value = terms[i + 1]; switch(ope) { case "+": acc += value; break; case "-": acc -= value; break; } } return acc; }), syntax("additive-expression-rest", [ [lit("+"), "multiplicative-expression"], [lit("-"), "multiplicative-expression"], ], (term) => { return term.contents(); }), syntax("multiplicative-expression", [ ["unary-expression", "multiplicative-expression-rest*"], ], (term) => { const terms = [].concat(...term.contents()); let acc = terms[0]; for(let i = 1; i < terms.length; i += 2) { const ope = terms[i]; const value = terms[i + 1]; switch(ope) { case "*": acc *= value; break; case "/": acc /= value; break; } } return acc; }), syntax("multiplicative-expression-rest", [ [lit("*"), "unary-expression"], [lit("/"), "unary-expression"], ], (term) => { return term.contents(); }), syntax("unary-expression", [["postfix-expression"]]), syntax("postfix-expression", [["primary-expression"]]), syntax("primary-expression", [ ["literal"], [lit("("), "expression", lit(")")], ], (term) => { const terms = term.contents(); return (terms[0] !== "(" ? terms[0] : terms[1]); }), syntax("literal", [ ["floating-constant"], ["integer-constant"], ]), syntax("floating-constant", [ ["floating-real-part", lit("e"), "integer-constant"], ["floating-real-part"], ], (term) => { // Get a token representing this element const s = term.str(); // With the BNF rule above, the string could include white spaces. // If the string includes white spaces, this method throws an error. // The error will be returned from `Language#evaluate()`. if(/\s/.test(s)) { throw new Error("invalid text for floating-constant"); } return parseFloat(s); }), syntax("floating-real-part", [ // The optional term is not offerd, so all patterns should be declared. [numlit, lit("."), numlit], [numlit, lit(".")], [lit("."), numlit], ["sign", numlit, lit("."), numlit], ["sign", numlit, lit(".")], ["sign", lit("."), numlit], ], (term) => term.str()), syntax("integer-constant", [ [numlit], ["sign", numlit], ], (term) => { return parseInt(term.str()); }), syntax("sign", [ [lit("+")], [lit("-")], ], (term) => term.str()), ]); module.exports = calc;
eval-expr.js - 四則演算計算機
"use strict"; const calc = require("./calc.js"); const expr = process.argv[2]; const result = calc.parse(expr); if(result.error) { console.error( `Syntax error: stopped at ${JSON.stringify(result.errorToken)}`); } else { try { const value = calc.evaluate(result); console.log(`${value}`); } catch(err) { console.error(`Evaluation error: ${err.message}`); } }
