Assignment 3:  Semantic Checking

Your parser from the last assignment accepts any program that is syntactically valid, and finds as many problems as possible in programs that have syntax errors.  We would like, however, to enforce many rules that a parser and CFG alone cannot guarantee.  For example, if we extend the calculator language to distinguish between integer and floating point numbers (as outlined in Section 4.6 of the textbook), then the following calculator program has a type error: 

   int pi
   pi := 3.1415926
In order to enforce rules like type checking, we’ll need a tool to reject programs that are syntactically valid but violate our semantic rules.  We’ll do this via traversal of an abstract syntax tree.  We won’t, however, be programming in C++:  for this assignment you’ll use Scheme. 

We will provide you with a working parser that produces explicit parse trees.  (It is, in fact, more general than you will need:  it includes an LL(1) parser generator like the one you built for the previous assignment, allowing it to work with any top-down single-lookahead grammar.  Your extensions will be calculator-grammar specific.) 

More specifically, your task in this assignment is to:

  1. Add declarations and types to the calculator grammar (as outlined in Section 4.6 of the book, but with automatic integer-to-floating-point coercion rather than a float routine).  This amounts to modifying the example CFG provided with the Scheme source code.&nsbp; The current version of that grammar looks like this: 
        (define calc-gram
          '(("P"  ("SL" "$$"))
            ("SL" ("S" "SL") ())
            ("S"  ("id" ":=" "E") ("read" "id") ("write" "E"))
            ("E"  ("T" "TT"))
            ("T"  ("F" "FT"))
            ("TT" ("ao" "T" "TT") ())
            ("FT" ("mo" "F" "FT") ())
            ("ao" ("+") ("-"))
            ("mo" ("*") ("/"))
            ("F"  ("id") ("num") ("(" "E" ")"))
           ))
  2. Change the provided code as necessary to handle the modified grammar.  In particular, you will need to distinguish between integer and real number constants in calculator programs.  Note that the built-in integer? function does not do what you want: 
         (integer? 3.0)   => #t
    For simplicity’s sake, you may assume that a floating-point constant is any atom that Scheme accepts as a number, and that contains a decimal point or an exponent.  (This is still a little tricky; see Section 6.2.4 of the Scheme R5 standard.  Note in particular that the letter ‘e’ can indicate an exponent, an exactness specification, or a hexadecimal digit, depending on context.) 
  3. Verify that your modifications work and correctly parse programs that meet the rules of the modified grammar (you are not required to implement syntax error recovery, but may do so for extra credit). 
  4. Build a (calculator-language-specific) routine make-AST that converts a parse tree to an abstract syntax tree (AST).  Note that we are not specifying what the AST should look like.  You can get ideas from the text, but what’s there is incomplete; you’ll have to flesh it out. 
  5. Build another (calculator-language-specific) routine check-semantics that walks the AST and enforces the following semantic rules:  Your check-semantics routine should return a list of all semantic errors, suitable for printing, or () (the empty list) if the input is semantically correct.  If passed #f (the output of the parser on invalid input), your code should return the string “semantic analysis inhibited due to syntax error(s)”. 

If everything works correctly, you should be able to type: 

      (check-semantics (make-AST (parse extended-calc-gram my-program)))
and see a list of errors (if any). 

The initial source code for this assignment is available for download HERE.  It’s about 480 lines of Scheme code.  You should read most of this code carefully to understand how it works (you can skip the details of parse table construction if you like, though I think it’s kind of cool :-). 

Resources

Your program should be written in Scheme, and should not take advantage of any imperative features (no functions of special forms with names ending in !). 

We will be grading your assignment using the “Dr. Scheme” interpreter: /u/cs254/bin/drscheme, set at the “R5RS” language level.  You can also download GUI versions of Dr. Scheme for Windows, MacOS, or Linux, but please be sure to set the language level correctly, and check that your code works correctly on the csug installation.  Here are some resources to help you: 

Division of labor and writeup

As in all assignments this semester, you may work alone or in teams of two.  If you choose to work in pairs, I strongly encourage you to read each others’ code, to make sure you have a full understanding of semantic analysis. 

Be sure to follow all the rules on the Grading page.  As with all assignments, use the turn-in script:  ~cs254/bin/TURN_IN.  Put your write-up in a README.txt or README.pdf file in the directory in which you run the script.  Be sure to describe any features of your code that the TAs might not immediately notice. 

Extra Credit Suggestions

  1. Extend the calculator grammar in other interesting ways (ways that give you other semantic rules to enforce).  You might, for example, implement arrays (no subscripting of scalars); for loops, while loops, or if statements  (no floating-point conditions or bounds); nested scopes (no redefinition within a scope); or functions (must contain a return statement; arguments and return value must match in number and type).
  2. Write a routine to turn the AST into C code, so you can execute the output. 
  3. Alternatively (this is my favorite EC suggestion), extend your code to make a full interpreter.  This is actually pretty easy given what you’ve already got, and can be very satisfying.  All you need is a routine interpret-AST that takes the AST and an input string as input, and then walks the tree, accumulating values and printing results.  (You can use display for output, even though it’s imperative.)  Then wrap your routine as follows: 
        (define interpret
          (lambda (grammar program input)
            (let* ((ast (make-AST (parse grammar program)))
                   (errors (check-semantics ast)))
              (if (null? errors) (interpret-AST ast input) errors))))
    And now you can type
        (interpret my-grammar my-program my-input)
  4. Add warning messages for variables that are used before they are assigned a value, or that are assigned a value and then never used.  Warnings should not inhibit interpretation or code generation (if you’re doing one of those). 
  5. Add syntax error recovery. 

Trivia Assignment

Trivia questions for this assignment can be found in Blackboard.  They are due before the beginning of class on Thursday, October 4

MAIN DUE DATE: 

Monday October 15, at noon; no extensions. 
Last Change:  02 October 2007 / Michael Scott's email address