In this assignment will you will implement a syntax checking SLR(1) parser, a symbol table(s), and perform semantic analysis on a simple programming language grammar. The name of your application must be ZOBOS (case sensitive).

Input

ZOBOS will accept three command line parameters:

Coding

ZOBOS will do do the following:

1. Your compiler will parse a token stream (the output of LUTHOR) with the LR knitting needles algorithm (pseudo code here), using this SLR table (the format is described in lga-code-prep.pdf) and the zlang.cfg grammar. Syntax error messages will be produced in a consistent manner to facilitate grading.

   • If program source has a syntax error, the remaining steps for ZOBOS are not to be performed and ZOBOS should exit() with a non-zero exit status.

2. Either during the parse (using syntax directed translation procedures during production rule reduction, show_lr-knitting-with-sdt.pdf, lga-sdt.pdf), after the parse using visitor patterns, or a combination of these methods; ZOBOS will construct an abstract syntax tree with the following properties

   1. all EXPR (sub)trees will be simplified so that

      1. leaves are either literals (intvals, floatvals) or variables (identifiers holding a value, not function names)

      2. the root and internal nodes are either one of the operations associated with the non-terminals BOOLS, PLUS, MULT, UNARY, or CAST, a FUNCALL node or a node.

   2. control structures IF, IFELSE, WHILE, DOWHILE, STEPS, SOLOSTMT, and BRACESTMTS will be simplified in the spirit of textbook figure 7.15 (lga-sdt.pdf) --- essentially lose the terminals, keep the functional children (blocks of statements, predicate expressions).

   Simplification of all other grammar constructs are at the student's discretion and inclination. They will not be graded.
   There are example .src and AST PDFs in the zobos-resources archives for download.

   Outside of the rules listed above, you are not required to duplicate the ASTs provided, they serve as examples!

3. ZOBOS will write to disk a simple tree representation of its AST.

4. ZOBOS will then use a scope respecting symbol table and visitor pattern(s) to perform several semantic checks on the variable, expression and function use within the parsed program source.

   1. Warnings or error messages will be emitted in a consistent and simple manner to facilitate grading.

   2. When the special EMIT form of symtable is encountered during this process, your ZOBOS will write the symbol tables for all scopes to disk in a simple format to facilitate grading.

   3. When a special domain node is encountered, the domain of its expression tree child should be emitted in a in a format similar to ERRORs to facilitate grading. The possible domain values are int, float, string or bool.

5. Lastly, ZOBOS will exit(0) if there were no errors detected in the program, and exit(1) otherwise.

   WARNING and DOMAIN messages are not ERROR messages

The ZOBOS language

The language compiled for this project is "C-like", but with some caveats and nuances. See this page for details.

Syntax and Semantic Checks

Your ZOBOS compiler will inspect the program.tok for these types of errors and inconsistencies.

Symbol Table Contents and Functions as (sort of a) Type

While functions are not first class objects in our language, we will adopt semantics around function prototypes and definitions so that ERROR and WARN messages, as well as the symbol table contents don't have to be specialized for function types. A symbol table should have the following (minimum) attributes per entry for ZOBOS success:

• location (line and column reported for the identifier token, see here for function definitions and prototypes),

• identifier (name), or a reference into a namespace if you've chosen that approach

• type (see here for function "types"),

• a const flag,

• a "used" or "unused" flag,
• an "initialized" or "uninitialized" flag.

When an identifier for a function is encountered, its value in the symbol table depends on the source context:

1. When a function prototype is encountered, the symbol is considered not const, but already initialized.

2. When a function definition is encountered the symbol has its const flag set (or is created with its const and initialized flag true).

These semantics mean your ZOBOS does not have to have different logic for processing variables versus functions (aside from the initial management of function symbols just described). The lion's share of function specific code producing output is for CALL error messages.

Expression Value Propagation Rules and Errors (EXPR)

