コンパイラ/文法

コンパイラ理論における文法は、主に原始言語の形式的な文法、すなわち形式文法のことを指す。形式言語は記号（アルファベット）の集合であり、形式言語は、その文字列のルール、すなわち文法を定める。

この形式文法はプログラミング言語の仕様の重要な部分を担っている。

生成文法

生成文法は、形式言語の変換ルールの集合を表す。生成文法には、「開始記号」と呼ばれる、最初に定義される記号が文となる。通常は"Start"の頭文字をとって、$S$とする。

生成文法の左側に出るものは、まだ展開可能であり終端に達していないという意味から、「非終端記号」と呼ぶ。また、生成文法の右側にしか出てこないものは非終端記号に対して、「終端記号」と呼ぶ。文は終端記号の集合であり、文法の展開は必ず終端記号に達するまで行われる。

また、特殊なもので、$\epsilon$がある。これは、空記号と呼ばれ、何も生成しない。

文脈自由文法・文脈依存文法

文脈自由文法の一般形は、

V → α

である。Vは非終端記号で、αは非終端記号、終端記号、またはεである。

それに対して、文脈依存文法は、

αAβ → αγβ または S → ε

という形をとる。ここで、α、βは終端記号の集合で、γは空ではない非終端記号と終端記号の集合である。また、文脈依存文法は完全に文脈自由文法を包含する。

プログラミング言語では、文脈自由文法の方が使われる。文脈自由文法は文脈依存文法に比べてシンプルで分かりやすく、人間にとっても誤りを出しにくく、コンパイラも楽に作れ実行速度も速くなるため、文脈自由文法が一般的である。そのため、本書では文脈自由文法についてのみ扱う。

文脈自由文法

文は本質的に再帰的な性質を持っており、文脈自由文法による再帰的な定義でプログラミング言語は定義されている。

なお、本書では今から次のルールを定める。特に断りが無い限り、これらは順次適応される。

1. 小文字のアルファベットから始まる単語・ 数字・記号、は終端記号である。
2. 大文字のアルファベットから始まる単語は非終端記号である。
3. 小文字のイタリック体のアルファベットは終端記号の集合とする。
4. 大文字のイタリック体のアルファベットは非終端記号の集合とする。
5. α, β, γ など、小文字のギリシャ文字は文法記号 (非終端記号または終端記号) の集合とする。
6. 開始記号は一番初めに出てくる生成規則の左辺とする。

また、生成規則は次のように書くものとする。

A → α | β | γ 

または、インデントを用いて

A
    α
    β
    γ

ここでは簡単な式の文法を定義してみる。

E → E + E | E * E | ( E ) | -E | number

numberは、ここでは数字とする。

この文法に従うと、

E ⇒ E + E ⇒ E * E + E ⇒ 10 * E + E ⇒ 10 * 9 + E ⇒ 10 * 9 + 8　・・・　(1)

のように、この文法は足し算とかけ算、マイナス、カッコを使った式を表すことができる。文は終端記号だけで出来ているので、全ての非終端記号を終端記号に置き換えてやらないといけない。(1)では「⇒」という記号を用いているが、A ⇒ B、は「AはBを導出する」と読む。この置き換えの操作とは、いずれかの非終端記号を生成文法の右側のいずれかに置き換えるということであり、これを導出と呼ぶ。上の (1) は、Eを開始記号とする文法から、10 * 9 + 8が導出でき、10 * 9 + 8はこの文法に当てはまる文であるという証明になっている。

ここで定義を補強する。S (Start)を開始記号とする文脈自由文法G (Grammar)があるとき、L(G) (Language)という言語が定義される。L(G)は、Gに含まれる終端記号の集合W (Word)だけでできている。WはGから一回以上の導出の繰り返しによってL(G)を文脈自由言語という。もしL(G)とL'(G')が同じ言語を生成するなら、GとG'は等価であるという。

また、Sから0回以上の導出によって生成されたαをGの文形式と呼ぶ。αは終端記号・非終端記号のどちらが入っていても良い。

導出の種類

導出とは、前述の通り、「いずれか」の非終端記号を生成文法の右側の「いずれかに」置き換えるという操作を表す。このとき、「どの」非終端記号を置き換えるかということと、非終端記号「どの」選択肢に置き換えるか、という2つの問題がある。真っ先に思いつくであろう方法は、最も左にある非終端記号の導出であろう。(1)では、最も左にある非終端記号の導出しかしていない。この導出を最左導出と呼ぶ。またSから0回以上の最左導出によって生成されたαをGの左文形式と呼ぶ。

