さて、字句解析が終わると
「1」「2」「3」「-」「4」「5」「6」「+」「7」「8」「9」
のような文字列のかわりに
「123」「-」「456」「+」「789」
のような字句の列が得られます。が、このように平らな列のままでは、まだ高度な処理はできません。たとえば「123-456+789」だったら123-(456+789)ではなく(123-456)+789という意味であることを認識しないといけないからです。syntax.mlで定義したデータ型Syntax.tで表現すると、
Add(Sub(Int 123, Int 456), Int 789)
のような構文木として解釈する必要があるわけです。このように字句の列を構文木に変換する処理を構文解析といいます。MinCamlコンパイラでは、ocamlyaccというツールを利用して、parser.mlyというファイルで構文解析を実装しています。
parser.mlyの中身はlexer.mllと類似しており、字句の列から構文木を表すデータ型へのパターンマッチングが並んでいます。たとえば
| exp PLUS exp
{ Add($1, $3) }
という感じです。$1や$3というのは、1番目や3番目の構文要素（ここでは両方ともexp）という意味です。
構文の定義は、ほとんど先に述べた式eの通りなのですが、一点だけ注意があります。MLでは式を並べるだけで関数適用になるので、x
- yと書いたときに、x
からyを引き算しているのか、関数xを引数-yに適用しているのか、曖昧になってしまうのです！ そこで、括弧をつけなくても関数の引数になれる式simple_expと、一般の式expを区別しています。たとえば-yはsimple_expではないので、先の例は関数適用ではなく引き算であるとわかるわけです。
また、いろいろな構文や二引数演算子の優先順位、（lexer.mllで出てきた）字句を表すデータ型もparser.mlyで定義されています。
なお、変数の型が必要なところ（letなど）は、とりあえず未定義の新しい型変数Var(ref
None)で埋めています。これについては次の型推論で述べます。