See this section in zlang for a description of how the type of an expression propagates up an expression tree to its root. The remaining discussion is specific to EXPR semantic checks.

Is it ever safe to stop looking for EXPR errors in poorly formed expression trees? Evaluation of an expression tree works from the bottom up (recursion is used to get down to the bottom).

1. Each node should look for EXPR errors under each child branch.

2. When an EXPR error occurs in any child, a parent node can no long evaluate the correctness of its operation and so should not emit any EXPR errors.

3. If none of a parent node's children report EXPR errors, the parent should evaluate the correctness of its operation.

4. Except for the root, all nodes communicate either an error condition or a resultant value type for its operation to its own parent.

5. domain nodes in an expression tree simply propagate their child node's value type (domain) or an EXPR error condition to their parent. DOMAIN OUTPUT lines should only be generated when there are no EXPR errors from the child node.

OUTPUT

ZOBOS will report four types of data to three different files.

Syntax, Warning and Error Messages

These will be written to system stdout and must be prefixed by the token OUTPUT as described by the course submission requirements. These messages will have four critical parts emitted in this order:

1. the type of message :TYPE:, enclosed with colons¹ where TYPE is one of (all capitals) SYNTAX, ERROR, or WARN.

2. the line number of the error in the source (see Terminal Location column of syntax, error, and warning table)

3. the character number of the error in the source (see Terminal Location column of syntax, error, and warning table)

4. the ID for the message type

The line and character number come from the program.tok token stream. For a SYNTAX error it is the location of the offending token or the the last good token iff the syntax error occurs because there are no more tokens to be parsed. For WARN and ERROR messages, the location to report is detailed here.

Example Syntax Error Output

Since we abort all tasks on a syntax error, there should only be one SYNTAX error ever printed on stdout. You are permitted to print other information, just don't put it on the required OUTPUT line:

OUTPUT :SYNTAX: 11 1 :SYNTAX:
Parsing error in state 155; input: rbrace; expected=bool|const|emit|float|id|if|int|rand|string|while

Expression Tree DOMAIN Messages

These will be written to system stdout and must be prefixed by the token OUTPUT as described by the course submission requirements.

The following are examples of DOMAIN messages from domain.vrb:

OUTPUT :DOMAIN: 1 9 :int:
OUTPUT :DOMAIN: 2 11 :float:
OUTPUT :DOMAIN: 3 10 :bool:
OUTPUT :DOMAIN: 4 12 :string:

The line and column number for DOMAIN messages are the location of the domain terminal in the source and provided to your parser in the token steam file (.tok).

Abstract Syntax Tree

ZOBOS will write its abstract syntax tree to the filename specified by the second command line parameter. The format of this file is in two parts. The first part is a line by line declaration of a tree node id and name, separated by white space. If a name is not provided the id is used.

An empty line separates the the first part from the second part.

The second part is a line by line description of tree edges. The first id on the line is the parent, subsequent ids are the children in left to right order. If a parent id is mentioned more than once, children are simply arranged in left to right, file order. The following two AST descriptions in this format yield the same tree graph:

A A
B  
C cee
D delta

A B C D

A A
B  
C cee
D delta

A B 
A C D

string word = "hello world";
int speak()
returns r = 0
{
    emit word, 0, 11;
}

0 MODULE
0-0 DECLLIST
0-0-0 type:string
0-0-1 DECLID
0-0-1-0 =
0-0-1-0-0 id:word
0-0-1-0-1 stringval:hello world
0-1 FUNCTION
0-1-0 FUNSIG
0-1-0-0 type:int
0-1-0-1 id:speak
0-1-0-2 PARAMLIST
0-1-1 =
0-1-1-0 id:r
0-1-1-1 intval:0
0-1-2 STEPS
0-1-2-0 scope:open
0-1-2-1 EMIT
0-1-2-1-0 id:word
0-1-2-1-1 intval:0
0-1-2-1-2 intval:11
0-1-2-2 scope:close

