Laboratory Assignments for Compiler Design for Spring 2020

Assignment 0

1. Write a C program that reads text from a file and prints on the terminal each input line, preceded by the line number. The output will look like -

   1     This is the first trial line in the file,
   2     and this is the second line.

   Try the problem once using fgetc() function and once using fgets() function for reading the input. Why is fread() not suitable for this purpose?
   
   Do not ignore the value returned by the functions fgetc() and fgets(). After this exercise the you should be comfortable with the formatted input and output functions of C.

2. Write a program that takes from the user the name of a file and a "field-number", and then reads that file and for each line in that file prints on the terminal word at position "field-number". For example if there are the following lines in the specified file -

   C is a programming language.
   lex produces a lexical analyser
   
         cc is a compiler

   and if the field-number specified is 4, then the output of the program is -

   programming
   lexical
   (NULL)
   compiler

   
   After this exercise you should be able to deal with individual words in a text file.

3. Write a C program that reads the names (as character strings of length upto 20 bytes) and corresponsing roll-numbers (as integers) of 10 students from the user and stores them in a file whose name is specified by the user-
   • in text format
   • in binary format
   
   After running the program check the size of the file created using ls -l command. Also see the content of the binary file using the command
   od -c filename.
   
   After this exercise you should be clear about the difference between a text file and a binary file.

4. Write a C program that works like the od program of LINUX (UNIX).

5. Write a C program that works like the strings program of LINUX (UNIX).

Assignment 1

Write a lexical analyser for the C programming language using the grammar for the language given in the book "The C Programming Language", 2e, by B Kernighan and D Ritchie.

(a) Write the lexical analyser in C without using a tool such as flex.
(b) 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 )
begin
      statement ;
            :
end

Write a context free grammar for the above construct, and create an operator precedence parsing table based on the grammar. Hint: Represent the grammar in appropriate data structures, then create the LEADING and TRAILING sets for the non-terminals of the grammar.

Assignment 4 Write a recursive descent parser for the construct mentioned in the previous question.

Assignment 5 Implement the routines to compute the FIRST and FOLLOW sets of the non-terminals of a given grammar. Also, write the routine to create an LL(1) parsing table for the grammar.

Hint: Take a suitable grammar and represent it in appropriate data structures.

Assignment 6

Implement an LL(1) parser that uses the LL(1) parsing table you have defined in the previous exercise.

Assignment 7

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 8

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 9 Implement a desk calculator using bison. Include addition, subtraction, multiplication and division operations in input arithmetic expressions.

A Simple example using bison

An useful page related to bison (local)

Assignment 10

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.

Additional Exercise

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 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.