Asignment 0
Write a lexical analyser for the C programming language using the gramar for the language given in the book "The C Programming Language", 2e, by B Kernighan and D Ritchie.
Use flex for creating the lexical analyser.
Implement a desk calculator using operator precedence parsing.
Imagine the syntax of a programming language construct such as while-loop --
while ( condition )where while, begin, end are keywords; condition can be a single comparision expression (such as x == 20, etc.); and statement is the assignment to a location the result of a single arithmatic operation (eg., a = 10 * b).
begin
statement ;
:
end
Write a program that verifies whether the input follows the above syntax. Use flex to create the lexical analyser module and write a C program that performs the required task using that lexical analyser.
Assignment 3
Write a C program for implementing shift-reduce parsing using a given
grammar.
Firstly, define the data structures for representing the given CFG in BNF,
the stack for the parsing, and the parse tree to be created.
Assignment 4
Write a C program for creating the precedence table for a given
grammar. The table should be created in an appropriate data structure that is
compatible with the requirements of Assignment 2.
Hint: Use a distinct number to represent each grammar symbol - terminal and
non-terminal.
Assignment 5
Write a LR parser program in C. Define the data structure for the parsing table in such a way that it can be initialised easily (manually) for a given grammar. Take a simple grammar, eg., expression grammar, compute the parsing table entries by hand using the steps discussed in the class, and initialize the table in your program with these values. Try to parse input expressions scanned by a lexical analyser (which can be easily created using flex). The output of the parser should be SUCCESS or FAILURE depending on the input. In case of FAILURE the parser should indicate the incorrect token in the input.
Assignment 6
Modify your LR parser program of the preceding assignment such that along with the reduce actions, the parser invokes routines associated with the particular grammar rule. For example, for a reduction by the rule E -> E + T of the exression grammar, the parser computes the sum of the numbers corresponding to the symbols E and T on the RHS, and associates the sum to the symbol E on the LHS.
Hint: Observe that it will be necessary to associate values with different symbols in the stack. Whenever a reduce action is taken some symbols of the stack are to be replaced by a non-terminal symbol. In this step the value to be associated with the non-terminal is to be computed using the values associated with the symbols that are being replaced.
Assignment 7
Take the C grammar from the book - The C Programming Language (by Kernighan and Ritchie), and try to generate a parser for the language using YACC. The notation for the grammar in the book is not strictly BNF (e.g. use of subscript "opt" with some symbols, use of "one of", etc.), so some rewriting shall have to be done due to that. Apart from that there are are some LALR conflicts which you shall have to resolve by any appropriate means.
Note: This exercise may require more time than available. So start the work, realise the issues and learn the tricks, so that completion of the remaining part should depend not on learning time, but only on adequate coding time.
An useful page related to bison (local)
Assignment 8
Take a common programming language construct of an HLL, such as the for-loop construct of the C language. Use LEX and YACC to create a translator that would translate input into three-address intermediate code. The output of the translator should finally be in a file. Assume a simple structure for "statements" that may appear inside the construct, and make necessary assumptions for the intermediate code format.