Project II

Due: Monday, 7 April, Monday, 14 April, at 11:59PM.

The goal of this project is to create a top-down parser for a simple grammar. The gammar will describe a language that contains expressions, if statements, and while loops. You will also have to keep track of types.

Your project will involve the creation of one main function (you may have many smaller helper functions). This function is:

parse. This function takes the first taken of the source program and returns a parse tree of that program.

Requirements

You must check the syntax of the source program against every rule and return a syntax error if the syntax of the source code is wrong. You have to identify the rule that was violated in your error statement, but don't have to identify exactly what's wrong with the syntax.

Your parser must continue parsing as long as possible to recognize as many errors as possible.

Your parser must return a parse tree of the given program. This tree should be in the format discussed in class. A list will represent an internal node of the parse tree and a symbol will represent a leaf. There will be no nonterminal symbol stored for an internal node.

You must maintain a symbol table. This table will take the form of a list. In the list will be pairs of (type variable). So if a program has the following declarations:

beginD int x float y int g endD

Then the symbol table would look like

( (int x) (float y) (int g))

Since there is no nested scope in our language (i.e., no blocks and no subroutines), no variable should be declared twice. If a variable is declared twice, you must recognize the error.

You must supply at least two functions to manipulate the symbol table, findSym and addSymbol. The former function will take two parameters, a type and a variable and destructively add these to the symbol table. To destructively update the symbol table use the function (set! symTab newValue). This is like doing an assignment statement in Java or C++: symTab = newValue.

The function findSym will take two parameters, a symbol (i.e., the variable you want to find in the symbol table) and a list (i.e., the symbol table). It must recursively search for the symbol in the symbol table and return true if the symbol is in the table and false otherwise.

Do not allow a variable to be declared twice. This is not part of the grammar and does not have to be handled via attributes. Instead, you can just search the symbol table for a variable each time you enter a new (type var) pair into the symbol table.

Provided functions

You will be given the following functions.

getToken Takes no arguments, returns the next token in the input string. The token will be of type symbol.

pushBack Takes one argument, a token, and adds it back into the beginning of the input stream. It will be convenient to be able to add a token back into the input stream since you may not destructively update a global nextToken value.

error Takes any number of parameters and prints them all out on the same line. Intended to be used to display syntax errors. Returns the string "error"

last Takes a list and returns the last item in that list.

beginParse Takes a string that contains your source program. Does proper initialization and then calls your function parse with the first token in the source code.

Constraints

You should use the language "Pretty Big" under "PLT". This will allow you to use the debugger.

You will use the grammar from problem set 4. The grammar, of course, must be modified as stated in the problem set, but the language that you implement must be the same as the language defined by the grammar given in problem set 4.

5% of the grade for the project will be given for adding a loop. The loop will act as follows:

loop <boolean_expr> beginL <SPoc_stmt_list> endL

You are to integrate this into your grammar and parse it with your parser.

For the functions given about to work, you must include the following code at the beginning of your file:

(require (lib "string.ss"))
(define tokens '())
(define symTab '( () ))

You may not use any imperative features in any of your functions. This means that the only control method you can use is recursion and that you can only define variables via let or letrec expressions. You may not use sequential execution in any of your functions. You may use the functions given in this project even though they contain imperative features. I've isolated all the imperative features that you will need in this project in these functions.

The only exception to the previous rule is addSymbol function. You may use sequential contol in this function and may use the set! function to change the value of the symTab variable (and only this variable).

You may define global constants, but may not create global variables that are changed. The one exception to this rule is the variable symTab that is created by the provided code and which you may change only in the function addSymbol. The global variable tokens is changed by the provided code, but you many not change this variable in any of your own code.

You may use a the built-in functions exact? and inexact? to test for integers and float numbers respectively.

Your code must be well commented and meet the standards provided in COMP 171 and COMP 220. 10% of the project grade will be given for comments.

Testing

You can use the following test strings. I will use additional test strings when I test your solutions.

(define testStr1 "program beginD int x endD  x = 10 $ end") 
(define testStr2 "program beginD int x int y endD x = y + 10 $ end")
(define testStr3 "program beginD int x float y float x endD x = 10 $ end") 
(define testStr4 "program beginD int x int y endD x = 10 $ y = x + 5 $ end")
(define testStr5 "program beginD int x endD x = 10 * 2 $ end")
(define testStr6 "program beginD int x endD x = 10 + 2 * 5 $ end")
(define testStr7 "program beginD int x float y float x endD x =  $ end") 

(display "Testing testStr1: ")
(newline)
(beginParse testStr1)
(newline)
(display "Testing testStr2: ")
(newline)
(beginParse testStr2)
(newline)
(display "Testing testStr3: ")
(newline)
(newline)
(beginParse testStr3)
(newline)
(display "Testing testStr4: ")
(newline)
(beginParse testStr4)
(newline)
(display "Testing testStr5: ")
(newline)
(beginParse testStr5)
(newline)
(display "Testing testStr6: ")
(newline)
(beginParse testStr6)
(newline)
(display "Testing testStr7: ")
(newline)
(beginParse testStr7)

Welcome to DrScheme, version 371 [3m].
Language: Pretty Big (includes MrEd and Advanced Student).


Testing testStr1: 
(PROGRAM ((int x)) ((x = ((10)) $)) END)

Testing testStr2: 
(PROGRAM ((int x) (int y)) ((x = ((y)) + ((10)) $)) END)

Testing testStr3: 

Error: Symbol already declared!  x
(PROGRAM ((int x) (float y) "error") ((x = ((10)) $)) END)

Testing testStr4: 
(PROGRAM ((int x) (int y)) ((x = ((10)) $) (y = ((x)) + ((5)) $)) END)

Testing testStr5: 
(PROGRAM ((int x)) ((x = ((10) * (2)) $)) END)

Testing testStr6: 
(PROGRAM ((int x)) ((x = ((10)) + ((2) * (5)) $)) END)

Testing testStr7: 
Error: Symbol already declared!  x
Error: Improper expr syntax:  $
(PROGRAM ((int x) (float y) "error") ((x = . "error")) END)
>

Deliverables

A file containing all of your definitions should be placed in the Faculty/barrj/CS321/turn-in/project2 folder on Nova.

Grading

Requirement Percent

Comments 10%

Basic grammar with expressions 75%

if statements 10%

while statements 5%

Code

You must include the following functions in your solution. Note that these functions provide a global input string and a global symbol table. To run your parser you should call the function beginParse and pass it a string that contains the program to be parsed. beginParse will call your function parse and pass it the first token from the input stream.

(require (lib "string.ss"))
(define tokens '())

(define symTab '( () ))

(define getToken
  (lambda ()
    (cond
      ((equal? tokens '()) '())
      (else
       (let ((first (car tokens)))
         (set! tokens (cdr tokens))
         first)))
    ))

(define pushBack
  (lambda (token)
    (set! tokens (cons token tokens))
    '()
    ))

(define error
  (lambda args
           (display "Error:")
           (for-each (lambda (value) (display " ")(display value)) args)
           (newline)
           "error"))

(define last
  (lambda (ls)
    (cond
      ((null? ls) ls)
      ((null? (cdr ls)) (car ls))
      (else
       (last (cdr ls))))
    ))

(define beginParse
  (lambda (src)
    (set! tokens (read-from-string-all src))
    (set! symTab '(()) )
    (parse (getToken))))

Last updated on 05 Apr 2008 by John Barr

Requirement	Percent
Comments	10%
Basic grammar with expressions	75%
if statements	10%
while statements	5%