CSCI 2041 Lab10: Lexing and Parsing

                           __________________

                            LAB 10 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.


PROBLEM 1: lexer.ml
===================

(A)
~~~

  Examine `lexer.ml'. The central function of interest is `lex_string'
  which is intended to process a string with an arithmetic expression in
  it and produce a list of tokens of the `token' type defined at the top
  of the file.

  Study the given code carefully and answer the following questions on
  how it works.

  1. The code makes use of recursion. Describe how recursion is used to
     process the entire string and to produce a list of the tokens that
     are found.

  2. There is a loop associated with digits. Why is this needed while no
     loop is needed for the other cases of tokens?

  3. Demonstrate some uses of `lex_string' in a REPL to show that it
     works.


(B)
~~~

  Extend the code in `lexer.ml' to account for the following new kinds
  of tokens.
  1. Subtraction with the Minus (-) sign - like Addition
  2. Division with the Slash (/) - like multiplication
  3. Identifiers of strings (abbreviated Ident) - like Int of integers.

  To complete the extension, make the following three modifications.
  1. Add in a variant to the `token' type for each of Minus, Slash,
     Ident.
  2. In `lex_string', extend the `match/with' single character cases to
     include one for - and / associated with Minus and Slash. These will
     behave similarly to their Plus and Times counterparts.
  3. Add in a case for character data which will become Ident cases and
     be similar to Int. Make use of the provided `is_letter' function to
     help identify letters.

  Once you have completed the modifications, uncomment the provided
  examples at the end of the file to ensure the modifications compile
  and work.  Try out the `lex_string' in a REPL.


PROBLEM 2: `parser.ml'
======================

(A)
~~~

  Examine `parser.ml'. This file contains a solution for Problem 1's
  lexer as it is required for the parser (this is also useful if you get
  stuck).

  The central function of interest is `parse_tokens' which converts a
  list of `tokens' into a tree structure which will be referred to as a
  Parse Tree or Abstract Syntax Tree (AST). This tree is comprised of
  variants of the `expr' type defined midway through the file.

  Describe the kinds of elements in the `expr' type and what kinds of
  data they carry. Note how this creates a tree structure.


(B)
~~~

  The code for `parse_tokens' uses recursion to perform the
  parsing. Notice its structure of dividing the task into 4 mutually
  recursive functions:
  1. prec0 which handles Int and OParen/CParen tokens.
  2. prec1 which handles Times tokens
  3. prec2 which handles Plus tokens
  4. parse which serves as an entry point for the beginning of parsing.

  Answer the following questions about how each of these work.

  1. Functions `prec2' starts by calling `prec1' and prec1 starts by
     calling prec0.  In both situations, a pair of `(lexpr, rest)' are
     returned.  What types are the `lexpr' and `rest' and how are they
     used?
  2. `prec0' matches in one case the `OParen' token which corresponds to
     `(' in the input.  This is handled by calling the `parse'
     function. Describe what effect this has in parsing. What happens if
     there is no `CParen' (closing paraenthesis `)' ) in the input?
  3. Try running `parse_tokens' on the following inputs as follows and
     report your results. Each of these will raise an error. How the
     code reaches this error.

  ,----
  | # parse_tokens (lex_string "5+10+");;
  | # parse_tokens (lex_string "5+10+11 )");;
  | # parse_tokens (lex_string "5*10+11 9");;
  | # parse_tokens (lex_string "5+10+11 + +");;
  | # parse_tokens (lex_string "5*(10+11");;
  `----


(C)
~~~

  Modify the parser to accommodate the new tokens - and / and string
  identifiers.  Add in the following variants type to the `expr' type.
  - `Sub' which corresponds to the `Minus' token and is similar to `Add'
  - `Div' which corresponds to the `Slash' token and is similar to `Mul'
  - `Varname' which corresponds to the `Ident' token and is similar to
    `Const'

  Note that each of these has analogues already in the parser.

  CORRECTED INSTRUCTIONS
  - Handle `Ident' tokens in the `prec0' function. It should create a
    `Varname' expression similar to `Int'. It is at the same precedence
    level as `Int' so can be in the same function.
  - Handle `Slash' tokens in a new `prec1_div' function. It should
    create a `Div' expression similar to `Mul' but be at a higher
    precedence than `prec1'.
  - Handle `Minus' tokens in a new `prec2_sub' function. It should
    create a `Sub' expression similar to `Add' but be at a higher
    precedence than `prec2'.

  ORIGINAL INCORRECT INSTRUCTIONS
  - Handle `Minus' tokens in the `prec2' function. It should create a
    `Sub' expression similar to `Add'
  - Handle `Slash' tokens in the `prec1' function. It should create a
    `Div' expression similar to `Mul'.
  - Handle `Ident' tokens in the `prec0' function. It should create a
    `Varname' expression similar to `Int'.

  When you complete the parser extensions, uncomment the code at the end
  of the file which allows you to test it in a REPL.