CSCI 439 lab 2

CSCI 439: Lab 2 (Spring 2025)

Note: the repo should now be accessible (1:15 Wed)

Lab 2 overview:

We'll continue working on the lex/yacc handling of the vurbossity language from lab 1, but now we're adding the context sensitie checking.

Obtaining/submitting the lab will follow the same process as lab1 (though of course the repo is named lab2 this time).

Our objectives in lab2 are to update the lex/yacc so that it correctly:

generates errors if a program contains multiple declarations of the same variable name in the same scope (e.g. "x" is declared twice in the same scope),
generates errors if a program attempts to use a variable that hasn't been declared in an accessible scope,
generates errors if a program contains multiple declarations of the same procedure name,
generates errors if a procedure is called with an incorrect number of parameters or incorrect parameter types,
generates errors if an expression contains incompatible types,
generates errors if an assignment statement contains incompatible types.

With respect to type compatibility, recall that an integer can be assigned to a real but not the reverse, and text is incompatible with both integers and reals.

Starting from a lab1 solution

The lab2 repo begins with a lab2.lex and lab2.yacc that represent the sample solution for lab1 plus some starter code for working with symbol tables and scopes.

The hope is that the sample code gives you a good start on the appropriate syntax and use of the symbol table and scope routines as well as accessing the content of the various tokens/non-terminals.

You are welcome to use your own lab1 solution as a starting point, and can use your own or the provided lab2 lex/yacc code for the context sensitive checking.

What the starter lab2 code provides

In the lab2.lex file

A struct and accompanying global variables to represent a symbol table, where each entry has fields for the variable name, scope, and type. The symbol table itself is simply an array of structs, with a global variable keeping track of the number of entries so far.
A routine to lookup a variable by its name and declaration scope, returning the variable's type if found and -1 if no such variable is found.
A routine to lookup a variable solely by name: this checks the current open scopes (starting at the innermost and working outwards to the global scope), returning the type of the first match found, or -1 if no match is found.
A routine to insert a variable into the symbol table (given its name, scope, and type), returning the insertion position if successful, -1 otherwise (e.g. if the table is full).
A stack of ints representing the ids of the currently-open scopes. Each scope is given a unique integer id, and the stack is simply an array plus a global variable tracking its current size. An init routine sets up the stack with just the global scope id on it, and variables to track the current scope id and a value to be assigned to the next new scope if/when encountered.
A push routine to be called when entering a new scope: this gets an id for the new scope, pushes it on the stack, and returns the id (-1 if the push fails).
A pop routine to be called when exiting a scope: this pops the top scope off the stack, sets the current scope to be the one we're returning to (the new top of stack), and returns the new current scope (-1 if the pop failed).
As each token is scanned it now stores its row and column number and its text string in the storage associated with the token (using yylval and yytext).
In the lab2.yacc file
Added prototypes so the scope/symbol table functions can be called, along with a call in main to run the scope init routine.
A new union type, struct itemInfo, that allows each token and non-terminal to store a row, column, text content, and data type. Note the %token and %type lines have been updated to all use this same struct. (And the .lex file sets the row, column, and text content fields for each token through the yylval variable.)
Context-sensitive checking in the rule for global variable declarations: using one of the lookup routines to check for re-declarations and using the insert routine to insert the new variable into the symbol table.
Context-sensitive additions to the rules for type declarations (dtype rules in the sample solution). Where the source code uses INTEGER, REAL, or TEXT, this appropriately stores the desired type (as 0 for integers, 1 for reals, 2 for text).
Context-sensitive additions to the rules for literal values (literal rules in the sample solution). Where the source code uses INTLIT, REALLIT, or TEXTLIT, this appropriately stores the actual data type.
Context-sensitive checking for cases where an expression is simply an IDENT (one of the expression rules in the sample solution). This checks that the variable has been declared in an accessible scope and records the type of the variable as the type of the expression.
Scope-tracking in the rule for block bodies: pushing on entry to a new scope and popping on exiting a scope. (This is in the body rule in the sample solution.)
A couple of additional test cases
both validprogs and invalidprogs contain one or two additional test cases

What the starter lab2 code doesn't provide (what's left for you to do)

The code currently does not handle inserting local variables into the symbol table (nor does it currently check for redeclarations).
The code currently does absolutely no type-checking in assignment statements, expressions, or parameter passing.
The code currently does not do anything with procedure declarations or calls beyond checking the structural syntax (as per lab1). Some means will need to be added for checking that procedures are not redeclared, that there are no calls to undeclared procedures, and that the number and types of parameters passed in a procedure call are correct.

Suggestions

Tackle the context sensitive checking in the order listed in the "doesn't provide" above: first the local variable declarations, then the type checking, then the procedure handling. Within the latter two I'd also recommend carving off one chunk at a time. (E.g. get type checking working on the basic expressions first, then on the conditional expressions, then on assignments, deal with procedure declarations working before worrying about calls, etc.)
The local variable declarations should be pretty similar to the global ones, so they should be a good starting point.
When working on the type-checking for expressions work bottom-up in terms of the parse tree rules and test with tiny sample programs customized for any checking you've just added..
Handling procedure declarations and calls is likely to be the most challenging:
- It will likely be useful to create something like the symbol table to hold procedure declarations, with insert and lookup routines. These won't need to track scope (since they're all global), but should probably record the name and the number of parameters.
- You'll also need to record the names, types, and order of all the parameters for each function (another table? additional fields in your procedures table entries?)
- In the calls to procedures you'll need to check that the procedure has actually been declared, that the correct number of parameters are being passed, and that a compatible type is being passed for each of the parameters.