Homework #3 (Parser- Code Generator)

COP 3402: System Software


Homework #3 (Parser- Code Generator)



This is a solo or team project (Same team as HW1 and HW2)

REQUIRMENT:
All assignments must compile and run on the Eustis3 server. Please see course website for details concerning use of Eustis3. 

Objective:
In this assignment, you must implement a Recursive Descent Parser for tiny PL/0. You will do this by implementing the file parser.c. 

Component Descriptions:
The Parser is a program that reads in the output of the Scanner (HW2) and parses the tokens. It must be capable of reading in the tokens produced by your Scanner (HW2) and produce, as output, if the program does not follow the grammar, a message indicating the type of error present and it must be printed (reminder: if the scanner detects an error the compilation process must stop and the error must be indicated, the compilation process must stop). A list of the errors that must be considered can be found in Appendix C. In addition, the Parser must fill out the Symbol Table, which contains all of the variables, procedure and constants names within the PL/0 program. See Appendix D for more information regarding the Symbol Table. If the program is syntactically correct and the Symbol Table is created without error, the execution of the compiler driver continues with intermediate code generation.

Submission Instructions:
1.- Submit via WebCourses:
1.    An implemented version of parser.c. We will use the provided files to compile your program, so do not alter them.
2.    Late policy is the same as HW1 and HW2.
3.    Only one submission per team: the name of all team members must be written in the header comment of parser.c, in a comment on the submission, and in the readme.
4.    Include comments in your program
5.    Output should print to the screen and should follow the format in Appendix A. A deduction of 5 points will be applied to submissions that do not print to the screen.
6.    The input file should be given as a command line argument. A deduction of 5 points will be applied to submissions that do not implement this.

Hints
•    Work out the first, follow, nullable, and predictive parsing table for the grammar first, then use it to implement a predictive parser as shown in the lecture slides.
•    In addition to a function for each non terminal of the grammar, we recommend a function for checking symbols for conflicting declarations before adding them to the symbol table, a function for marking symbols as inaccessible, a function for adding symbols to the symbol table, and a function for accepting tokens.

Error Handling
•    When your program encounters an error, it should print out an error message and stop executing immediately. You can do this by calling errorend()

We will be using a bash script to test your programs. This means your program should follow the output guidelines listed (see Appendix A for examples). You don’t need to be concerned about whitespace beyond newline characters. We use diff -w.

The function printtable() is included to print your symbol table. There are three necessary variables: symbol *table, sym_index, and error. If error is zero, no error was found.

Rubric
15 – Compiles
20 – Produces some instructions before segfaulting or looping infinitely
5 – Follows IO specifications (takes command line argument for input file name and prints output to console)
10 – Correctly parses symbol table
5 – Correctly implements expression, term, and factor
10 – Loads and store values correctly
15 – Supports error handling
10 – Correctly implements if statements
10 – Correctly implements while statements
 
Appendix A:

Traces of Execution:

Input:
    const a := 8;
var x, y;
procedure J;
        const x := 9;
        var x, y;
        begin
            x := y * 2;
        end;
begin
        call J;
end.
Output:
    Parser Error: Competing Symbol Declarations
Input:
var x, y;
begin
    x := 8 ( 3 + y);
end.
Output:
    Parser Error: Unrecognized Statement Form
Input:
var x;
begin
    x := 8;
    x := x * 4
.
Output:
    Parser Error: begin Must Be Followed By end
Input:
const z := 8, w:=3;
var x, y;
procedure J;
    var x, z;
    begin
        x := 7 * y; ; ; 
        z:=1;
        y := z*11;
    end;
begin
    y := z * w;
    call J
end.
Output:
    Symbol Table:
Kind | Name        | Value | Level | Address
--------------------------------------------
   3 |        main |     0 |     0 |     0
   1 |           z |     8 |     0 |     0
   1 |           w |     3 |     0 |     0
   2 |           x |     0 |     0 |     3
   2 |           y |     0 |     0 |     4
   3 |           J |     0 |     0 |     0
   2 |           x |     0 |     1 |     3
   2 |           z |     0 |     1 |     4
Appendix B:

EBNF of  tiny PL/0:

program ::= block "." . 
block ::= const-declaration  var-declaration  procedure-declaration statement.    
const-declaration ::= ["const" ident ":=" number {"," ident ":=" number} ";"].    
var-declaration  ::= [ "var "ident {"," ident} “;"].
procedure-declaration ::= { "procedure" ident ";" block ";" }.
statement   ::= [ ident ":=" expression
| "call" ident
              | "begin" statement { ";" statement } "end" 
              | "if" condition "then" statement ["else" statement]
        | "while" condition "do" statement
        | "read" ident
        | "write" expression
              | e ] .  
condition ::= "odd" expression 
          | expression  rel-op  expression.  
rel-op ::= "=="|“<>"|"<"|"<="|">"|">=“.
expression ::= [ "+"|"-"] term { ("+"|"-") term}.
term ::= factor {("*"|"/"|”%”) factor}. 
factor ::= ident | number | "(" expression ")“ .
 
Based on Wirth’s definition for EBNF we have the following rule:
[ ] means an optional item.
{ } means repeat 0 or more times.
Terminal symbols are enclosed in quote marks.
A period is used to indicate the end of the definition of a syntactic class.

 
Appendix C:

Error messages for the tiny PL/0 Parser:
1.    Competing Symbol Declarations
2.    Unrecognized Statement Form
3.    Programs Must Close with a Period
4.    Symbols Must Be Declared with an Identifier
5.    Constants Must Be Assigned a Value at Declaration
6.    Symbol Declarations Must Be Followed By a Semicolon
7.    Undeclared Symbol
8.    while Must Be Followed By do
9.    if Must Be Followed By then
10.    begin Must Be Followed By end
11.    while and if Statements Must Contain Conditions
12.    Conditions Must Contain a Relational-Operator
13.    ( Must Be Followed By )
14.    call and read Must Be Followed By an Identifier
These are all the error messages you should have in your parser.

Appendix D:

Symbol Table

Recommended data structure for the symbol.

typedef struct  
    { 
    int kind;         // const = 1, var = 2, procedures = 3
    char name[12];    // name up to 11 chars
    int val;         // number 
    int level;         // L level
    int addr;         // M address
    int mark;        // a one in this entry means deleted.
    } symbol; 

symbol_table[MAX_SYMBOL_TABLE_SIZE = 500];

For constants, you must store kind, name L, and value.
For variables, you must store kind, name, L and M.
For procedures, you must store kind, name, and L