(* Yacc: "Yet Another Compiler Compiler" / Parser generator / LR(1) grammars. Context-Free Grammars: How to parse? O(n^3): CYK, O(n^2.78) with sophisticated matrix multiplication "Deterministic Context-Free Grammars" / LR(1) grammars / Knuth O(n) running time. LALR grammars / Antlr Yacc ==> GNU Bison, Menhir *) %token INT %token PLUS %token MINUS %token LPAREN %token RPAREN %token SEMICOLON %start top_expr %% top_expr: | e = expr_nt; SEMICOLON { e } (* Ocaml(10 - 4 + 3) = 9. "-" and "+" operators in Ocaml are left-associative. Ocaml(10 - 4 + 3) = Ocaml((+) ((-) 10 4) 3) = 9. If you see 8 + 17 + 3 + 4 ==> 25 + 3 + 4 ==> 28 + 4 ==> 32. Ourparser(10 - 4 + 3) = 3. "right-associative" Ourparser(10 - 4 + 3) = Ourparser((-) 10 ((+) 4 3)) = 3. Ourparser: 8 + 17 + 3 + 4 ==> 8 + 17 + 7 ==> 8 + 24 ==> 32. *) expr_nt: | c = INT { Int c } | e1 = expr_nt; MINUS; c = INT { Minus(e1, Int c) } | e1 = expr_nt; MINUS; LPAREN; e2 = expr_nt; RPAREN { Minus(e1, e2) } | e1 = expr_nt; PLUS; c = INT { Plus(e1, Int c) } | e1 = expr_nt; PLUS; LPAREN; e2 = expr_nt; RPAREN { Plus(e1, e2) } | LPAREN; e = expr_nt; RPAREN { e }