Java EE勉強会

DSL / BNF

DSL

BNF †

一言要約 †

プログラム言語の構文を定義する形式についての概観

要約 †

仕組み †

  • BNFはプログラム言語の構文を定義する文法を記述する仕組み
  • BNFには様々なパターンがある。
  • 共通しているのは、ルールの連続によって言語を定義するという考え方

元となる言語

 contact mfowler {
     email: fowler@acm.org
 }

BNF１

 contact  :  'contact' Identifier '{' email '}' ;
 email : 'email:' Identifier '@' Identifier ;

BNF2：Algol BNF

 <contact>  ::=  contact <Identifier> { <email> }
 <email> ::= 'email:' <Identifier> @ <Identifier>

BNF3；電話番号が入る場合

 contact  :  'contact' username '{' line '}' ;
 username : Identifier;
 line : email | tel ;
 email : 'email:' EmailAddress ;
 tel : 'tel:' TelephoneNumber ;

多重度シンボル

BNF4：電話番号は複数あるかもしれない

 contact : 'contact' username '{' fullname? email+ tel* '}';
 username : Identifier;
 fullname : QuotedString;  
 email : 'email:' EmailAddress ;
 tel : 'tel:' TelephoneNumber ;

BNF4'：サブルールのインライン化

 contact : 'contact' Identifier '{' 
   QuotedString? 
   ('email:' EmailAddress)+ 
   ('tel:' TelephoneNumber)* '}'
   ;
  • サブルールの方が意図が明確になる

BNF5：多重度シンボルの代わりにカッコを使う

 contact : 'contact' username '{' [fullname] email {email} {tel} '}';
 username : Identifier;
 fullname : QuotedString;  
 email : 'email:' EmailAddress ;
 tel : 'tel:' TelephoneNumber ;
  • ?　→　[ . . ] ／ *　→　{ . . }

EBNFを基本BNFに変換する

BNF6：?のかわりに|を使う

 contact : 'contact' username '{' fullname email+ tel* '}';
 username : Identifier;
 fullname :  /* optional */ | QuotedString  ;
 email : 'email:' EmailAddress ;
 tel : 'tel:' TelephoneNumber ;
  • a : b? c → a: c | b c.

BNF7：*のかわりに|を使う

 contact : 'contact' username '{' fullname email+ tel '}';
 username : Identifier;
 fullname :  /* optional */ | QuotedString  ;
 email : 'email:' EmailAddress ;
 tel : /* multiple */ | 'tel:' TelephoneNumber tel;
  • x : y*; → x : y x |;

BNF8：+のかわりに|を使う

 contact : 'contact' username '{' fullname email tel '}';
 username : Identifier;
 fullname :  /* optional */ | QuotedString  ;
 email : singleEmail | email singleEmail;
 singleEmail : 'email:' EmailAddress ;
 tel : /* multiple */ | 'tel:' TelephoneNumber tel;
  • x : y+ → x : y | x y.

コードアクション

BNF9：ログ出力

 contact  :  'contact' username '{' email? tel? '}';
 username:  ID;
 email  :  'email:' EmailAddress {log("got email");};
 tel  :  'tel:' TelephoneNumber;

BNF10：要素の参照 - Antlrの場合

 contact  :  'contact' username '{' email? tel? '}';
 username:  ID;
 email  :  'email:' e=EmailAddress {log("got email " + $e.text);}; 
 tel  :  'tel:' TelephoneNumber;
  • yaccの場合は、インデックスを使う

BNF11：ルールの参照

 contact   :  'contact' username '{' e=email? tel? '}' 
     {log("email " + $e.text);}
     ;
 username :   ID;
 email   :  'email:' EmailAddress ; 
 tel   :  'tel:' TelephoneNumber;

BNF12：戻り値と変数の定義

 contact   :  'contact' username '{' e=email? tel? '}' 
     {log("email " + $e.result);}
     ;
 username :   ID;
 email returns [EmailAddress result]  
    :  'email:' e=EmailAddress 
           {$result = new EmailAddress($e.text);}
    ; 
 tel   :  'tel:' TelephoneNumber;

表現解析文法

 contact : email / tel;
  • まずemailをトライしてからtelを見る

使いどころ †

  • パーサジェネレータを使う時には必ず使うし、他でも使えることがある。

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

担当者のつぶやき †

  • よく見かけるわりに、なんとなく敬遠していたBNFと向き合えたのは良かったっす。
  • やっぱりファウラーさんは体系的にまとめるのが得意ですね。

みんなの突っ込み †


Menu