| Edit this page | Report an issue |
まず，非常に単純な言語として，整数，真偽値，条件分岐，加算乗算と変数の参照のみ（新しい変数の定義すらできない!）を持つ言語 MiniML1 から始める．
MiniML1 は，上記のように OCaml のうち，整数，真偽値，条件分岐，加算乗算と変数参照の機能のみを持つ言語である．したがって，以下はすべて MiniML1 の式として扱いたい: 3, true, x, if x then 3 else y, 3 + x, (3 + x1) * false．この節の目的は，どのようなプログラムが MiniML1 の式であるか，すなわち，これらの式のシンタックスをどのように定めればよいかである．
ところで，我々はこれまでに「語の集合」を定義する方法をいくつか学んできた．プログラミング言語のシンタックスを定義する際には，これらの方法のうち 文脈自由文法 を用いることが多い．1特に，プログラミング言語のシンタックスを定める際には，文脈自由文法を更に簡略的に表記するための方法である BNF ( Backus-Naur form) を用いることが多い．
1: 本科目では有限状態オートマトン，正則表現，文脈自由文法については既知であるとする．復習が必要な者は「言語・オートマトン」で学習した内容や適当な教科書を参照されたい．
とりあえず BNF によるシンタックス定義がどのようなものか見てみよう．MiniML1 のシンタックスは以下の形で与えられる．
P ::= e ;;
b ::= true | false
e ::= <識別子> | <自然数リテラル> | b | e op e | if e then e else e | ( e )
op ::= + | * | <
まず，これがどのように文脈自由文法を表現しているとみなせるかを説明しよう．ここに挙げた BNF は非終端記号がP, b, e, opで，その他の記号（;;, true, false, <識別子>, <自然数リテラル>, op, if, then, else, (, ), +, *, <）が終端記号である文脈自由文法を表していると思ってもらえばよい．書き換え規則の表現が少し独特で，例えばこの文法のeについては，「e は <識別子> または <自然数リテラル>，または b または … のいずれかに書き換えられる」という規則を表現している．文脈自由文法における書き換え規則のうち，左辺の非終端記号が同じ規則を一つにまとめてあるわけである．
また，<識別子> と <自然数リテラル> は，それぞれ別途定められた識別子の集合と自然数リテラルの集合の元を表す記号である．（このように，文法中に現れるある集合の元を表す記号のことを メタ変数 と呼ぶ．）この言語では，識別子は，英小文字で始まり，数字，英小文字，'（アポストロフィ）を並べた，予約語ではない文字列と定めておく．なお，この段階では予約語は if, then, else, true, false の5つである．
また，非終端記号を表す記号 P, b, e, op は，それぞれ プログラム, 真偽値リテラル, 式, 演算子 を表すメタ変数である．（これらのメタ変数が動く範囲は，この BNF を文脈自由文法として見たときに生成される語の集合である．）
ところで，この BNF で定義される文法は曖昧であり，例えば式 1 + 2 * 3 の構文木が複数存在する．この曖昧性を排除するために，優先順位と結合を以下の通り定める．演算子 +と*は左結合とする．また，結合の強さは，強い方から*, +, <, if式とする．
TODO: 具象構文木と抽象構文木