◇BNFに構文選択プロパティ記述法追加拡張
構文を規定するのにBNF表記を用いることは良くあります。
しかし、 BNFはトークンの並びは定義できても"構文"を定義するには あまりにも力不足であり、BNFだけでは構文をちゃんと定義できていないことも 多く見られます。
繰り返しの定義やオプショナル定義ができず、 再帰や構文選択でごまかすしかないということは ◇BNFは間違っている：繰り返しを再帰で表すべきではないに書きました。
実はBNFはそれ以外にも構文表現力の弱さを持っているのです。
BNFの"定義力"の限界
例えば、２項演算、前置演算、後置演算を左右再帰で定義した
expression ::= STRING | minus | plus | fract | add | sub | mul | div | eq minus ::= '-' expression plus ::= '+' expression fract ::= expression '!' // n!形式の階乗 add ::= expression '+' expression sub ::= expression '-' expression mul ::= expression '*' expression div ::= expression '/' expression eq ::= expression '==' expressionの様な定義で、STRINGが名前文字列として、次のような文
A - B - Cを解析するとします。
この時、構文構造が
( A - B ) - C 即ち sub(sub(A,B),C) なのか A - ( B - C ) 即ち sub(A,sub(B,C))なのかは定まりません。
さらに、+と*の結合則なども定義されないため
A + B * C
を
A + ( B * C )
と解釈させることもできません。
また前置、後置演算子の適用範囲も決定できません。
-A+B
は
(-A) + B
なのか
-(A+B)
なのか決定できない。
-A!
は
((-A)!)
なのか
(-(A!))
なのか決定できない
左右再帰とせず結合力の違いにより構文をレベル分け し曖昧性を持たせない記述は可能なのですが、 演算種が多くなると複雑になりすぎ、現実的な記述では 無くなります。
yaccではどうしているか？
BNFの申し子、yaccではこの問題をどう取り扱っているのでしょうか？
yaccはBNFの他に、プログラムと構文を結び付けるための%type記述などの
補助指定記述を持ちます。
この補助指定に%left,%rightという記述を設けて優先度を決定し、
曖昧性を避けるようにしています。
前置、後置演算に関しては%nonassocと%precの組み合わせで優先度指定
を行います。
%left * / %left + - %right == %nonassoc UMINUS UPLUS %nonassoc UFRACT expression : STRING | minus | plus | fract | add | sub | mul | div | eq minus : '-' expression %prec UMINUS plus : '+' expression %prec UPLUS fract : expression '!' %prec UFRACT add : expression '+' expression sub : expression '-' expression mul : expression '*' expression div : expression '/' expression eq : expression '==' expression
結合の強弱は、先に書かれたもの、ここでは*と/、が
強いとします。
同一の強さの場合は、leftの場合は左再帰、rightの
場合は右再帰となります。
この構文外定義により構文が定まり、例えば
A - B - C - D は ((A-B)-C)-D 即ち sub(sub(sub(A,B),C),D)
A + B * C - D は (A+(B*C))-D 即ち sub(add(A,mul(B,C)),D)
A = B = C = D は A=(B=(C=D)) 即ち eq(A,eq(B,eq(C,D)))
-A + B は ((-A)+B) 即ち add(minus(A),B)
という解釈が可能となります。残念ながら
-A! を (-A)! 即ち fract(minus(A))と解釈させることは、手元にあるyacc(BISON)では、できませんでした。
もう少し複雑なものなら
A == B + C / D - E == F
なら
A == ( ( ( B + ( C / D ) ) - E ) == F )
即ち
eq(A,eq(sub(add(B,div(C,D)),E),F))
といった解釈ができるようになります。
本来はこれはきちんと「構文規則」としての定義（BNF）の中に
あるべきものですが、BNFが無能なので仕方ありません。
別に定義を用意したのです。
BNFに導入すればいいじゃないか。(left/right)
BNFが現しているのは構文ではなく単語の並びです。構文とは 単語と単語の接続関連を決めるもので、単純な並びを決める だけではありません。その意味でBNFを構文定義と呼んだり、 構文を概念的に示すものとするのは誤っています。
先の例ではBNFが示しているのは、
A + B + C
も
A + B * C
も
A == B + C / D - E == F
も、
単語の並びとしては「許される」というだけであって、
文の構文構造は全く示していないのです。
どうすれば構文構造を示せるか？
簡単な事です。
yaccが仕方なく持ち込んだBNF外構文定義をBNFに持ち込めば
よいのです。
例えば、それを構文のプロパティと呼びましょう。形式は
/で囲む文字列で、プロパティ名とプロパティ値からなり
その間は:で区切られるとしましょう。
すなわち、
expression ::= STRING | minus | plus | fract | add | sub | mul | div | eq minus/p:10/ ::= '-' expression plus/p:10/ ::= '+' expression fract/p:8/ ::= expression '!' add/p:3/ ::= expression '+' expression sub/p:3/ ::= expression '-' expression mul/p:5/ ::= expression '*' expression div/p:5/ ::= expression '/' expression eq/right:2/ ::= expression '==' expressionといった定義法とするのです。左優先を標準としleftと書かずpを使っています。
その他のプロパティ（long/short/priority)
BNF記述で頻出する曖昧性に
- if-if-else問題
- reduce-reduce衝突
if-if-else問題は次のような記述
if( A ) x= 1; if( B ) x= 2; else x= 3;で、最後のelseがif(B)のelseなのかif(A)のelseなのか曖昧に なるという問題です。
if( A ) x=1; { if( B ) x=2; else x=3; } // if(B)のelse
if( A ) { x=1; if( B ) x=2; } else x=3; // if(A)のelse
これは内側になる構文を長く解釈するか、短く解釈するかを
指定できれば解決できます。
例えば
@ ::= ?"[ \t\n\f\r\u3000]+" // 空白 @NUMBER ::= ?"[0-9]+" // 数値トークン定義 @NAME ::= ?"[a-zA-Z]+" // 名前トークン定義 sentences ::= { sentence } sentence ::= assign-sentence | if-sentence assign-sentence ::= NAME "=" NUMBER ";" if-sentence/long/ ::= "if" "(" NAME ")" sentence [ else-part ] else-part ::= "else" sentence // この定義法は繰り返し部を {...} で、省略可能部を [...] で現していますとすれば、内側の文が長くなるように解釈、即ち最後のelseはif(B)の elseとなるとするのです。
/long/の代わりに/short/を指定すると 短く解釈し、最後のelseはif(A)のelseになります。
reduce-reduce衝突は例えば次のような形式の構文
{ a 1 2 3 } // oid:名前の後に数値が続く
{ b 4 , c 5 , d 6 } // struct:名前 数値パターンが","を挟み繰返す
で、次の文
{ e 7 }
が来た場合どちらか曖昧となるというものです。
これは、どちらを優先するかを定義できれば解決できます。
例えば構文"struct"が構文"oid"より優先される場合
oid ::= "{" NAME { NUMBER } "}"
struct/priority:oid/ ::= "{" NAME NUMBER [{ "," NAME NUMBER }] "}"
のように指定するのです。
構文定義記述に導入することが重要
「yaccなら%left,%rightがあるからいいじゃないか」という実装レベル の話をしているのではありません。
規約として文法を決める場合使用されるBNFを問題にしているのです。
例えば、規約では
add/left:3/ ::= expression '+' expression mul/left:5/ ::= expression '*' expressionと書き、yaccでの実装は
%left * %left + add : expression '+' expression mul : expression '*' expressionといったものにするのです。(yaccでは%leftは先に書いたものが優先度が 高いので、ここでは/left:3/, /left:5/の違いにより*を先に書いています)
なお、/long/,/short/はyaccでは機構上全てlong扱いになります。また /priority/は先に記述されたものが優先ということになります。
BNFの素晴らしさと実用に供する場合の問題
BNF自体は極めて少ない約束毎でかなり広い範囲で単語の並び順を現すことの できる優れたものです。
しかしながら、少ない約束故に現せる構文構造に制限が付いてしまいます。
そしてその制限により実際に使う構文「構造」を現せないことが多いのです。
少ない約束毎にこだわるメリットは殆どありません。現実的な記述法 を導入すべきなのです。
＃＃＃ 補
結合則を持つＢＮＦを構文定義として用いるJavaのツール/ライブラリが現在仮公開されています。
利用者がプログラムをしなくても構文木をＸＭＬで得る機能などを持ち、
人間向きの簡潔な記述からＸＭＬを生成し、プログラムはＸＭＬを解釈
するといった使い方もできるものです。
オツアンドサンズのホームページは です。
| 固定リンク