0-0-1-0 0-0-1-0-0 0-0-1-0-1
0-0-1 0-0-1-0
0-0 0-0-0 0-0-1
0-1-0 0-1-0-0 0-1-0-1 0-1-0-2
0-1-1 0-1-1-0 0-1-1-1
0-1-2-1 0-1-2-1-0 0-1-2-1-1 0-1-2-1-2
0-1-2 0-1-2-0 0-1-2-1 0-1-2-2
0-1 0-1-0 0-1-1 0-1-2
0 0-0 0-1

Symbol Tables

During symbol table generation and the search for semantic warnings and errors, if ZOBOS encounters the emit symtable statement all the symbols for all scopes should be written to the third command line argument. The format for this output is as follows:

1. The global or deepest scope will be considered scope zero (0), each nested scope within it is assigned the next sequential scope value.

2. Each symbol should be written on one line, and contain the following comma delimited fields: scope value, type, and id.

   1. The scope value is a non-negative integer, 0 is used for the deepest or "global" scope.

   2. type is the sequence of grammar terminals associated with a variable's DECLTYPE or it is the function signature:

      returnType//(param1type(/param2type(/param3type(/...))))

      eg, the function signature for speak in the helloworld.src example above is simply int//.

   3. The id is the identifier of the symbol.

   1. Yes, it is possible to have scopes without any symbols declared within them.
   2. Within the same scope, if an identifier is attempted to be re-used,

      1. If required by the semester write-up a REIDENT error should be generated

      2. Regardless of error generation, the attempted re-declaration is ignored.

All of the .src files with emit symtable instructions in the zobos resource archives have .sym files provided as well. Here is an example of program source with multiple scoping levels and the emit symtable output.

string  m = "helloworld";
const float  pi = 3.1415;
int     i = 0;
const bool    b = 1<3;
int main()
returns r=0
{
    string p = m;
    int    f = i;
    string i = "eyespymeashadow";
    {
        {
            bool c = b;
            emit p, 0, int(b);
            if ( f > 9.81 ) {
                c = bool(f*f-int(c));
                emit symtable;
            }
            emit i, 0, 15;
        }
        emit m, int(pi), 5;
    }
}

0,const bool,b
0,int,i
0,const string,m
0,const int//,main
0,const float,pi
1,int,r
2,int,f
2,const string,i
2,const string,p
4,bool,c

Hints and Testing

1. You know you're going to dump symbol table debug info during development, so you might as well format it according to the requirements in the first place.

grader.sh

I am providing to students the same tarball the grader will use for testing your ZOBOS. Here is how to use it:

First, download this tarball to your Mines Linux account ("alamode" machines!) and unroll it in a temporary directory.

$ ls zobos-student.*
zobos-student.tar.bz2
$ mkdir ~/tmp
$ cd ~/tmp
$ tar xjf ../zobos-student.tar.bz2
:
$ ls
zobos/

Second, set the COMPGRADING environmental variable with:

$ source ~khellman/COMPGRADING/setup.sh ~khellman/COMPGRADING

Now go to the directory holding your ZOBOS and execute the grader.sh script from the zobos-student.tar.bz2 resource.

$ cd ~/compilers/zobosCC
$ ls ZOBOS
ZOBOS
$ ~/tmp/zobos/grader.sh
:
:
:

You will need to read any messages from the script carefully, and perhaps hit ENTER several times throughout its course. This script checks for:

1. missing data files
2. truncated data files
3. inaccessible data files

4. and the difference between your ZOBOS results and expected results.

The latter test results are displayed on the terminal screen, but they whip by pretty quickly so you may need to scroll up and make sure you see them all.

When there is a discrepancy in expected results the script either:

• points you to a data file along side your ZOBOS where more failure details are available,

• or all the details are displayed on screen.

Before the grader.sh terminates, it will show a summary of some specific rubric line results for the programming project.

Submit Your Work

Rubric

This work is worth 120 points.