yaccを使って、コンパイラを作るためにコンパイラ言語の文法を定義しなくてはならない。
今回のTiny Basicの場合、
10 INPUT X
20 Y= x*x + 6*x + 9
30 PRINT Y
というようなBASICの言語の文法を定義する。
プログラムは複数の行からできているので、
プログラム = 行 + プログラム または プログラム = 行
の2通りを定義する。
プログラム = 行 + プログラム という定義は再帰している。
2通りの定義は、正規表現のようにマッチする組み合わせが自動で見つけられるような仕組みと考えればよい。
行は、行番号と命令からできているので、
行 = 行番号 + 命令群
命令群 = 命令 + 「：」 + 命令群 または 命令群 = 命令
の2通りを定義する
命令は、
命令 = PRINT 数式 または INPUT 変数 または 代入文
と定義し、
代入文 = 変数 + 「=」 + 数式
数式 = 項 + 演算子 + 数式 または 数式 = 項
項 = 変数 または 項 = 定数
と、細分していく形で順に定義していく。
これらの定義をyaccのソースコードに記述すれば、定義されたコンパイラ言語の構文解析用のソフトが自動的に得られる。
lintのような構文チェッカーとして機能させることができる。
構文解析ソフトに入力したものが、文法に合致しているか、それとも構文エラーになるかどうかが判定できるということだ。
これをコンパイラに仕上げるには、構文解析ソフトの骨組み(スケルトン)に肉付けをして、コンパイル結果としてのコード生成機能を付け加えなくてはならない。