README.md

The goal of this exercise it to have a minimal parser which will parse expressions as the ML languages do. Namely to have function application to have the highest priority. The key to this seems to have a minimal set of productions in the base rule. The app rule defines that application groups to the left.

The type expr from Syntax module has the following interpretation: Int-s are numbers, Fn-s are predefined function names and App and Plus have the obvious and natural meaning.

A way to test it is to run mehnir --interpret --interpret-show-cst parser.mly

Some examples where first line is the input the rest is menhir output:

FN INT PLUS FN INT
ACCEPT
[parse:
  [expr:
    [arith:
      [expr: [app: [base: FN] [base: INT]]]
      PLUS
      [expr: [app: [base: FN] [base: INT]]]
    ]
  ]
  EOF
]

Which shows the a hypothetical expression exp2 10 + log10 100 will be parsed as we expect it to be parsed.

And a simpler example to demonstrate that currying works too:

FN INT INT
ACCEPT
[parse:
  [expr: [app: [app: [base: FN] [base: INT]] [base: INT]]]
  EOF
]

Which shows how something like exp 2 10 will be parsed. As ((exp 2) 10) which is exactly what ML does.

parser.mly

%{
  open Syntax
%}

%token <int> INT
%token <string> FN
%token LP RP                       (* '(' and ')' *)
%token PLUS
%token EOF

%left PLUS

%start <Syntax.expr> parse

%%

parse: e = expr EOF                     { e }

expr:
  | e = app                             { e }
  | e = base                            { e }
  | e = arith                           { e }
  
app:
  | u = app v = base                    { App (u, v) }
  | u = base v = base                   { App (u, v) }
  
base:
  | v = INT                             { Int v }
  | x = VAR                             { Fn x }
  | LP e = expr RP                      { e }
  
arith:
  | u = expr PLUS v = expr              { Plus (u, v) }
  

syntax.ml

type expr =
  | Int of int
  | Fn of string
  | App of expr * expr
  | Plus of expr * expr