CSCI 2041 Lab11: Expression Evaluation
- Due: 11:59pm Tue 11/27/2018
- Approximately 0.83% of total grade
- Submit to Canvas
- Lab exercises are open resource/open collaboration. You must submit your own work but you may freely discuss lab topics with other members of the class.
CODE DISTRIBUTION: lab11-code.zip
- Download the code distribution every lab
- See further setup instructions below
CHANGELOG:
- Tue Nov 20 10:54:40 CST 2018
- The original version of
parsetree_string
had a minor bug in which the.else_expr
was printed where the.then_expr
was supposed to be and vice-versa. This has now been corrected in the code pack or you can download only the corrected function here: parsetree_string.ml - Mon Nov 19 10:22:41 CST 2018
Lab 11's parser in
lex_parse_eval.ml
contained a bug which gave equal precedence to addition/subtraction and multiplication/division. This leads to incorrect results in some cases. The proper precedence ordering should beLowest: Add Sub Mul Div :Highest
The parser has been adjusted to fix this.
1 Rationale
In language processing, the result of lexing and parsing input is usually a data structure which can be either further processed or evaluated. Thus, a 3-part system of lexer/parser/evaluator is a standard way to interpret simple programming languages. The code for evaluation usually must have some context in the form of environments for variable name bindings to values. In simple cases this is often an abstract map from names to values via a tree or hash table.
This lab covers a simple lexer/parser/evaluator. It extends the
previous arithmetic language to include let/in
bindings and
if/then/else
constructs giving it more of a programming language
feel than a simple calculator.
Grading Policy
GRADING NOTE: Due to the Thanksgiving holiday break, this lab may be checked off during a student's assigned Lab 12 section on Mon 11/26 and Tue 11/27.
- Check-off 30%: Demonstrate to a TA that a student understands answers to questions. This must be done in person in groups of one or two. Check-offs can happen during the lab period of during a TA office hour.
- Submit 70%: Submit required files according to the lab instruction. This can be done at any time and from anywhere with a network connection. Submitting does not require attending lab. All students must submit files even if they were checked off in a group during lab.
See the full policy in the syllabus.
2 Codepack
The codepack for the lab contains the following files:
File | State | Description |
---|---|---|
QUESTIONS.txt |
Edit | Answer questions in the file to complete the lab |
lex_parse_eval.ml |
Edit | Problem 1/2 file to analyze and edit |
lpe_main.ml |
Edit | Main function which allows experimentation with expression evaluation |
3 Questions
Analyze the files in the provided codepack and answer the questions
given in QUESTIONS.txt
.
__________________ LAB 11 QUESTIONS __________________ - Name: (FILL THIS in) - NetID: (THE kauf0095 IN kauf0095@umn.edu) Answer the questions below according to the lab specification. Write your answers directly in this text file and submit it to complete the lab. Files `lex_parse_eval.ml' and `lpe_main.ml' =========================================== This lab deals with a lexer, parser, evaluator system for a small language that includes arithmetic, `let/in' expressions, and `if/then/else' expressions. `lex_parse_eval.ml' is primarily responsible for this and is divided into 4 sections that handle a simple arithmetic language with some more programmatic elements. The 4 sections are: 1. Lexer: which converts a character string into a list of tokens. 2. Parser: which converts a list of tokens into an expression tree, often referred to as a Parse Tree or Abstract Syntax Tree (AST). 3. Evaluator: which analyzes the expression tree and computes a numeric result. 4. To-string functions: which are used to convert token lists and parse trees to strings that can be printed. The functions in `lex_parse_eval.ml' are used in the file `lpe_main.ml' which takes an expression from the command line and performs lexing, parsing, and evaluation on it. Here are some examples though the examples for `if/then/else' won't work until the lab is completed. ,---- | > ocamlc lex_parse_eval.ml lpe_main.ml | | > ./a.out '1' | Tokens: | [Int(1)] | | Parse Tree: | IConst(1) | | Result: | Int(1) | | > ./a.out 'true' | Tokens: | [Bool(true)] | | Parse Tree: | BConst(true) | | Result: | Bool(true) | | > ./a.out '1+2' | Tokens: | [Int(1); Plus; Int(2)] | | Parse Tree: | Add | IConst(1) | IConst(2) | | Result: | Int(3) | | > ./a.out '1+2*3' | Tokens: | [Int(1); Plus; Int(2); Times; Int(3)] | | Parse Tree: | Add | IConst(1) | Mul | IConst(2) | IConst(3) | | Result: | Int(7) | | > ./a.out 'if false then 1+2*3 else 4*5' # WON'T WORK UNTIL LAB IS COMPLETED | Tokens: | [If; Bool(false); Then; Int(1); Plus; Int(2); Times; Int(3); Else ; Int(4); | Times; Int(5)] | | Parse Tree: | Cond | .if_expr: | BConst(false) | .then_expr: | Mul | IConst(4) | IConst(5) | .else_expr: | Add | IConst(1) | Mul | IConst(2) | IConst(3) | | Result: | Int(20) | | > ./a.out 'let x=5 in let y=2 in x*y' | Tokens: | [Let; Ident(x); Equal; Int(5); In; Let; Ident(y); Equal; Int(2); In; | Ident(x); Times; Ident(y)] | | Parse Tree: | Letin( x ) | .var_expr: | IConst(5) | .in_expr: | Letin( y ) | .var_expr: | IConst(2) | .in_expr: | Mul | Varname(x) | Varname(y) | | Result: | Int(10) `---- PROBLEM 1: Lexer and Parser =========================== (A) ~~~ In addition to arithmetic, the lexer/parser/evaluator understands two additional features 1. `if/then/else' constructs for conditional execution 2. `let/in' expressions as `let x=1+2 in x*7' for binding names to values Examine the first section of `lex_parse_eval.ml' which contains the lexer. Explain what tokens exist for the keywords like `let' and `if' and how the lexer creates these tokens versus variable name `Ident' tokens. (B) ~~~ Examine the second section of `lex_parse_eval.ml' which contains the parser. Examine the `expr' type which represents the tree-like structure of parsed expressions. Describe the new entries in this type that correspond to `if/then/else' and `let/in' constructs. Describe their parts and whether expression trees will always be binary trees. (C) ~~~ The parser is somewhat more complex then previous versions but has many of the same features in that it is comprised of a series of mutually recursive functions. However some cosmetic differences are immediately apparent. - The names of the parsing elements do not mention their precedence but instead name the kind of element they handle such as `parse_add' and `parse_cond'. Some of these such as `parse_add' handle more than `Add' tokens but this should be easy to interpret. - The parsing functions, starting with `parse_expr' are shown in source code "top-down" with lower-precedence `parse_add' coming before higher-precedence `parse_mul'. Examine the parsing functions carefully and answer the following questions. 1. Is the parsing of `let/in' and `if/then/else' expressions higher or lower precedence than adding and multiplying? 2. Functions like `parse_add' make recursive calls to themselves to try to parse more additions. Is this what `parse_letin' and `parse_cond' do? Why or why not? 3. Functions like `parse_add' first attempt to call higher-precedence parsing functions like `parse_mul'. They then use the results in an addition. Is the same done by `parse_letin' and `parse_cond'? Why or why not? PROBLEM 2: Evaluator ==================== (A) ~~~ Examine the third section of `lex_parse_eval.ml' which contains the Evaluator. This portion defines types and functions relevant to walking through an expression tree generated by the parser to evaluate an answer. The first few lines of the evaluator lay out a type `varval' for results and create a `varmap_t' type to map string names. Answer the following questions about this section. 1. Describe the kinds of value that can result for evaluation or be let-bound via `let/in' bindings. 2. How is OCaml's standard library used to easily derive functions for adding and looking up variable bindings in the `varmap_t'? What standard functor is used? 3. Will the variable maps be mutable or immutable? (B) ~~~ Examine the `eval_expr' function which is where most of the work of the evaluator is performed. Answer the following questions. 1. What two arguments does `eval_expr' take? What types are they as inferred by looking through the rest of the code? 2. What action is taken when a `Varname' expression is found and what error can result? 3. Inspect how the different arithmetic operators are handled. Describe how the common task of evaluating the left/right child expressions is handled while still performing appropriate arithmetic operations. 4. Analyze the `Letin' case within `eval_expr'. Describe how a new binding is created in a `let/in' expression. (C) ~~~ The code for the `Cond' case is not complete so `if/then/else' expressions will not evaluate yet. Fill in the gaps marked `EDIT ME' to complete this code. - Evaluate the `c.if_expr' to determine if the test is true or false - When b is true, evaluate c.then_expr - When b is false, evaluate c.else_expr Paste your code below as your solution. Optional Extras =============== Currently the lexer/parser/evaluator does not handle numeric comparisons to produce boolean results such as ,---- | 5 < 2 -> Bool false | if 1+2 > 0 then 8 else 4 -> Int 8 `---- This will be a required part of the final assignment interpreter so it would be an excellent exercise to extend the system to handle these new expression types. - Extend the lexer to include < and >. The = sign is already part of the lexer. - Extend the expression type to include comparison expressions for Less, Greater, Equal with constituent left/right expressions (like arithmetic). - Extend the parser functions with a new function to parse comparisons. This should occur at a lower precedence than arithmetic. - Extend the evaluator to include evaluation cases for comparisons. These should check that their left/right expressions are integers, do the appropriate comparison on the numbers, and return a Bool. You may wish to model them after the arithmetic evaluation code.
4 What to Understand
Ensure that you understand
- Basic information flow from lexer to parser to evaluator
- Basic structure of an expression evaluator which walks the parse tree to perform relevant operations
- How variable name bindings can be tracked in an abstract map and how
language constructs like
let/in
can be used to alter the map for further expressions
5 Getting Credit: Submit and Check-off
- Check-off your answers with a TA in person during lab or office hours.
- Submit your completed
QUESTIONS.txt
file to Canvas under the appropriate lab heading. Make sure to paste in any new code and answers you were to write at appropriate locations in the file.