A Structural Analyzer for C--


To solve the structural analysis problem for C--:

Due dates

You must complete the PEP tasks (individually), and then hand in the requested material (as a group) at the beginning of class on Monday, September 21. This assignment is worth 40 points.


C-- is defined in Appendix A of Waite. Experience has shown that the source program tree described in Section A.3 can be improved upon:

RULE AndOp: Binop ::= '&&' END;
RULE AssignExp: Expression::= AppliedOccurrence '=' Expression END;
RULE Block: Range::= '{' Body'}' END;
RULE BreakStmt: Statement::= 'break' ';' END;
RULE Cminus: Source::= TypeSpecifier Identifier' (' Parameters ')' Range END;
RULE Computation: Statement::= Expression ';' END;
RULE CondExp: Expression ::= Expression '?' Expression':' Expression END;
RULE ContinueStmt: Statement::= 'continue' ';' END;
RULE DyadicExp: Expression::= Expression Binop Expression END;
RULE EmptyStmt: Statement::= ';' END;
RULE EqualOp: Binop ::= '==' END;
RULE FloatTypeSpecifier: TypeSpecifier ::= 'float' END;
RULE FloatVal: Expression::= FloatDenotation END;
RULE GreaterOp: Binop ::= '>' END;
RULE IdnExp: Expression ::= AppliedOccurrence END;
RULE IdnDef: DefiningOccurrence ::= Identifier END;
RULE IdnUse: AppliedOccurrence ::= Identifier END;
RULE Init: VariableDecl ::= DefiningOccurrence '=' Expression END;
RULE IntTypeSpecifier: TypeSpecifier ::= 'int' END;
RULE IntVal: Expression::= IntDenotation END;
RULE LessOp: Binop ::= '<' END;
RULE Loop: Iteration::= 'while' '(' Expression ')' Body END;
RULE MinusOp: Binop ::= '-' END;
RULE MonadicExp: Expression::= Unop Expression END;
RULE NegOp: Unop ::= '-' END;
RULE NotOp: Unop ::= '!' END;
RULE OneSided: Statement ::= 'if' '(' Expression ')' Body END;
RULE OrOp: Binop ::= '||' END;
RULE Parameter: ParameterDecl ::= TypeSpecifier DefiningOccurrence END;
RULE PercentOp: Binop ::= '%' END; 
RULE PlusOp: Binop ::= '+' END;
RULE ReturnStmt: Statement::= 'return' Expression';' END;
RULE SlashOp: Binop ::= '|' END;
RULE StarOp: Binop ::= '*' END;
RULE TwoSided: Statement ::= 'if' '(' Expression ')' Body 'else' Body END;
RULE Uninit: VariableDecl ::= DefiningOccurrence END;
RULE Variable: Declaration::= TypeSpecifier Variables';' END; 

RULE: Body LISTOF Declaration | Statement | Iteration | Range END;
RULE: Parameters LISTOF ParameterDecl END;
RULE: Variables LISTOF VariableDecl END;

This tree is to be used for all exercises in this course.

Click here for a zip file containing a small C-- compiler test suite. This suite contains programs that conform to the definition of the language and programs that exhibit various kinds of errors. There is a ``try'' script at the top level of the test suite. It can be used to execute all of the conformance tests or all of the deviance tests, and verify that error reports have or have not been made. This provides a simple way to exercise the processor to make certain that its behavior is close to being correct.

Suppose that you have generated an executable processor called cmm. The following command will run that processor over all of the conformance tests:

% try cmm tests/conformance

If one of the runs generates an error report, that error report will appear in the file' 'ERRS" in the current directory, and the test program will appear in the file "input" in the current directory.

The following command will run cmm over all of the deviance tests:

% try -d cmm tests/deviance

If one of the runs does not generate an error report, that test program will appear in the file input in the current directory.


Implement a structural analyzer for C--, using any tools and techniques you wish. Your program must read input text, construct the corresponding source program tree, and print a representation of the tree if the text is lexically and syntactically correct. If the input text is incorrect according to the lexical or syntactic rules of C--, your program must report at least the first error. It may terminate immediately after reporting the first error, or it may continue in an attempt to detect further errors.

Test you structural analyzer by applying it to the C-- test suite. If you feel that the test suite is inadequate, provide any additional test you deem necessary. Note that since you are testing only a structural analyzer, deviance tests that do not contain lexical or syntactic errors will not generate error reports.

Hand in the printed representation of the source program tree for the factorial program. A directory containing the complete source code (or specifications, if you used tools) for your structural analyzer must be permitted for world read by 1700 on the due date for this assignment. You need not make it available to be read by others before that time. Hand in the location of this directory (machine and path name).

Complete your personal postmortem for this assignment and your personal project plan for the next assignment, and submit them via the web before class on the due date of this assignment.

Revision 2.7 (1998/09/20 20:37:45)