学習範囲
文法の記述方法と再帰下降構文解析
生成規則による演算子の優先順位の表現まで
四則演算のルールを定義する
1+2*3
私たち人間はこの式を見たとき、頭の中で「2 * 3を先に計算して6になって、+1をして7になるな」と
ルールに従って計算をしています。「1+2を先に足して3になって、* 3をして9になるんだな」とはなりません。
コンピューターにも同様にルールを教えてあげて計算させる必要があります。
木構造による文法構造の表現
1+2*3という式を木のように表現してみます。構文木(syntax tree)といいます。
そして木の末端から計算していくというルールを設定します。そうすることでシンプルに式の構造を表すことができます。
+
├── 1
└── *
├── 2
└── 3
このようにして、コンパイラは入力のトークン列を構文木に変換してから、アセンブリに変換するようします。
生成規則による文法の定義
世界の言語の基本語順の分布
一般的にはS(Subject/主語)・O(Object/目的語)・動詞(Verb/動詞)の3個の並び方によって分類されます。
3つのものを重複なしに並べるので、理屈的には6種類(3×2×1)が考えられます。
1.SOV
2.SVO
3.VSO
4.VOS
5.OVS
6.OSV
こういったルールに沿って展開していくことで、意味のある文を無数に作り出すことができます。
コラム:チョムスキーの生成文法
それまで一人一人の個人が白紙の状態から、言語は習得・蓄積されていくものだと考えられていました。しかしチョムスキーは人間は生まれながらにして文法を自由に扱える回路を備えていると提唱しました。これは当時の言語学にとって大きなインパクトを与えました。
そしてこの生成文法の背景にある、母国語の種類にかかわらず人間の脳には全てに備わっている統語能力を普遍文法と呼びました。
人間は環境によってどんな言語でも習得ができるので、誰でも多言語を取得することができます。そう考えると母国語以外の言語を学ぶ時に少し前向きな気持ちになれそうです。
日本語の語順
日本語の語順はSOV型(主語・目的語・動詞)が基本です。語順の自由度が高く、日常会話で主語がなくても会話ができます。
私たち日本人は無意識レベルで文法の構造を組み立てて、日常生活で意味を持った文を自由に扱えています。
コンピュータにも応用
上記のような定義はコンピュータとの親和性がとても高いです。
プログラミング言語の構文も同様に「生成規則」を使って定義していきます。
参考
EBNF記法
生成規則の記法として、BNF(Backus-Naur form)があります。それを拡張したEBNF(Extended BNF)というものがあります。ここまでで我々が作ってきたプログラミングの文法をEBNFを使って説明してきます。
以下の記号を使って複雑なルールを簡潔に書き下すことができます。
A* :Aの0回以上の繰り返し
A? :Aまたはε
A | B " : AまたはB
(...) :グループ化
単純な生成規則
expr = num("+" num | "-" num) *
EBNFを使ったこのような生成規則があるとします。
exprは、まずnumが1つありその後に0個以上の「+とnum、あるいは-とnum」があることを定義しています。
42-30+2のときは以下のような文字列を作り出せます。
exper → num "-" num "+" num
→ "42" "-" "30" "+" "2"
木構造で表すことで展開がよりわかりやすくなるかと思います。
[expr]
├── [num] ── 2
└── "+"
└── [num] ── 30
└── "-"
└── [num] ── 42
演算子の優先順位を生成規則で定義
expr = mul("+" mul | "-" mul) *
mul = num("*" num | "-" num) *
mulというのが乗除算の生成規則です。今回はexprはmulを経由してnumに展開されるルールになります。これはmulが先に計算され、その後加減算が計算されるルールとなっています。
以下は1 * 2 +3 * 4 * 5の構文木です。
[expr]
├── [mul]
│ ├── [num] ── 5
│ ├── "*"
│ ├── [num] ── 4
│ ├── "*"
│ └── [num] ── 3
├── "+"
└── [mul]
├── [num] ── 2
├── "*"
└── [num] ── 1
たった少しの単純なルールでコンピュータの計算の柔軟性が上がるのはとても不思議です。
まとめ
第7回まで加減算は行ってきてはいたが、乗除算は計算の優先順位があるためどのようなロジックで計算するのか気になっていました。今回の学習範囲でたった2行のルールを定義することで、計算の幅が拡張されたことに感動しました。