DSL/Nested Expression - Java EE勉強会

タイトル †

Nested Expression

一言要約 †

ネスト式の扱いは、（トップダウンパーサではなく）ボトムアップパーサが適している。

要約 †

・ネスト式は「再帰的性質」と「優先度」の扱いでトリッキーな面を有している。

・どのように対処するかは、トップダウンパーサとボトムアップパーサとで大きく異なる。

・ネスト式の扱いは、（トップダウンパーサではなく）ボトムアップパーサが適している。

ボトムアップパーサーの例

expr ::=
   NUMBER:n {: RESULT = new Double(n); :}
 | expr:a PLUS expr:b   {: RESULT = a + b; :}
 | expr:a MINUS expr:b  {: RESULT = a - b; :}
 | expr:a TIMES expr:b  {: RESULT = a * b; :}
 | expr:a DIVIDE expr:b {: RESULT = a / b; :}
 | expr:a POWER expr:b  {: RESULT = Math.pow(a,b); :}
 | expr:a ROOT expr:b   {: RESULT = Math.pow(a,(1.0/b)); :}
 | MINUS expr:e         {: RESULT = - e; :}  %prec UMINUS
 | LPAREN expr:e RPAREN {: RESULT = e; :}
 ;

precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE;
precedence right POWER, ROOT;
precedence left UMINUS;

単純な再帰グラマー規則と優先度宣言の組合せにより、ボトムアップパーサーでは入れ子式を取り扱うのは非常に容易になっている。（定義がそのまま表れている。）

トップダウンパーサ　　左再帰を導入（左再帰って何？）　　すると→単純な再帰文法を使用できない　　すると→入れ子式が複雑になる　　すると→文法はかなり不明確　　だから、多くの人はボトムアップパーサを使う

トップダウンパーサの例

expression : mult_exp ( ('+' | '-') mult_exp )* ;

mult_exp : power_exp ( ('*' | '/') power_exp )* ;

ここで、左結合演算子のパターンが見られる。規則の本体は次の規則への参照から始まり、演算子とその右辺の繰り返しグループがそれに続く。常に、今対応している規則ではなく、次の規則を述べることになる。

べき乗と平方根演算子は、右結合演算子のパターンを示す。

power_exp : unary_exp ( ('**' | '//') power_exp )? ;

さらに、このボロボロの文法から生じる別の結果は、パーサーツリー結果も複雑になることである。1 + 2のパーサーツリーは、この様になることが予想されるだろう。

 +
   1
   2

しかし、代わりに、この様になる。

 +
   mult_exp
     power_exp
       unary_exp
         factor_exp
           1
   mult_exp
     power_exp
       unary_exp
         factor_exp
           2

ファウラーへのフィードバック †

担当者のつぶやき †

・RESULT変数を言語に組み込んでほしい。特に手続型言語は必須。

・＋ではなくPLUSのようにトークンの名前をつけた理由として、「この本の実例で通常、選択するAntlrとは異なり、リテラル・トークンをグラマーファイルに入れることができないため」の意味が分かりません、、。前の方を読んでいないから？

・ボトムアップの文法から、トップダウンの文法を生成できないのかなぁw ・「トップダウンパーサーの愛好者は、ボロボロになるのは入れ子式の場合のみで、ボトムアップパーサーの他の問題と比較して、つり合ったトレードオフであると主張している。」とあるが、ボトムアップパーサにはこれよりひどいどんな問題があるというのだろう、。

DSL / Nested Expression

Menu

最新の20件