CSE310-Syntax and Semantic Analysis Solved

1          Introduction
In the previous assignment, we have constructed a lexical analyzer to generate token streams. In this assignment, we will construct the last part of the front end of a compiler for a subset of the C language. That means we will perform syntax analysis and semantic analysis with a grammar rule containing function implementation in this assignment. To do so, we will build a parser with the help of Lex (Flex) and Yacc (Bison).

2          Language
Our chosen subset of the C language has the following characteristics:

There can be multiple functions. No two functions will have the same name. A function needsto be defined or declared before it is called. Also, a function and a global variable cannot have the same symbol.
There will be no pre-processing directives like #include or #define.
Variables can be declared at suitable places inside a function. Variables can also be declared inthe global scope.
All the operators used in the previous assignment are included. Precedence and associativityrules are as per standard. Although we will ignore consecutive logical operators or consecutive relational operators like, a && b && c, a < b < c.
No break statement and switch-case statement will be used.
3          Tasks
You have to complete the following tasks in this assignment.

3.1     Syntax Analysis

For the syntax analysis part you have to do the following tasks:

Incorporate the grammar given in the file “BisonAssignmentGrammar.PDF” along with thisdocument in your Yacc file.
1

Modify your Lex file from the previous assignment to use it with your Yacc file. Remove allthe symbol table insertions from the Lex file.
Use a SymbolInfo pointer to pass information from lexical analyzer to parser when needed. For example, if your lexical analyzer detects an identifier, it will return a token named ID and pass its symbol and type using a SymbolInfo pointer as the attribute of the token. On the other hand, in the case of semicolons, it will only return the token as the parser does not need any more information.
You can implement this in two ways: either redefine the type of yylval (YYSTYPE) in parser and associate yylval with new type in the scanner, or use %union field in the parser.

Handle any ambiguity in the given grammar (For example, if-else, you can find a solution in page 188-189 of flex-bison manual). Your Yacc file should compile with zero (0) conflicts.
Insert all the identifiers in the symbol table when they are declared in the input file. For exam-ple, if you find int a, b, c; then insert a, b, and c in the symbol table. You can do this in the grammar rule of declaration.
When a grammar matches the input from the C code, it should print the matching rule in thecorrect order in an output file (log.txt). For each grammar rule matched with some portion of the code, print the rule along with the relevant portion of the code.
Print symbol table when a scope exists (in the log.txt file). This means to print the symbol table just before the exitScope function of the symbol table is called.
Print well-formed syntax error messages with line number (in a log.txt file).
Print the symbol table after finishing parsing (in the log.txt file).
Bonus Task: Incorporate error recovery in your parser. Go through the Yacc manual for a better understanding of error recovery. You might need to use Yacc’s predefined token error (token number 256) for this purpose.

4          Semantic Analysis
In this part, you have to perform the following tasks:

Type Checking: You have to perform different types of type checking in this part. You have to perform the following semantic checks:
Generate error message if operands of an assignment operator are not consistent with eachother. Note that, the second operand of the assignment operator will be an expression that may contain numbers, variables, function calls, etc.
Generate an error message if the index of an array is not an integer.
Both the operands of the modulus operator should be integers.
During a function call all the arguments should be consistent with the function definition.
A void function cannot be called as a part of an expression.
Type Conversion: You have to perform some type-conversion. For example, you have to generate error/warning message if floating point number is assigned to an integer type variable. Also, the result of RELOP and LOGICOP operation should be an integer.
Uniqueness Checking: You should check whether a variable used in an expression is declared or not. Also, check whether there are multiple declarations of variables with the same ID in the same scope.
Array Index: You have to check whether there is an index used with array and vice versa.
Function Parameter: Check whether a function is called with appropriate number of parameters with appropriate types. Function definitions should also be consistent with declaration if there is any. Besides that, a function call cannot be made with non-function type identifier. To implement this task, you can add necessary fields in the SymbolInfo class as required but try to avoid redundant fields.
5          Handling Grammar Rules for Functions
For implementing the grammar rules of functions, you will need to add some fields in your SymbolInfo class as required.

You will need extra fields to store the return type, parameter list, number of parameters etc.in the SymbolInfo class, for proper handling of functions. You can take another class to hold the above-mentioned fields and add a reference of that class in the SymbolInfo class for convenience. Note that this is just a guideline, you are free to implement otherwise.
As a part of the semantic analysis you have to match the function declaration and functiondefinition and report an error if there is any mismatch in the return type, parameter number, parameter sequence or parameter type.
Bonus Task:      Report an error if there is any invalid scoping of the function.

6          Input
The input will be a C source program in .c extension. The filename will have to be given from the command line.

7          Output
In this assignment, there will be two output files. One file, log.txt, will contain matching grammar rules, corresponding segment of source code, and symbol table entries as instructed in the previous sections. Another file, error.txt will contain error messages with line numbers. For any detected error print something like “Line no 5: Corresponding error message”. Print the line count and number of errors at the end of the log file. For more clarification about input-output check the supplied sample I/O files.