Calculator Parser

Work on this exercise locally

This web app is a reference guide — you can read instructions, browse starter code, and view tests here. To actually complete the exercise, you need to work in your local development environment.

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module0-warmup/exercises/calculator-parser

7. Exercise 5: Calculator Parser (~25 min)

File: exercises/calculator-parser/starter/main.ml (TODO: printing + eval) File: exercises/calculator-parser/starter/parser.mly (TODO: grammar rules) Run:

dune exec modules/module0-warmup/exercises/calculator-parser/starter/main.exe

What You'll Implement

This exercise has two files to edit:

parser.mly -- add grammar rules:

Rule	What It Produces	Provided?
`expr PLUS expr`	`BinOp(Add, e1, e2)`	Yes (example)
`expr MINUS expr`	`BinOp(Sub, e1, e2)`	EXERCISE
`expr STAR expr`	`BinOp(Mul, e1, e2)`	EXERCISE
`expr SLASH expr`	`BinOp(Div, e1, e2)`	EXERCISE
`atom` fallthrough	`a`	Yes (provided)
`INT` literal	`Num n`	Yes (provided)
`IDENT` variable	`Var id`	EXERCISE
`LPAREN expr RPAREN`	`e`	EXERCISE
`MINUS atom %prec UMINUS`	`Neg a`	EXERCISE

main.ml -- implement:

Function	What It Does	Concept
`string_of_op`	Converts op to "+"/"-"/"*"/"/"	Pattern matching
`string_of_expr`	Pretty-prints AST	Recursive pattern matching
`eval`	Evaluates expression	Option + division by zero

Hints

The lexer (lexer.mll) is fully provided -- you do not need to edit it.

Parser rules follow this pattern:

| e1 = expr MINUS e2 = expr  { BinOp (Sub, e1, e2) }

%prec UMINUS tells Menhir to use the UMINUS precedence for unary minus:
```
| MINUS a = atom %prec UMINUS  { Neg a }
```

In main.ml, the types are defined in ast.ml:

type op = Add | Sub | Mul | Div
type expr = Num of int | Var of string | BinOp of op * expr * expr | Neg of expr

Expected Output

=== Exercise 5: Calculator Parser ===

Input:  42
AST:    42
Result: 42

Input:  1 + 2
AST:    (1 + 2)
Result: 3

Input:  3 * 4 + 5
AST:    ((3 * 4) + 5)
Result: 17

Input:  (3 + 4) * 5
AST:    ((3 + 4) * 5)
Result: 35

Input:  10 - 3 - 2
AST:    ((10 - 3) - 2)
Result: 5

Input:  -7
AST:    (- 7)
Result: -7

Input:  x + 1
AST:    (x + 1)
Result: <cannot evaluate>

Done!

Starter Files

starter

starter/ast.ml

Read-only

Loading editor...

Work on this exercise locally

1Clone the repo: git clone https://github.com/weihaoqu/program-analysis-bootcamp-student

2Edit the starter file in your editor (VS Code, Vim, etc.) — replace failwith "TODO" with your implementation.

3Run the tests: dune runtest modules/module0-warmup/exercises/calculator-parser