プログラム言語の文法はどうやって定義されるのか？：Javaでコンパイラの基礎を理解する（4）（2/2 ページ）
「0以上の10進整数」をBNFで表すと
次に、「0以上の10進整数 <number>」をBNFで記述してみましょう。1つの生成規則だけでは表現できないので、次のように2つの生成規則を使って定義します。
<number> ::= <digit>|<digit><number> <digit> ::= 0|1|2|3|4|5|6|7|8|9
ここで、「{e}」はeを0個以上並べたものを生成することを意味し、「[e]」はeを0または1個生成することを意味することにして、BNFを拡張して表記すると、最初の生成規則をより分かりやすく次のように表記できます。説明のためにそれぞれの生成規則に「 …（a）」「…（b）」と付けてあります。
<number> ::= <digit>{<digit>} …（a）
<digit> ::= 0|1|2|3|4|5|6|7|8|9 …（b）
この定義を使って、ある文字列が「0以上の10進整数」かどうかを判定するのは、ちょっと複雑になります。対象の文字列がBNFで定義された生成規則を使って生成できれば、それは「0以上の10進整数」だといえます。逆に生成できなければ、それは「0以上の10進整数」とはいえません。
例1：「1」という文字列が「0以上の10進整数」であるかの判定
例えば、「1」という文字列が「0以上の10進整数」であるかを判定するには、次のような手順となります。「1」という文字列が生成できるため、これは「0以上の10進整数」だといえます。
図3 「1」という文字列が「0以上の10進整数」であるかの判定フロー（1）（a）の生成規則で、最初の文字は
（2）文字列が終了しているので、処理を終了
例2：「12」という文字列が「0以上の10進整数」であるかの判定
次に、「12」という文字列が「0以上の10進整数」であるかを判定するには、次のような手順となります。
図4 「12」という文字列が「0以上の10進整数」であるかの判定フロー（1）（a）の生成規則で、最初の文字は
（2）文字列が終了していないので、生成を続ける
（3）（a）の生成規則から、
（4）文字列が終了しているので、処理を終了
例3：「a2」という文字列が「0以上の10進整数」であるかの判定
次に、「a2」という文字列が「0以上の10進整数」であるかを判定してみると、すべての生成規則を適用しても、「a」を生成できません。その結果から、「a2」という文字列は「0以上の10進整数」ではないということになります。
図5 「a2」という文字列が「0以上の10進整数」であるかの判定フロー例4：「01」という文字列が「0以上の10進整数」であるかの判定
なお、今回紹介した定義において微妙なのは、「01」といった文字列を生成できてしまう点です。文字列の先頭に0が付く「0より大きな整数」について、「0以上の10進整数」としたくない場合には改良が必要になります。
BNFでプログラム言語を定義してみよう
ここまで説明したことから、BNFを使えば「文字列が文法に従っているか否か」を判定できることが分かったはずです。そこで、実際にBNFを使ってS1s（Svm1用プログラミング言語）の定義をしてみましょう。短い時間の中で理解するには、あまり複雑な文法にはできませんから、S1sは「簡単な四則演算の計算を実現できる程度のプログラミング言語」として定義します。
ということで、0以上の10進整数の四則演算式を実現するようにS1sを定義すると、次のようになります。生成規則がたくさん出てきますが、順番に見ていけば理解できるはずです。
なお、「{」と「}」についてはBNFを独自に拡張して特別な意味を持たせているので、終端記号としての「{」と「}」についてはそれぞれ「'（シングルクオーテーション）」を付けて、「'{'」「'}'」と表記しています。
<program> ::= main '{' <expression> '}'
<expression> ::= <term>{ <opeas> <term> }
<term> ::= <factor>{ <opemd> <factor> }
<factor> ::= <number>|( <expression> )
<number> ::= <digit>{<digit>}
<opeas> ::= + | -
<opemd> ::= * | /
<digit> ::= 0|1|2|3|4|5|6|7|8|9
このBNFから分かるのは、S1sのプログラムは「main { 」で始まり、「}」で終わるということです。また、半角の空白で各記号が区切られていることも分かります。
「1+2」「1+2-3」「1*(2+3)」といった式をS1sのプログラムにすると、「main { 1 + 2 }」「main { 1 + 2 - 3 }」「main { 1 * ( 2 + 3 ) }」となります。ここでは確認は省略しますが、「main { 1 + 2 }」はS1sのBNFを使って生成できることを自分で確認してみてください。
また、「main { 1 + 2 - }」については、「<expression> ::= <term>{ <opeas> <term> }」の生成規則から、「 <opeas> 」の後には必ず「<term>」から生成される記号が必要なので、生成できないことはすぐに分かるはずです。このほかの例についても、自分で確認してみてください。
このようにして、BNFでプログラミング言語の文法定義ができることが分かりましたが、使用する文字について確認をしておきましょう。BNFからS1sで使用可能な文字列は、カンマを区切り文字とすると、main,{,},+,-,*,/,(,),0,1,2,3,4,5,6,7,8,9と半角の空白です。main以外は1文字です。
なお、BNFで使われる<,>,|といった文字は、生成規則を記述するために使用されている文字なので、特別な文字として考える必要があります。これらは「メタ記号」と呼ばれます。
そもそもJavaの文法は何で定義されているの？
さて、BNFが分かるようになると、JLS（Java Language Specification、Javaの言語仕様）で定義されているJavaの文法も理解できるようになってきます。ちょっとのぞいてみましょう。「The Java Language Specification」のページから言語仕様を参照できます。
この中のCHAPTER 18にSyntaxが定義されており、BNFを拡張した表記で文法が書いてあります。「Statement:」を見ると、ブロック文、if文、for文などのどれかを生成すると定義されているのが分かるはずです。
（略）
Statement:
Block
assert Expression [ : Expression] ;
if ParExpression Statement [else Statement]
for ( ForControl ) Statement
while ParExpression Statement
（略）
SQLやXMLもBNFで表現されている
さて、今回はプログラミング言語の文法を定義する方法について解説をしました。Javaを使ったプログラムは出てきませんでしたが、BNFという表記方法を知らなかった人にとっては興味深く読んでもらえたのではないかと思います。
BNFは言語設計に興味を持った開発者は必ず学ぶ基本事項なのですが、実はプログラミング言語を使ってプログラムをする開発者にとっても重要です。なぜなら、コンピュータが扱うプログラミング言語というのは、BNFを拡張した記法で文法定義がされていることが多いからです。このため、プログラミング言語の文法について何かを確認したいときには、BNFを読めるとずいぶんと違うはずです。
例えば、ECMAScriptはStandard ECMA-262から仕様が公開されているので、開いてみると文法がBNFを拡張したもので表記されています。
ほかには、SQLやXMLなどもBNFでどのように表現されるのか、検索エンジンなどを使って調べてみると面白いはずです。
次回は「字句解析」について
これまでの連載で、コンパイラを作成する準備をしてきました。コンパイラの基本構成を図で振り返ってみましょう。
図6 コンパイラの基本構成図を見ても何のことか思い出せない読者は、連載第1回の「コンパイラの基本構成」を見て、復習しておくことをお勧めします。
次回はいよいよコンパイラのプログラムをJavaで作成します。まずは今回定義した文法に従って、図の（1）「字句解析」を行うプログラムについて解説をする予定です。お楽しみに。
筆者紹介
小山博史（こやま ひろし）
Webシステムの運用と開発、コンピュータと教育の研究に従事する傍ら、オープンソースソフトウェア、Java技術の普及のための活動を行っている。Ja-Jakartaプロジェクトへ参加し、コミッタの一員として活動を支えている。また、長野県の地域コミュニティである、SSS(G)やbugs(J)の活動へも参加している。
Copyright © ITmedia, Inc. All Rights Reserved.
注目のテーマ
ITmediaはアイティメディア株式会社の登録商標です。