学び直し45日目:10章 コンパイラ#1:構文解析(背景)
記録
構文解析が、トークナイザとパーサの2つの仕事に分かれていることを学んだ。
構文解析器のしくみ
構文解析器は、トークナイザとパーサから成る。トークナイザでプログラムを分解して、パーサでそれら要素をルール(文法)に照らし合わせて構文構造を理解する。
パーサ
言語の文法ルールに基づいて、トークンをグループ分けしてプログラムの構造を理解するためのモジュール。
再帰的な構文解析のざっくり理解
トークンには終端要素と非終端要素がある。終端要素はプログラム中の "while", "if", ";", "{", "}" などの意味としての開始や区切りとなるようなトークンであり、そのほかの要素が非終端要素と呼ばれている。
構文解析のざっくりとした理解は、
- 終端要素があったら、次の要素を調べる。
- 次の要素が非終端要素だったら、その中の要素を調べる。
- その中の要素が非終端要素だったら、さらにその中を調べる。
- さらにその中の要素が非終端要素だったら、(以下略)を終端要素に出くわすまでつづける。
- 終端要素に出くわしたら、そのグループはおしまい。はじめと終わりの終端要素で挟まれているグループの完成。
- 次のグループ調査へ (1 へ戻る)。