コンパイラつく〜ろ〜♪ 3番BNF記法

前回記事pokotyamu.hatenablog.com

今回は
BNF記法」についてまとめていきます。

BNF記法とは

プログラミング言語の設計を行うために文法を定義するのに使うメタ言語の代表格
正式名称は「Backus-Naur From
HTMLやXMLの構文定義や通信プロトコルの定義にも利用されているとのこと。

1.形式言語

日本語や英語など、自然に発生していって必ずしも文法に従っていない言語のことを自然言語と言います。
これに対して、プログラム言語のように、厳格な文法によって定義される言語を形式言語といいます。
なので、今回のようにBNF記法で表せるということですね。

ここで、ノーム・チョムスキーが提案した形式文法のクラスを紹介します。
これらのクラスによって、複雑さを表しており、0型から3型に向かって制限が増えていきます。
f:id:pokotyamu:20150515004606p:plain

2.文法構文

ここでは、例題として数値を定義したいと思います。

<数値> ::= <数字列> | <符号><数字列> | <数字列>.<数字列>
<数字列> ::=  <数字> | <数字列> <数字>
<数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 
<符号> ::= + | - | ±

<数値>や<符号>のように< >で囲まれているものは「非終端記号」
0, 1, 2, +などの< >で囲まれていないものは「終端記号」といいます。
BNFは必ず、全ての非終端記号が、終端記号になるように設計する必要があります。

ここで::=や|の意味について説明します。

<A> ::= B AはBで構成されている。
<C><D> Cの後ろにDが続く。
E | F EまたはFで構成されている。

つまり、「3.14」は上の構文で表せますが、「3,-14」などは表せないことがわかると思います。

オレオレ言語のBNF記法作成の際に
Java言語のBNF記法を参考にさせてもらったので、そちらをそちらのURLを載せておきます。
Java BNF
実際のコードを頭に置きながら、このBNF記法を読んでいくと、
かなり理解しやすいと思います!

以上で、BNF記法の定義まで終わったので、次回からはいよいよ!
オレオレ言語のBNF記法で書いたものをJavaCCで実装していきたいと思います。