In this assignment will you will implement a syntax checking LR(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 zlang.cfg using the LR knitting needles algorithm (pseudo code here, using this SLR table (the format is described here). 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.

   • It turns out that for zlang.cfg, an empty file is a valid program, but ZOBOS won't be tested with empty source files. So you don't need to contemplate "is ∅ a SYNTAX error?"

2. Either during the parse (using syntax directed translation procedures during production rule reduction), 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

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

   2. control structures IF, IFELSE, WHILE, STMTS, 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 are provided 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 and expression use of the parsed program source.

   1. 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.

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

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

   WARNING messages are not ERROR messages.

Syntax and Semantic Checks

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

Conversion Errors (CONV)

Attempting to perform these types of data storage causes a CONV ERROR.

Expression Value Propagation Rules and Errors (EXPR)

The type of value result in expression trees is always one of bool, float, int or string. An expression tree value type begins in the leaves and is implicit based on the type of literal value (intval, stringval, floatval) or variable is in the leaf.

• The value type may be altered in expression trees (as the calculation progresses up) by CAST operations or through int and float arithmetic combinations.

• UNARY operations do not change the value type.

• PLUS and TIMES operations between int and float values yield float results

OUTPUT

ZOBOS will report three 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 error in source (see Terminal Location column of syntax, error, and warning table)

3. the character number of error in 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: 7 1 :SYNTAX:
state /1/ input ('rbrace', '}') expected bool,const,emit,float,id,if,int,lbrace,string,while,$

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 B
C C
D D

A B C D

A A
B B
C C
D D

A B
A C D

string word = "hello world";
emit word 0 11;

0 PROGRAM
0-0 STATEMENT
0-0-0 DECLLIST
0-0-0-0 string
0-0-0-1 DECLID
0-0-0-1-0 =
0-0-0-1-0-0 word
0-0-0-1-0-1 hello world
0-1 STATEMENT
0-1-0 EMIT
0-1-0-0 word
0-1-0-1 0
0-1-0-2 11
0-2 $

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

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 the variable's DECLTYPE.

   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, when a variable identifier is attempted to be re-used, an REVAR error should be generated and the attempted variable redeclaration 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;
{
    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,string,m
0,const float,pi
1,int,f
1,string,i
1,string,p
3,bool,c

zlang.lr

zlang.cfg is not an SLR(1) language, nor is it LALR(1). This is due to the (55) UNARY->PLUS VALUE production rule, which causes two shift-reduce conflicts during LR table generation. Both conflicts can be resolved by preferring the shift action over the reduce. Because of this (and the size of the grammar), we'll use a static fixed-up LR table that has these conflicts resolved.

The zlang.lr LR parsing table has 107 lines with 58 comma separated fields per line (that makes 59 fields each line). There is no white space except for new line separators (x0A).

1. The first field of the first line is a period (.), which serves as a placeholder. The remaining fields on the first line are the column heading grammar symbols. There are 57 grammar symbols in the language (|$T+\Sigma_{\$}|$).

2. The remaining lines are for the 106 item set states. The first field is the item set index. Subsequent fields are the actions to be performed on the associated grammar symbol. The actions are written in the same notation used in the text and lectures slides with one exception:

   1. sh-X means "shift the symbol to the parsing stack and goto to state X.

   2. r-N means reduce by rule number N (not index!) and push the resulting subtree back to the input queue.

   3. R-N means by rule number N, which has the grammar's goal symbol on the LHS --- accept the token stream as valid!

      In the text and slides R-N is written out across the entire row of the LR table, as shown here in item set 10.

zlang-pure.cfg does not contain #comments and should be immediately readable by your learning group code for grammars. zlang-rules.lis is a text file with numbered grammar rules, zlang-lr.pdf is a typeset LR table formatted in the same manner as lectures slides. And for the very curious, here is the CFSM item set graph of the language.

Hints and Testing

1. You know you're going to dump symbol table debug info during development, so you might as 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 95 points.