同様に、最も右にある非終端記号の導出を最右導出、または正準導出と呼び、Sから0回以上の最右導出によって生成されたαをGの右文形式と呼ぶ。

解析木

解析木は、導出をグラフで表したものである。ただし導出の順序は表せない。

						E
					／	｜	＼
				E		+		E
			／	｜	＼				＼
		E		*		E				8
	／						＼
10								9

上の解析木は(1)の導出を表している。導出のたびに、導出される非終端記号から子が伸びている。

解析木は順序の情報を保存しない。

そのため、

E * E ⇒ 10 * E ⇒ 10 * 9

と

E * E ⇒ E * 9 ⇒ 10 * 9

は、同じ解析木になる。このように導出の順序は様々に考えられる。最左導出や最右導出はその順序を一つに絞るためのよくある方法である。もちろん他に方法は考えられるが、この2つ以外の方法はほとんどないといって良い。

ただし、最左導出や最右導出は1通りのみ、文に対応する構文木はただ一つである、といった仮定はここではしない。

文法の曖昧さ

E + E * E の導出を考えてみる。この導出には2つ考えられる。

ひとつは、

E ⇒ E + E ⇒ E + E * E　・・・　(2)

である。その次に、

E ⇒ E * E ⇒ E + E * E　・・・　(3)

が考えられる。

(2)の解析木は以下の通り。

図1

		E
	／	｜	＼
E		+		E
			／	｜	＼
		E		*		E

(3)の解析木は以下の通り。

図2

				E
			／	｜	＼
		E		+		E
	／	｜	＼
E		*		E

普通、演算は足し算よりもかけ算を優先する。(2)の導出と図1ではかけ算の方を優先しているのに対し、(3)の導出と図2では足し算の方を優先している。

そのように優先されている理由はというと、2段目に注目すると良い。図1は、E + (E * E) なのに対し、図2は、(E + E) * E である。

このように、同じ文に対し2つ以上解析木が出来上がってしまうことを曖昧であるといい、2つ以上の解析木が出来上がってしまう文法を曖昧な文法と呼ぶ。曖昧な文法で解析木が2つ以上ではコンパイラはそこから先へ進めないので、曖昧さを解消するような規則 (曖昧性解消規則) が必要になる。後に説明するが、これはif-else文がよく例に出される。if-else文を曖昧さの無い文法で記述することも可能であるが、曖昧さを残したまま後から曖昧性解消規則によって解析木を作る方がシンプルになる。このように、曖昧さは常に煩雑で不要なものではないのである。

例:

if a == 0
    if b == 0
        c = 0
    else
        c = 1

このプログラムは、a=0 かつ b≠0 のとき、c=1 となる。しかし、次のプログラム

if a == 0
    if b == 0
        c = 0
else
    c = 1

は、a≠0 のときに c=1 となる。このプログラムではインデントで表しているので人間が読んだときに誤って捉えてしまうことはないが、空白を無視するコンパイラにとって、曖昧な文法であるため、この文はどちらの意味かは判断できない。pythonのような言語では空白がインデントを意味するため、この曖昧さは回避できているが、そうでない場合、前述の通り特別な規則が必要になる。

正規表現

文脈自由文法は正規表現を完全に含有する(厳密な証明は行わない) 。しかし正規表現では文脈自由文法で記述可能な言語を記述できないことがある。例えば、釣り合ったカッコの文法は正規表現では表せない。文脈自由文法でこれを表現すると、

S → (S) | ε

となるが、正規表現ではこれは表現できない。それでも正規表現が使われるのは、正規表現の方が範囲は狭いが簡潔に表現できることであり、文脈自由文法をわざわざ用いなくとも良いことがあるからである。正規表現は字句解析によく用いられる。逆に字句解析で文脈自由文法を使わないと表現できないようなルールを設けても使用する側にとっては不便になりやすい。強力だが複雑なルールよりも、表現範囲は狭いが単純なルールの方が使用する側にとって使いやすく苦痛が少ないのである。

また正規表現程度の文法なら手書きも十分可能であり、実際GCCは独自の字句解析である。

正規表現の表記方法

正規表現は文脈自由文法で表すとなると少々煩雑になるものを簡単に表現できる。例えば、idを一回以上繰り返すことを表すのに、文脈自由文法では、

S
    id
    id S

としなければならないが、正規表現であればid+ですむ。また0回以上の繰り返しは文脈自由文法では

S
    ε
    id S

だが正規表現ではid*ですむ。

0個または1個は文脈自由文法では

S
    ε
    id

だが、正規表現ではid?ですむ。

もちろん、これらの機能を拡張バッカス・ナウア記法のように文脈自由文法に組み込むこともできるが、一般的にはそのようなことは行われない。