18-12-05 BNF EBNF
BNF EBNFについてお話します。
大体の言語はBNFと調べれば構文定義が出てきますので、読めるようになっておくと何かと便利です。
というか読めるようになっていただくと以降、私が情報共有しやすいので読めるようになってください。
皆さんが思っている10倍は簡単です。
まず大前提として、ここで書かれていることが全てのBNF、EBNFに通用するかって言うとそうではなくて、読みやすさのために簡易化したりしているものが多数なので、ここの定義そのままに読み解こうとせず「あーだいたいこんな感じね把握」みたいなノリで読み進めていってください。
BNFはバッカスナウア記法(Backus-Naur form)の略称です。
実際に使う場合、パーサジェネレータ（yacc）などで使用されることが多いです。
これに関しては本当に覚えることがほぼなくて
symbol
変数みたいなものです。構文パターンを記録したもの。
これ一つ一つが小型の構文解析器だと思ってください。
string
" "
tokenとか言われてたり。
要はどの文字（列）にマッチするかということ。
definition
::=
代入、要はsymbolの定義ですね。
厳密には代入...ではないのですけど、kotlinわかる人ならby（委譲プロパティ）に近い存在だと思ってください。
alternation
|
orです。
symbolは一つの構文パターンで構成されてるとは限らないので構文A | 構文Bの様に使われます。
comment
; begin~end
セミコロン以降、またはbegin~end間がコメントとなります。
からなります。
このままでは実際にどう記述されるかわからないので、「Hello （2回生の誰か）」を解析するパーサを作ってみましょう。
code: bnf
<hello-name> ::= <hello> <ws> <second>
<hello> ::= “Hello”
<ws> ::= “ “
<second> ::= <daigo> | <ayumi>
<daigo> ::= “daigo”
<ayumi> ::= “ayumi”
こんな感じ
繰り返しを扱いたい場合は再帰を使用します。
code: bnf
<any-hello> ::= <hello-name> | <hello-name> “, ” <any-hello>
これで
Hello daigo, Hello ayumi, Hello daigo
のような構文も解析できるようになります。
ただ正直再帰って人に優しくないと思うんですよ。それに冗長になりがちです。
BNFなんてもともと人が読むものなので、読みやすくないと意味がないのです。
なのでもっとBNFを書きやすく読みやすくしようとしたものがE(xtended)BNFです。
EBNFでは正規表現のような書き方ができます。
こちらはよりプログラム的なのでパーサコンビネータで使用されますね。
EBNFはBNF以上に個人によって書き方が変わります。
標準化自体はされてますが、言語の公式EBNF見てもこれに倣ってないものが多数です。
*
zero or more
0か1以上
+
one or more
1以上
?
optional
0か1
A{B}
B separated list of A
Bで区切られたリストA
++
no space or comment
空白、もしくはコメント禁止
( ... )
grouping
グループ化。正規表現の(?:abc)と同じものです。
実際に1エントリーポイントの定義を見ると
code: ebnf
kotlinFile
: preamble topLevelObject*
;
のように定義されています。
kotlinFileの部分が定義されるSymbolの名前
:がdefinitionですね。
preambleとtopLevelObjectが他のSymbolを参照しています。続けて書かれている場合は結合を表します。
これKotlinの場合はSymbolを続けて書くと結合扱いなのですけど、結合が,で表されるパターンも多いので一応注意を。
topLevelObjectの後に0か1以上の記号があるのでkotlinFileはpreambleさえあれば成り立つようですね。
定義の終わりに終端を示す;があって終わりですね。
ではpreambleも見ていきましょうか。
code: ebnf
preamble (used by script, kotlinFile)
: fileAnnotations? packageHeader? import*
;
scriptとkotlinFileで使用されている定義、ということまで書いてくれてます。
fileAnnotationsにoptionがついてるので0か1回この定義が呼ばれるらしいです。
packageHeaderも同様。
importは0か1以上。
以上のことから何も書かなくても拡張子がktであればkotlinFileとして認めてくれるらしいです。
どうでしょう？思っていた10倍は読み解くの楽だったのではないでしょうか。
こんなん読めるようになってもここ以外で使わないだろと思われるかもしれませんが、新しい言語を学ぶ際に見慣れない書き方などがあった場合、BNFを読めるようになっておけば大体解決できますし効率的です。
無駄に時間を使うこともないので、構文解析に興味がなくても余裕があれば覚えることをおすすめします。