コンパイラは、原始プログラムを機械語に変換するものですが、変換する前に、まず、原始プログラムが文法的に正しいことを保証しなければなりません。
x + y
は正しい足し算なので 0x60 に変換できますが、
+ x y
は正しくないので変換できません。
高級言語の文法のことを、
構文規則
(
syntax
)
と呼びます。
また、構文規則に基づいて、原始プログラムの文法的構造を解析することを、
構文解析
(
parsing
)
と言います。
構文規則の例として、正の整数を考えます。
123
は正しいですが、
2x2
は正しくありません。
001
は、ここでは正しくないとします。
すると、「正の整数は数字の列である。
ただし、先頭は
0
ではない。」
という規則が考えられます。
構文規則を日本語で記述していたのでは、厳密な議論が困難です。 構文規則を厳密に記述する方法として、バッカス・ナウア記法がしばしば用いられます。
バッカス・ナウア記法 ( Backus-Naur form ) とは、書換え規則に基づく構文規則の表記法です。 ここで、 書換え規則 ( rewriting rule ) とは、文字列を別の文字列で置き換えることです
バッカス・ナウア記法では、左辺を右辺に書き換えるという規則を表します。 左辺と右辺は"::="で区切り、構文単位は"<"と">"で囲みます。 書き換えの候補が複数あるときは、右辺を"|"で区切ります。 書き換えを何度か行うことを 導出 ( derivation ) と言います。 表現 E に至る導出が存在すれば、 E は文法的に正しいとします。
正の整数の構文規則をバッカス・ナウア記法で表しますと、次のようになります。
<正の整数> | ::= | <先頭数字><数字の列> |
<数字の列> | ::= | <空列> | <数字><数字の列> |
<先頭数字> | ::= | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
<数字> | ::= | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
<空列> | ::= |
123
に至る導出は次の通りです。
<正の整数> | ⇒ | <先頭数字><数字の列> |
⇒ | 1 <数字の列> |
|
⇒ | 1 <数字><数字の列> |
|
⇒ | 12 <数字の列> |
|
⇒ | 12 <数字><数字の列> |
|
⇒ | 123 <数字の列> |
|
⇒ | 123 <空列> |
|
⇒ | 123 |
今日の演習は次のプログラムから始めます。
/* 1*/ class Ex7 { /* 2*/ public static void main (String[] args) { /* 3*/ int x, y = 2, z = 3; /* 4*/ x = (y + (z * z)); /* 5*/ System.out.println(x); /* 6*/ } /* 7*/ }
この4行目に注目します。 ここでは、Java言語を単純化して、構文規則を次のようにします。 この規則では、演算は必ず括弧で囲むことに注意してください。
<代入文> | ::= | <変数> = <式>; |
<式> | ::= | <変数> | ( <式> <演算子> <式>) |
<変数> | ::= | x | y | z |
<演算子> | ::= | + | * |
この表現は代入文として文法的に正しいことが証明できます。 この表現に至る導出は次の通りです。
<代入文> | ⇒ | <変数> = <式>; |
⇒ | x = <式>; |
|
⇒ | x = ( <式> <演算子> <式>); |
|
⇒ | x = ( <変数> <演算子> <式>); |
|
⇒ | x = (y <演算子> <式>); |
|
⇒ | x = (y + <式>); |
|
⇒ | x = (y + ( <式> <演算子> <式>)); |
|
⇒ | x = (y + ( <変数> <演算子> <式>)); |
|
⇒ | x = (y + (z <演算子> <式>)); |
|
⇒ | x = (y + (z * <式>)); |
|
⇒ | x = (y + (z * <変数>)); |
|
⇒ | x = (y + (z * z)); |
実際、このプログラムは問題なくコンパイルできます。
b04a001@AsiaA1:~/comp2l% javac Ex7.java b04a001@AsiaA1:~/comp2l%
表現 E が文法的に正しいことを示すには、 E に至る導出を一つ見つければ十分です。 逆に、 E が文法的に正しくないことを示すには、あらゆる導出が E に至らないことを確認する必要があります。
例題1.
表現
x = ((y * y) + z);
が代入文として文法的に正しいことを証明してください。
プログラムEx7.javaを変更してjavacコマンドを実行しますと、正しいことが確認できます。
解答例1. この表現に至る導出は以下の通り。
<代入文> | ⇒ | <変数> = <式>; |
⇒ | x = <式>; |
|
⇒ | x = ( <式> <演算子> <式>); |
|
⇒ | x = (( <式> <演算子> <式>) <演算子> <式>); |
|
⇒ | x = (( <変数> <演算子> <式>) <演算子> <式>); |
|
⇒ | x = ((y <演算子> <式>) <演算子> <式>); |
|
⇒ | x = ((y * <式>) <演算子> <式>); |
|
⇒ | x = ((y * <変数>) <演算子> <式>); |
|
⇒ | x = ((y * y) <演算子> <式>); |
|
⇒ | x = ((y * y) + <式>); |
|
⇒ | x = ((y * y) + <変数>); |
|
⇒ | x = ((y * y) + z); |
実際、問題なくコンパイルできる。
b04a001@AsiaA1:~/comp2l% javac Ex7.java b04a001@AsiaA1:~/comp2l%
次の表現が代入文として文法的に正しいことを証明してください。
x = y;
x = (y + z);
x = ((y * y) + (z * z));
プログラムEx7.javaを変更してjavacコマンドを実行しますと、正しいことが確認できます。 構文規則は次の通りとします。
<代入文> | ::= | <変数> = <式>; |
<式> | ::= | <変数> | ( <式> <演算子> <式>) |
<変数> | ::= | x | y | z |
<演算子> | ::= | + | * |
今日の演習7の答案をメールで提出してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(11月24日)を明記してください。