Description
1. The problem In the last assignment you built a scanner for C- in flex and a “driver” in bison that printed out information about the tokens produced by the scanner. For this assignment you are to modify the “driver” of the last assignment in order to produce a parser for C-. Your parser will construct the abstract syntax tree (AST) corresponding to the input C- program. Building your parser should consist of the following steps: 1. Build a C- recognizer 2. Extend your C- recognizer to add the AST 3. Add user interface options Your completed parser must produce the same AST as is specified in the provided examples. If your parser does not produce the same AST then your parser is flawed. 1.1 Building the Recognizer A recognizer for a particular programming language (PL) simply determines whether or not a given program is a member of the PL that is generated by the grammar for the PL. Use the C- grammar provided on the course website to build a grammar that is suitable for consumption by bison. You will need to fix the dangling-else ambiguity and any other ambiguities or associativity/precedence errors that are currently in the C- grammar. You may not use any bison directives such as %assoc, %left, %right, or %expect in fixing these errors. After you have learned to fix errors “by hand” you can venture into the realm of trying to figure out what the tools are doing to you when they are supposed to be fixing errors for you. But, for now, you are to fix any errors by hand. Once you have built a bison-ready C- grammar that contains no shift/reduce or reduce/reduce conflicts, you have successfully built a recognizer that needs to be tested. Test your recognizer by passing legal C- files into it and observing your recognizer. If your recognizer doesn’t emit a message indicating that there was an error (e.g. an unrecognized character or missing paren,) your recognizer recognized that the C- program is legal. If your recognizer emits an error message or behaves in an abnormal way (e.g. SIGSEGV) your grammar is incorrect and needs to be repaired. Once you have successfully tested your recognizer on all provided C- samples and are confident that it will recognize any legal C- program, it is time to extend the recognizer to build a parser. 1.2.1 Adding the AST Typically compilers build a modified form of syntax tree known as an abstract syntax tree (AST) instead of building a full parse tree for a given program. An AST is like a distilled form of parse tree that only contains the information that we need to continue the compilation process. Your parser is to construct an AST for any legal C- program. An AST is of course just a tree, and the tree will contain nodes representing information that was gathered about the input C- program. The following is a sample AST node structure that has been previously used in this course: typedef struct treeNode { // connectivity in the tree struct treeNode *child[MAXCHILDREN]; // children of the node struct treeNode *sibling; // siblings for the node // what kind of node int lineno; // linenum relevant to this node NodeKind nodekind; // type of this node union // subtype of type { DeclKind decl; // used when DeclK StmtKind stmt; // used when StmtK ExpKind exp; // used when ExpK } subkind; // extra properties about the node depending on type of the node union // relevant data to type -> attr { OpKind op; // type of token (same as in bison) int value; // used when an integer constant or boolean unsigned char cvalue // used when a character char *string; // used when a string constant char *name; // used when IdK } attr; ExpType expType; // used when ExpK for type checking bool isArray; // is this an array bool isStatic; // is staticly allocated? // even more semantic stuff will go here in later assignments. } TreeNode; This structure was pulled from the Louden textbook and is just a suggestion. You can use whatever you want, as long as you can reliably represent the necessary information in memory and can produce the same results as in the provided examples. The following type definitions are used by the TreeNode structure above, and were also pulled from the Louden textbook: // Kinds of Operators // these are the token numbers for the operators same as in flex typedef int OpKind; // Kinds of Statements //typedef enum {DeclK, StmtK, ExpK} NodeKind; enum NodeKind {DeclK, StmtK, ExpK}; // Subkinds of Declarations enum DeclKind {VarK, FuncK, ParamK}; // Subkinds of Statements enum StmtKind {NullK, IfK, WhileK, ForK, CompoundK, ReturnK, BreakK, RangeK}; // Subkinds of Expressions enum ExpKind {OpK, ConstantK, IdK, AssignK, InitK, CallK}; // ExpType is used for type checking (Void means no type or value, UndefinedType means undefined) enum ExpType {Void, Integer, Boolean, Char, CharInt, Equal, UndefinedType}; // What kind of scoping is used? (decided during typing) enum VarKind {None, Local, Global, Parameter, LocalStatic}; Because this design was borrowed from the Louden textbook, you are free to use the example from the Tiny language compiler in the book (a link for the code for this is on the course website) as a reference to study and build from. You are free to use a C++ class rather than a struct to represent a TreeNode. You can use any structure that you like as long as your C- parser produces the same output as in the provided examples. Building a correct AST is of critical importance because all future assignments will require successful construction and traversal of the AST corresponding to a given C- program. Any bugs that you produce in the construction and traversal of your AST are going to follow you for the remainder of the semester, so be Very Careful. To encode a C- program as an AST, you will need to construct the right nodes at the right times during the parsing process. When you need to construct a node, you should use functions that you build like the newStmtNode function in the util.c file for the Tiny language compiler in the book (a link for the code for this is on the course website). These nodes will be passed up the tree as pointers and assembled to build the AST like in the example for the Tiny language in the Louden textbook. The following is an example to use for specifying the set of types that can represent a yylval in your bison file (this was discussed in class). %union { ExpType type; // For passing types (i.e pass a type in a decl like int or bool) TokenData *tokenData; // For terminals. Token data comes from yylex() in the $ vars TreeNode * tree; // For nonterminals. Add these nodes as you build the tree. } This is just a suggestion of what could be in your %union. Note, however, that you are expressly forbidden from accessing YYSTYPE as is done in the Louden book. Using YYSTYPE directly subverts type checking facilities and is too risky for you in this course. You should, as mentioned earlier, build functions to construct different types of TreeNode that you want to put in your AST. The following are prototypes that can be used for these functions. If you examine the Tiny compiler code you will see that this is how TreeNode children are added to a given TreeNode in almost all cases (the initialization of a var is one exception). The use of default values for arguments in these prototypes simplifies the construction of a given TreeNode and also simplifies the corresponding code for the action in your bison file. TreeNode *newDeclNode(DeclKind kind, ExpType type, TokenData* token=NULL, TreeNode* c0=NULL, TreeNode* c1=NULL, TreeNode* c2=NULL); TreeNode *newStmtNode(StmtKind kind, TokenData* token, TreeNode* c0=NULL, TreeNode* c1=NULL, TreeNode* c2=NULL); TreeNode *newExpNode(ExpKind kind, TokenData* token, TreeNode* c0=NULL, TreeNode* c1=NULL, TreeNode* c2=NULL); Note: Once you have your parser working correctly, make sure that you modify your parser to rename the unary – (minus) operator to the CHSIGN token and rename the unary * (asterisk) operator to the SIZEOF token. There is no need to leave these operators untokenized after we can differentiate between their use in a unary or binary context. 1.2.2 Printing the AST Once you have successfully constructed an AST for a given program, you will need to print the AST in order to verify that your AST is correct. How do you know that your AST is correct? The structure of a correct AST for a given program is dictated by your bison grammar. You can also compare your printed AST with examples that are provided in the test dataset for this assignment. To print your AST, you should make a function in your code called printTree. Your printTree function must print out the AST precisely as it is printed in the provided examples. Almost the same format is not good enough. The printTree function will be called after the AST has been constructed by your bison-generated parser. Your main() function in your bison file will look something like this: int main(int argc, char* argv[]) { // some stuff here… // Call yyparse to build the AST and put its address in // the “global” var named syntaxTree of type TreeNode* yyparse(); if (printTreeFlag) // Print the contents of the AST to stdout printTree(stdout, syntaxTree); // other stuff here… } The printTreeFlag variable in the example above is one of the user interface options that you are going to add for this assignment, and is discussed later in this document. The printTree function prints the important information within a given node, and then recursively applies the printTree function to all of the non-NULL children of the node (starting with child[0]), and then recursively applies the printTree function to the sibling pointer if it is not NULL. The first sibling found is numbered 1. Reading the AST provided for given examples is a good way to figure out what to do. For example, given the following C- program as input: ## C-S22 int main() begin int x; int y[5]; bool b; b <- true or false and 11 + 22 * 33 / 44 > 55; if 666>777 then begin x <- 111; end else y[3] <- x+222; while x>999 do begin x <- 333; if x<9 then break; x <- 444; break; end for z <- 1 to 8 do if z>x then x <- z; end Your c- (the program containing the C- scanner, parser, and print routines) will scan the input, produce an AST, and print the following output: Func: main returns type int [line: 2] . Child: 1 Compound [line: 3] . . Child: 0 Var: x of type int [line: 4] . . Sibling: 1 Var: y of array of type int [line: 5] . . Sibling: 2 Var: b of type bool [line: 6] . . Child: 1 Assign: <- [line: 8] . . . Child: 0 Id: b [line: 8] . . . Child: 1 Op: or [line: 8] . . . . Child: 0 Const true [line: 8] . . . . Child: 1 Op: and [line: 8] . . . . . Child: 0 Const false [line: 8] . . . . . Child: 1 Op: > [line: 8] . . . . . . Child: 0 Op: + [line: 8] . . . . . . . Child: 0 Const 11 [line: 8] . . . . . . . Child: 1 Op: / [line: 8] . . . . . . . . Child: 0 Op: * [line: 8] . . . . . . . . . Child: 0 Const 22 [line: 8] . . . . . . . . . Child: 1 Const 33 [line: 8] . . . . . . . . Child: 1 Const 44 [line: 8] . . . . . . Child: 1 Const 55 [line: 8] . . Sibling: 1 If [line: 10] . . . Child: 0 Op: > [line: 10] . . . . Child: 0 Const 666 [line: 10] . . . . Child: 1 Const 777 [line: 10] . . . Child: 1 Compound [line: 10] . . . . Child: 1 Assign: <- [line: 11] . . . . . Child: 0 Id: x [line: 11] . . . . . Child: 1 Const 111 [line: 11] . . . Child: 2 Assign: <- [line: 13] . . . . Child: 0 Op: [ [line: 13] . . . . . Child: 0 Id: y [line: 13] . . . . . Child: 1 Const 3 [line: 13] . . . . Child: 1 Op: + [line: 13] . . . . . Child: 0 Id: x [line: 13] . . . . . Child: 1 Const 222 [line: 13] . . Sibling: 2 While [line: 15] . . . Child: 0 Op: > [line: 15] . . . . Child: 0 Id: x [line: 15] . . . . Child: 1 Const 999 [line: 15] . . . Child: 1 Compound [line: 15] . . . . Child: 1 Assign: <- [line: 16] . . . . . Child: 0 Id: x [line: 16] . . . . . Child: 1 Const 333 [line: 16] . . . . Sibling: 1 If [line: 17] . . . . . Child: 0 Op: < [line: 17] . . . . . . Child: 0 Id: x [line: 17] . . . . . . Child: 1 Const 9 [line: 17] . . . . . Child: 1 Break [line: 17] . . . . Sibling: 2 Assign: <- [line: 18] . . . . . Child: 0 Id: x [line: 18] . . . . . Child: 1 Const 444 [line: 18] . . . . Sibling: 3 Break [line: 19] . . Sibling: 3 For [line: 22] . . . Child: 0 Var: z of type int [line: 22] . . . Child: 1 Range [line: 22] . . . . Child: 0 Const 1 [line: 22] . . . . Child: 1 Const 8 [line: 22] . . . Child: 2 If [line: 22] . . . . Child: 0 Op: > [line: 22] . . . . . Child: 0 Id: z [line: 22] . . . . . Child: 1 Id: x [line: 22] . . . . Child: 1 Assign: <- [line: 22] . . . . . Child: 0 Id: x [line: 22] . . . . . Child: 1 Id: z [line: 22] Note that this output, including the dots to indicate indenting levels, is what your program output is going to be compared against. Your c- must produce this exact same output for this particular input. When building your AST, if there is an optional expression or statement that is absent, be sure to set the corresponding child pointer to NULL. For example, compound statements can contain declarations, but sometimes they don’t. If a compound statement doesn’t contain declarations, then the child[0] pointer for that compound statement should be set to NULL. As another example, a return statement in C- may or may not contain an expression. If a given return statement doesn’t contain an expression, the child[0] pointer corresponding to the TreeNode for the return statement should be set to NULL. The default value for all pointers, including unnecessary children and siblings, should always be NULL. This means that your code must set these pointers to NULL and consistently check the value of a pointer before attempting to dereference the pointer. The bison code in the Tiny compiler example source code (on the course website) is a good example of how to connect the TreeNode nodes that you construct. The calculator example that we showed in class is a good example of how to organize the interaction between the scanner (flex) and the parser (bison). The following are two examples of functions that can be used to connect sibling pointers and to pass information down a list of siblings. These functions also demonstrate the use of some of the type variables in struct TreeNode. // Adds a TreeNode to a list of siblings. // Adding a NULL node to the sibling list is probably a programming error! TreeNode *addSibling(TreeNode *t, TreeNode *s) { if (s==NULL) { printf(“ERROR(SYSTEM): never add a NULL to a sibling list.\n”); exit(1); } if (t!=NULL) { TreeNode *tmp; tmp = t; while (tmp->sibling!=NULL) tmp = tmp->sibling; tmp->sibling = s; return t; } return s; } // Passes the isStatic and type attributes down the sibling list. void setType(TreeNode *t, ExpType type, bool isStatic) { while (t) { t->expType = type; t->isStatic = isStatic; t = t->sibling; } } 1.3 User Interface Options Once you have successfully built your parser, you are ready to make changes to the interface of your cprogram, which is now starting to look like a compiler. Your program must be named c- (note the lowercase) as was the case in the last assignment. Your c- must be able to read the stream of tokens contained within a file whose name is passed as an argument on the command line, or to read the stream of tokens from standard input (stdin) if no argument is passed on the command line. This is the same behavior that was present in the last assignment. 1.3.1 The -p Option Your c- will always construct an AST for a legal C- program. If the user specifies the -p option on the command line, your c- will print the AST that it built to stdout. For example, if the user types the following command: $bash> c- -p mergeSort.cYour c- will build the AST for the program in mergeSort.c- and will print the AST to stdout. Whereas if the user types the following command: $bash> c- mergeSort.c- Your c- will build the AST for the program in mergeSort.c- but will not print the AST to stdout. The -p option will set a variable named printTreeFlag (as shown earlier in this assignment) so that you can determine whether or not to print the AST after it has been built. The -p option is the first of many options that we will be adding to the compiler interface during the semester. There is a Unix function called getopt that is used to handle command line arguments that you are free to use. A custom version called ourgetopt is provided on the course website. This custom version is much more portable than standard getopt implementations, and is provided so that you can reap the benefits of getopt while building your compiler on platforms other than Unix. 1.3.2 The -d Option Your c- will also take the -d option on the command line. This option enables debugging of the parser by setting the yydebug flag in bison to 1. For example if the user enters the following command: $bash> c- -d mergeSort.cYour -c will build an AST for the program in mergeSort.c and information about what is happening during the parsing of the file will be printed to stdout. The information that is printed will automatically be printed by the parser generated by bison once you set yydebug to 1. If the user doesn’t specify the -d option, no information about what is happening during parsing will be printed. In order to access the yydebug flag that is inside the parser generated by bison, be sure to declare it as an external integer (extern int yyedebug) inside your code. 2. Deliverables and Submission Your homework will be submitted as an uncompressed .tar file that contains no subdirectories. Your .tar file must contain all files and code necessary to build and test your compiler. If you use ourgetopt, be sure to include the ourgetopt files in your .tar archive. The .tar file is submitted to the class submission page. You can submit as many times as you like. The last file you submit before the deadline will be the only one graded. No late submissions are accepted for this assignment. For all submissions you will receive email at your uidaho address showing how your file performed on the pre-grade tests. The grading program will use more extensive tests, so thoroughly test your program with inputs of your own. Your code must compile successfully and have no shift/reduce or reduce/reduce conflicts from bison. Your program must run with no runtime errors such as segmentation violations (SIGSEGVs).