| 目次 | 索引 |
|---|---|
h2 構文規則 toc-syntax
h3 コンパイラ toc-compilers
機械語は人間にとって分かりにくいのでアセンブラが考え出された、
ということは、前回説明しました。
しかし、アセンブリ言語も、それほど分かりやすくはありません。
x と y を足すことを、機械語で 0x60 と書くよりは、
アセンブリ言語で iadd と書くほうが多少ましですが、
やはり x + y と書くのが一番です。
そこで開発されたのが、高級言語とコンパイラです。
index 高級言語 high level language こうきゆうけんこ
とは、数式や英単語の組み合わせで記述できる、
人間にとって分かりやすく設計されたプログラミング言語です。
Java や C は高級言語です。
高級言語と比較するために、機械語とアセンブリ言語を
index 低級言語 low level language ていきゆうけんこ
と呼ぶことがあります。
CPU は高級言語を直接理解することはできませんので、
高級言語のプログラムを機械語に変換する必要があります。
この変換ソフトウェアが
index コンパイラ compiler こんはいら
です。
コンパイラで変換することを
index コンパイル compile こんはいる
と言います。
Java では、javac コマンドがコンパイラです。
なお、変換前のプログラムは、
index 原始プログラム source program けんしふろくらむ
または
index ソース・コード source code そおすこおと
と呼ばれます。
変換後のプログラムは、
index 目的プログラム target program もくてきふろくらむ
または
index オブジェクト・コード object code おふしえくとこおと
と呼ばれます。
コンパイラは、原始プログラムを機械語に変換するものですが、
変換する前に、まず、
原始プログラムが文法的に正しいことを保証しなければなりません。
x + y は正しい足し算なので 0x60 に変換できますが、
+ x y は正しくないので変換できません。
高級言語の文法のことを、
index 構文規則 syntax こうふんきそく
と呼びます。
また、構文規則に基づいて、
原始プログラムの文法的構造を解析することを、
index 構文解析 parsing こうふんかいせき
と言います。
h3 構文規則の表記法 toc-syntax-forms
構文規則の例として、正の整数を考えます。
123 は正しいですが、2x2 は正しくありません。
001 は、ここでは正しくないとします。
すると、
「正の整数は数字の列である。ただし、先頭は '0' ではない。」
という規則が考えられます。
構文規則を日本語で記述していたのでは、厳密な議論が困難です。
構文規則を厳密に記述する方法として、
バッカス・ナウア記法がしばしば用いられます。
index バッカス・ナウア記法 Backus-Naur form はつかすなうあきほう
とは、書換え規則に基づく構文規則の表記法です。
ここで、
index 書換え規則 rewriting rule かきかえきそく
とは、文字列を別の文字列で置き換えることです
バッカス・ナウア記法では、左辺を右辺に書き換えるという規則を表します。
左辺と右辺は ::= で区切り、構文単位は < と > で囲みます。
書き換えの候補が複数あるときは、右辺を | で区切ります。
書き換えを何度か行うことを
index 導出 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
なお、構文規則を記述する言語は、
index 超言語 metalanguage ちようけんこ
と呼ばれます。
超言語の中では
index 文脈自由文法 context-free grammar
が重要ですが、
これはバッカス・ナウア記法と同じ能力を持つことが知られています。
h3 構文規則の例 toc-syntax-examples
今日の演習は次のプログラムから始めます。
/* 1*/ class Ex6 {
/* 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 Ex6.java
b04a001@AsiaA1:~/comp2l% java Ex6
11
b04a001@AsiaA1:~/comp2l%
表現 E が文法的に正しいことを示すには、
E に至る導出を一つ見つければ十分です。
逆に、E が文法的に正しくないことを示すには、
あらゆる導出が E に至らないことを確認する必要があります。
すべての可能性を調べるには、一般的には場合分けが必要ですが、
構文規則によっては一本道になります。
例えば、上記の規則
<式> ::= <変数> | (<式> <演算子> <式>)
については、先頭の文字が '(' でなければ、
変数の可能性だけを調べればよいということです。
例題 1.
表現 x = (y + (z z)); が正しい代入文でないことを証明してください。
プログラム Ex6.java を変更して javac コマンドを実行しますと、
エラーが確認できます。
構文規則は次の通りとします。
<代入文> ::= <変数> = <式>;
<式> ::= <変数> | (<式> <演算子> <式>)
<変数> ::= x | y | z
<演算子> ::= + | *
解答例 1.
<代入文> ⇒ <変数> = <式>;
⇒ x = <式>;
⇒ x = (<式> <演算子> <式>);
⇒ x = (<変数> <演算子> <式>);
⇒ x = (y <演算子> <式>);
⇒ x = (y + <式>);
⇒ x = (y + (<式> <演算子> <式>));
⇒ x = (y + (<変数> <演算子> <式>));
⇒ x = (y + (z <演算子> <式>));
という導出しかできないが、z は演算子でないから、
与えられた表現は正しい代入文ではない。
実際、コンパイルしてみますとエラーが発生します。
b04a001@AsiaA1:~/comp2l% javac Ex6.java
Ex6.java:4: ')' がありません。
/* 4*/ x = (y + (z z));
^
Ex6.java:4: ')' がありません。
/* 4*/ x = (y + (z z));
^
エラー 2 個
b04a001@AsiaA1:~/comp2l%
h2 演習 6 toc-exercises
次の表現が正しい代入文でないことを証明してください。
1. x = (y +) z * z));
2. x = (y + (z * z);
3. x = (y + ((z * z));
プログラム Ex6.java を変更して javac コマンドを実行しますと、
エラーが確認できます。
構文規則は次の通りとします。
<代入文> ::= <変数> = <式>;
<式> ::= <変数> | (<式> <演算子> <式>)
<変数> ::= x | y | z
<演算子> ::= + | *
今日の演習6の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（10月29日）を明記してください。