$35
Project 4A: SmallC Parser Solution
## Introduction
In this project, you will implement the lexer and parser for SmallC, which is the input language of the interpreter you will write in project 4B. This parser will be capable of parsing expressions, statements, and full programs, thus making it a complete replacement for the parser we supplied for the interpreter project. The parser will operate on a flat `token list` assembled by your lexer and create a correct `stmt` and/or `expr` corresponding to the input. When you're done, you will have written the complete pipeline to turn a text file into a running SmallC program!
The only requirement for error handling is that input that cannot be lexed/parsed according to the provided rules should raise an `InvalidInputException`. We recommend using relevant error messages when raising these exceptions, as it will make debugging easier.
All tests will be run on direct calls to your code, comparing your return values to the expected return values. Any other output (e.g., for your own debugging) will be ignored. You are free and encouraged to have additional output.
### Ground Rules
In your code, you may use any OCaml modules and features we have taught in this class (If you come asking for help using something we have not taught we will direct you to use methods taught in this class). You may even choose to use imperative OCaml, but are not required to.
### Testing
Build the interface with `dune build bin/interface.bc`. Then you can run your lexer or parser directly on a SmallC program by running `dune exec bin/interface.bc lex [filename]` or `dune exec bin/interface.bc parse [filename]` where the `[filename]` argument is optional.
You can run the tests as usual with `dune runtest -f` and test from the toplevel with `dune utop src`.
## Part 1: The Lexer
Before your parser can process input, the raw file must be transformed into logical units called tokens. This process is readily handled by use of regular expressions. Information about OCaml's regular expressions library can be found in the [`Str` module documentation][str doc]. You aren't required to use it, but you may find it very helpful. Note that a lexer is the same as a scanner, which is discussed in the lecture slides.
Your lexer must be written in `lexer.ml`. You will need to implement the function `tokenize : string - token list` which takes as input the program as a string and outputs the associated token list. The `token` type is implemented in [`smallCTypes.ml`](./smallCTypes.ml).
Your lexer must meet these general requirements:
- Tokens can be separated by arbitrary amounts of whitespace, which your lexer should discard. Spaces, tabs ('\t') and newlines ('\n') are all considered whitespace.
- The lexer should be case sensitive.
- Lexer input should be terminated by the `EOF` token, meaning that the shortest possible output from the lexer is `[EOF]`.
- If the beginning of a string could be multiple things, the longest match should be preferred, for example:
- "while0" should not be lexed as `Tok_While`, but as `Tok_ID("while0")`, since it is an identifier
Most tokens only exist in one form (for example, the only way for `Tok_Pow` to appear in the program is as `^` and the only way for `Tok_While` to appear in the program is as `while`). However, a few tokens have more complex rules. The regular expressions for these more complex rules are provided here:
- `Tok_Bool of bool`: The value will be set to `true` on the input string "true" and `false` on the input string "false".
- *Regular Expression*: `true|false`
- `Tok_Int of int`: Valid ints may be positive or negative and consist of 1 or more digits. You may find the function `int_of_string` useful in lexing this token type.
- *Regular Expression*: `-?[0-9]+`
- `Tok_ID of string`: Valid IDs must start with a letter and can be followed by any number of letters or numbers. Note that keywords may be contained within IDs and they should be counted as IDs unless they perfectly match a keyword!
- *Regular Expression*: `[a-zA-Z][a-zA-Z0-9]*`
- *Valid examples*:
- "a"
- "ABC"
- "a1b2c3DEF6"
- "while1"
- "ifelsewhile"
In grammars given later in this project description, we use the lexical representation of tokens instead of the token name; e.g. we write `(` instead of `Tok_LParen`. This table shows all mappings of tokens to their lexical representations, save for the three variant tokens specified above:
Token Name (in OCaml) | Lexical Representation (in grammars below)
--- | ---
`Tok_LParen` | `(`
`Tok_RParen` | `)`
`Tok_LBrace` | `{`
`Tok_RBrace` | `}`
`Tok_Equal` | `==`
`Tok_NotEqual` | `!=`
`Tok_Assign` | `=`
`Tok_Greater` | ``
`Tok_Less` | `<`
`Tok_GreaterEqual` | `=`
`Tok_LessEqual` | `<=`
`Tok_Or` | `\|\|`
`Tok_And` | `&&`
`Tok_Not` | `!`
`Tok_Semi` | `;`
`Tok_Int_Type` | `int`
`Tok_Bool_Type` | `bool`
`Tok_Print` | `printf`
`Tok_Main` | `main`
`Tok_If` | `if`
`Tok_Else` | `else`
`Tok_While` | `while`
`Tok_Add` | `+`
`Tok_Sub` | `-`
`Tok_Mult` | `*`
`Tok_Div` | `/`
`Tok_Pow` | `^`
Your lexing code will feed the tokens into your parser, so a broken lexer will render the parser useless. Test your lexer thoroughly before moving on to the parser!
## The Parser
Once the program has been transformed from a string of raw characters into more manageable tokens, you're ready to parse. The parser must be implemented in `parser.ml` in accordance with the signatures for `parse_expr`, `parse_stmt` and `parse_main` found in `parser.mli`. `parser.ml` is the only file you will write code in. The functions should be left in the order they are provided, as a good implementation will rely heavily on earlier functions.
We provide an **ambiguous** CFG for the language that you must convert to be right-recursive and right-associative, so it can be parsed by recursive descent. (By right associative, we are referring to binary infix operators—so something like `1 + 2 + 3` will parse as `Add(Int(1), Add(Int(2), Int(3)))`, essentially implying parentheses in the form `(1 + (2 + 3))`.) As convention, in the given CFG all non-terminals are capitalized, all syntax literals (terminals) are formatted `as non-italicized code` and will come in to the parser as tokens from your lexer. Variant token types (i.e. Tok_Bool, Tok_Int, and Tok_ID) will be printed *`as italicized code`*.
## Part 2: `parse_expr`
Expressions are a self-contained subset of the SmallC grammar. As such, implementing them first will allow us to build the rest of the language on top of them later. Recall the `expr` type from project 3b:
```
type expr =
| ID of string
| Int of int
| Bool of bool
| Add of expr * expr
| Sub of expr * expr
| Mult of expr * expr
| Div of expr * expr
| Pow of expr * expr
| Greater of expr * expr
| Less of expr * expr
| GreaterEqual of expr * expr
| LessEqual of expr * expr
| Equal of expr * expr
| NotEqual of expr * expr
| Or of expr * expr
| And of expr * expr
| Not of expr
```
The function `parse_expr : token list - token list * expr` takes a list of tokens and returns a tuple of the remaining tokens and the `expr` that was parsed. Examples in class used a more imperative style with a global reference, but the `parse_expr` and `parse_stmt` functions in this project use a purely functional style where remaining tokens are returned along with the produced AST types. How you choose to use this part of the return value is up to you, but it must satisfy the same property of finally returning all remaining tokens regardless of your design decisions around it.
The (ambiguous) CFG of expressions, from which you should produce a value of `expr` AST type, is as follows:
- Expr - OrExpr
- OrExpr - OrExpr `||` OrExpr | AndExpr
- AndExpr - AndExpr `&&` AndExpr | EqualityExpr
- EqualityExpr - EqualityExpr EqualityOperator EqualityExpr | RelationalExpr
- EqualityOperator - `==` | `!=`
- RelationalExpr - RelationalExpr RelationalOperator RelationalExpr | AdditiveExpr
- RelationalOperator - `<` | `` | `<=` | `=`
- AdditiveExpr - AdditiveExpr AdditiveOperator AdditiveExpr | MultiplicativeExpr
- AdditiveOperator - `+` | `-`
- MultiplicativeExpr - MultiplicativeExpr MultiplicativeOperator MultiplicativeExpr | PowerExpr
- MultiplicativeOperator - `*` | `/`
- PowerExpr - PowerExpr `^` PowerExpr | UnaryExpr
- UnaryExpr - `!` UnaryExpr | PrimaryExpr
- PrimaryExpr - *`Tok_Int`* | *`Tok_Bool`* | *`Tok_ID`* | `(` Expr `)`
The transformation of the above ambiguous grammar into a parsable, non-ambiguous, grammar can be found in the addendum. We encourage you to do the transformation yourself and utilize the addendum to check your work and ensure correctness before coding.
As an example, see how the parser will break down an input mixing a few different operators with different precedence:
### Input:
```
2 * 3 ^ 5 + 4
```
### Output (Stylized to show order):
```
Add(
Mult(
Int(2),
Pow(
Int(3),
Int(5))),
Int(4))
```
## Part 3: `parse_stmt`
The next step to parsing is to build statements up around your expression parser. When parsing, a sequence of statements should be terminated as a `NoOp`, which you will remember as a do-nothing instruction from the interpreter. Recall the `stmt` type:
```
type stmt =
| NoOp
| Seq of stmt * stmt
| Declare of data_type * string
| Assign of string * expr
| If of expr * stmt * stmt
| While of expr * stmt
| Print of expr
```
The function `parse_stmt : token list - token list * stmt` takes a token list as input and returns a tuple of the tokens remaining and the `stmt` that was parsed from the consumed input tokens. The `stmt` type isn't self contained like the `expr` type, and instead refers both to itself and to `expr`; use your `parse_expr` function to avoid duplicate code!
Again, we provide a grammar that is ambiguous and must be adjusted to be parsable by your recursive descent parser:
- Stmt - Stmt Stmt | DeclareStmt | AssignStmt | PrintStmt | IfStmt | WhileStmt
- DeclareStmt - BasicType ID `;`
- BasicType - `int` | `bool`
- AssignStmt - ID `=` Expr `;`
- PrintStmt - `printf` `(` Expr `)` `;`
- IfStmt - `if` `(` Expr `)` `{` Stmt `}` ElseBranch
- ElseBranch - `else` `{` Stmt `}` | ε
- WhileStmt - `while` `(` Expr `)` `{` Stmt `}`
As with the Expression grammar, the transformation to enable the grammar to be parsable can be found in the addendum.
If we expand on our previous example, we can see how the expression parser integrates directly into the statement parser:
### Input:
```
int x;
x = 2 * 3 ^ 5 + 4;
printf(x 100);
```
### Output (Stylized to show order):
```
Seq(Declare(Int_Type, "x"),
Seq(Assign("x",
Add(
Mult(
Int(2),
Pow(
Int(3),
Int(5))),
Int(4))),
Seq(Print(Greater(ID("x"), Int(100))), NoOp)))
```
## Part 4: `parse_main`
The last and shortest step is to have your parser handle the function entry point. This is where `parse_main : token list - stmt` comes in. This function behaves the exact same way as `parse_stmt`, except for two key semantic details:
- `parse_main` will parse the function declaration for main, not just the body.
- `parse_main` validates that a successful parse terminates in `EOF`. A parse not ending in `EOF` should raise an `InvalidInputException` in `parse_main`. As such, `parse_main` does NOT return remaining tokens, since it validates ensures that the token list is emptied by the parse.
The grammar for this parse is provided here:
- Main ::= `int` `main` `(` `)` `{` Statement `}` `EOF`
For this slightly modified input to the example used in the previous two sections, the exact same output would be produced:
### Input:
```
int main() {
int x;
x = 2 * 3 ^ 5 + 4;
printf(x 100);
}
```
The output is the exact same as in the statement parser, but `parse_main` also trims off the function header and verifies that all tokens are consumed.
## Academic Integrity
Please **carefully read** the academic honesty section of the course syllabus. **Any evidence** of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, **will be** submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus, which you should review before starting.
[list doc]: https://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html
[str doc]: https://caml.inria.fr/pub/docs/manual-ocaml/libref/Str.html
[pervasives doc]: https://caml.inria.fr/pub/docs/manual-ocaml/libref/Pervasives.html
[git instructions]: ../git_cheatsheet.md
[submit server]: submit.cs.umd.edu
[web submit link]: ../common-images/web_submit.jpg
[web upload example]: ../common-images/web_upload.jpg
