Skip to content

Instantly share code, notes, and snippets.

@vrotaru
Last active Feb 24, 2020
Embed
What would you like to do?

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.

%{
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) }
type expr =
| Int of int
| Fn of string
| App of expr * expr
| Plus of expr * expr
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment