【プログラミング言語】構文を理解する

プログラミング言語の基本要素

プログラミング言語の基本要素として、文と式が挙げられる。この2つを区別できるようになりたい。以下にその具体的な例を記載する。

n = i*3;
if (n > 8) return 1;
return 0;

上のコードにおいて、文と式を区別すると以下のようになる。

・文→n = i*3，if (n > 8) return 1;，return 1;，return 0;

・式→i*3，i，3，n > 8，n，8，1，0

文は;で切れている一部分を指す。式は四則演算などの評価結果となる値を持つ要素を指す。そのため、上のコードの1行目のn = i*3;の左辺のnは式ではないことに注意。

注意：特別に＜式＞ ";"のものを式文と呼ぶ。（例 10;）

構文規則

文脈自由文法

文脈自由文法(context-free grammer，CF文法)について理解する。CF文法では定義::=の代わりに→が用いられる。ここでひとつCF文法の例を以下に挙げる。

G_0 = (
  N = {E},                          //非終端記号
  Σ = {num, +, *, (, )},            //終端記号
  P = {E → E+E | E*E | num | (E)},  //生成規則
  S = E                             //開始記号
)

以上のCF文法から得られる式を1つ挙げるとnum + num * numである。ここでCF文法の曖昧性を考える。num + num * numの解析木を描くと以下の2つが得られることがわかる。

解析木Ⅰでは*が深い部分に存在している、すなわち*が優先して演算されていることがわかる。
反対に、解析木Ⅱでは、+が深い部分に存在している、すなわち+が優先して演算されていることがわかる。このとき、数学的に正しい演算順序は解析木Ⅰである。

この曖昧さを無くすためにG_0と等価でかつ、無曖昧な文法G_1を以下に示す。このとき、曖昧さを無くすために意識する3点は、
・+よりも*を優先して演算する。（*を深い位置で実行する）
・+は左結合が優先
・*は左結合が優先
である。これを基に作成したG_1は以下の通りである。

G_1 = {
  N = {E, T, F},
  Σ = {num, +, *, (, )},
  P = {
    E → E+T | T,
    T → T*F | F,
    F → num | (E) 
  }
  S = E
}

Pの配列の内容に着目する。P[0]に+の演算が来た後、P[1]に*の演算が来ている。この順序により、num + num * numの解析木を書いた際に曖昧さが無くなっていることがわかる。
また、各生成規則で左結合を示していることにも注意。