Laboratory

  Lectures   : 	Mon - 4, Tue - 1,2, Thu -3 
  Room #     :  CSE 107
  Units      :	4-0-2
  Credits    :  4 (Theory) 
  Instructor :	Niloy Ganguly
  Contact    : 	Room #313  (CSE), Phone 3460

Text Books:

[1]  Aho, A. V., Sethi, R. and Ullman, J. D.
     Compilers - Principles, Techniques and Tools
     Addison-Wesley, 1988 (Indian reprint)
     - aka Dragon book

[2] Santanu Chattopadhyay
    Compiler Design
    PHI, 2005.

1. Write the regular expression for variable names. Assume that the variable name can start with alphabets or underscore and can also have digits but _____ is not a variable. (First 2 correct submissions accepted)

2. Write the regular expression to represent an ip address. (First 5 correct submissions accepted)

3. Given |r| the length of the regular expression, and |x| is the length of the input string write down the time and space complexity to test whether the string belongs to the regular expression or not by an (a) NFA and (b) DFA. (First 7 correct submissions accepted)

4. Show the two trees produced by the grammar S-> aSbS | bSaS | epsilon. (First 10 correct submissions accepted)

5. Given the grammar
E -> T E'
E' -> + T E' | epsilon
T -> F T'
T' -> * F T' | epsilon
F -> (exp) | id
Construct for Recursive Predictive Parsing, minimum state transition diagram for the rules
T -> F T'
T' -> * F T' | epsilon
(First 10 correct submissions accepted)

6. Write down the CFG to detect the following. (a). occurence of balanced parentheses (b). strings over alphabet {a,b} such that every 'a' is followed by a 'b'. (First 10 correct submissions accepted)

7. Given the grammar S -> iEtSS' | a
S'-> eS
E -> b.
Prepare the first and follow list and the LL(1) parsing table. (First 20 correct submissions accepted)

8. Given the grammar
S -> A
A -> T | A + T | A - T
T -> F | T * F | T / F
F -> P | P ^ F
P -> id | (A)
Prepare the operator precedence table. (First 23 correct submissions accepted)

1. Consider the grammar
S -> A S | b
A -> S A | a
a. Show that the grammar is ambiguous
b. Construct the corresponding SLR parsing table
c. Construct the corresponding LR(1) parsing table
d. Construct the corresponding LALR parsing table
Opening date - 28.09.2005, Closing Date - 6.10.2005
Persons to submit - 03CS1019, 03CS1025, 03CS3007

2. Consider the grammar
S -> AaAb
S -> BbBa
A -> epsilon
B -> epsilon
Show that the grammar is not SLR
Opening Date - 28.09.2005, Closing Date - 6.10.2005
Persons to submit - 03CS1006, 03CS1013, 03CS1027

General Guidelines

• 3 people per group.
• Web based submission has to be done. The procedure will be explained during lab hours.
• Each member of the group should specify what he/she has done.

You have to implement the following two algorithms

• Thompson Construction - Constructing NFA from regular expression
• Constructing DFA from NFA.

For constructing a lexical analyzer/scanner from a given set of regular expression. The input alphabet may be specified by the user. It should be possible to encode each symbol of the alphabet as a printable ascii character.

Marking Guidelines

* Evaluation of items (B) and (D) will be done in the lab. Please be present on 12/09/2005 to show your code.

* The overall working of the code will be evaluated based on test cases.

Construct a simple C-like language with

1. Data Type : integer (INT/int), floating point (FLOAT/float)

2. Condition constructs: if

3. Loop Constructs: for, while
4. Input / Output Constructs:
   1. read(x) - Read into variable x
   2. print(x) - Write variable x to output
5. Relational operators, assignment and arithmetic operators
6. Only function is main(), there is no other function.

Example

main()
{
        INT i=0;
        INT sum=0;
        INT count;
       
        read(count);
        for(i=0;i<10;i++)
        {
               
               read(x);
               sum+=x;

        }
        
        print(sum);
}

You have to implement a Lexical Analyzer/Scanner for the simple C-like programming language using 'lex' tools.

Take a file as input (You can test it on the above example file).

Output the tokens along with:

• Value of the integer constant
• Value of the floating point constant
• An array of characters (for identifiers)

Use the variable yyval to accomplish this.

Marking Guidelines

* Evaluation will be done on test cases.

Assignment 3: LL(1) Parser

Given

1. The Simple-C language is a simplified and modified subset of C programming language.
   The language specifications are given in second assignment.
2. You can get the CFG for C-programming language at Appendix A13 in Kernighan, B. W. and Ritchie, D. M., The C Programming Language, PHI.
   

Reuse

• Use the Lexical Analyzer developed by you in assignment 2. (Feel free to modify).

TO BE DONE - with paper and pencil

• Write a CFG for the Simple-C language specifications.
• Transform your CFG (without changing the language) suitably for a table-driven predictive parser (LL(1)).
• Compute FIRST, FOLLOW and Predict Sets and create the Parsing table (manually).

TO BE DONE - programming assignment

• Write a non-recursive table-driven LL(1) parser.

Input for this assignment

The input will be Simple-C programs, which may be wrong or correct syntactically and semantically. You will have to output both syntax and semantic errors in the Input.

Example Input Programs

Example 1: Correct Simple-C Program

int main()
{

      int fn1 = 1;
      int fn2 = 1 ;
      int i=0;
      int n;
      int fn=0;
     
      read(n);
      if(n < 1)
            print(0);
      else
      {
            while(i < n)
            {
                  fn = fn1 + fn2;
                  print(fn);
                  fn2 = fn1;
                  fn1 = fn;
                  i++;
            }

      }     

}

The above program should be accepted by the parser.

Example 2: Wrong Simple-C Program

int main()
{

      int r;
      int p                   /* Syntactic error here, missing semicolon */
      int int j;              /* Parse error here, keyword int occurs two times */
      int total=0;
      int i;
      
      read(r);
      read(p);
      scanf (j;            /* unrecognized token here: scanf and mismatched parentheses*/
      for(i = r; i < p; i+= j)
            total = total + j;
      print(total);
}

Output Expected

If input is wrong, i.e the parser was not able to parse the input or lexer was not able to recognize a token, then the output along with diagnosed reasons should be presented to the user.

Sample Output

FAIL
Line number: 7 Parse Error
Or
FAIL
Line number: 6 Token 716aklas Unexpected Token
If input is correct then OUTPUT should be simply PASS.

Files To Be Submitted

• Individual submissibles, to be submitted by everyone, individually:
  1. Description of own contribution
• Group submissibles, to be submitted by any group member:
  1. Lex file *.l
  2. Your parser implementation *.c
  3. Header file *.h
  4. Sample input file in.txt
  5. README.txt
  6. Makefile

You have to implement a Lexical Analyzer/Scanner for the simple C-like programming language using 'lex' tools.

Take a file as input (You can test it on the above example file).

Output the tokens along with:

• Value of the integer constant
• Value of the floating point constant
• An array of characters (for identifiers)

Use the variable yyval to accomplish this.

Marking Guidelines

Given

1. The Simple-C language is a simplified and modified subset of C programming language. The language specifications are given in second assignment.
2. You can get the CFG for C-programming language at Appendix A13 in Kernighan, B. W. and Ritchie, D. M., The C Programming Language, PHI.

TO BE DONE - programming assignment

• Implement a lexical analyser for Simple-C programming language using the lexical analyzer developed for the Thompson Construction assignment.
• Integrate it with LL(1) parser developed in the LL(1) Parser assignment, without modifying the parser program. You may have to work on the interface of the lexical analyzer developed in the Thompson Construction assignment to make that lex-compatible.
• Your Parser should already be working with lexical analyser developed in the Lexical Analyzer assignment.

Input for this assignment

The input will be Simple-C programs, which may be wrong or correct syntactically and semantically. You will have to output both syntax and semantic errors in the Input.

Example Input Programs

Example 1: Correct Simple-C Program

int main()
{

      int fn1 = 1;
      int fn2 = 1 ;
      int i=0;
      int n;
      int fn=0;
     
      read(n);
      if(n < 1)
            print(0);
      else
      {
            while(i < n)
            {
                  fn = fn1 + fn2;
                  print(fn);
                  fn2 = fn1;
                  fn1 = fn;
                  i++;
            }

      }     

}

The above program should be accepted by the parser.

Example 2: Wrong Simple-C Program

int main()
{

      int r;
      int p          /* Syntactic error here, missing semicolon */
      int int j;     /* Parse error here, keyword int occurs two times */
      int total=0;
      int i;
      
      read(r);
      read(p);
      scanf (j;      /* unrecognized token here: scanf and mismatched parentheses*/
      for(i = r; i < p; i+= j)
            total = total + j;
      print(total);
}

Output Expected

If input is wrong, i.e the parser was not able to parse the input or lexer was not able to recognize a token, then the output along with diagnosed reasons should be presented to the user.

Sample Output

FAIL
Line number: 7 Parse Error
Or
FAIL
Line number: 6 Token 716aklas Unexpected Token
If input is correct then OUTPUT should be simply PASS.

Files To Be Submitted

• Individual submissibles, to be submitted by everyone, individually:
  1. Description of own contribution
• Group submissibles, to be submitted by any group member:
  1. Your lex implementation *.c
  2. Your parser implementation *.c
  3. Header file *.h
  4. Sample input file in.txt
  5. README.txt
  6. Makefile

Take a file as input (You can test it on the above example file).

Output the tokens along with:

• Value of the integer constant
• Value of the floating point constant
• An array of characters (for identifiers)

Use the variable yyval to accomplish this.

Marking Guidelines

Given

1. The Simple-C language is a simplified and modified subset of C programming language. The language specifications are given in the lexical analyser assignment.
2. You can get the CFG for C-programming language at Appendix A-13 in Kernighan, B. W. and Ritchie, D. M., The C Programming Language, PHI.

TO BE DONE - programming assignment

• Develop a LR(1) parser generator for a given grammar
• Use the generator to generate a LR(1) parser for the Simple-C programming language
• Interface parser with an earlier lexical analyser to get a fully working parser lexical analyzer pair

Input for this assignment

The input will be Simple-C programs, which may be wrong or correct syntactically and semantically. You will have to output both syntax and semantic errors in the Input.

Example Input Programs

Example 1: Correct Simple-C Program

int main()
{

      int fn1 = 1;
      int fn2 = 1 ;
      int i=0;
      int n;
      int fn=0;
     
      read(n);
      if(n < 1)
            print(0);
      else
      {
            while(i < n)
            {
                  fn = fn1 + fn2;
                  print(fn);
                  fn2 = fn1;
                  fn1 = fn;
                  i++;
            }

      }     

}

The above program should be accepted by the parser.

Example 2: Wrong Simple-C Program

int main()
{

      int r;
      int p          /* Syntactic error here, missing semicolon */
      int int j;     /* Parse error here, keyword int occurs two times */
      int total=0;
      int i;
      
      read(r);
      read(p);
      scanf (j;      /* unrecognized token here: scanf and mismatched parentheses*/
      for(i = r; i < p; i+= j)
            total = total + j;
      print(total);
}

Output Expected

If input is wrong, i.e the parser was not able to parse the input or lexer was not able to recognize a token, then the output along with diagnosed reasons should be presented to the user.

Sample Output

FAIL
Line number: 7 Parse Error
Or
FAIL
Line number: 6 Token 716aklas Unexpected Token
If input is correct then OUTPUT should be simply PASS.

Files To Be Submitted

• Individual submissibles, to be submitted by everyone, individually:
  1. Description of own contribution
• Group submissibles, to be submitted by any group member:
  1. README.txt
  2. Your lex program *.c (essential)
  3. Your lex header *.h (optional)
  4. Your parser generator program *.c (essential)
  5. Your parser generator header *.h (optional)
  6. Grammar file gram.txt
  7. Sample input file in.txt
  8. Makefile

Marking Guidelines

Given

1. The Simple-C language is a simplified and modified subset of C programming language. The language specifications are given in the lexical analyser assignment.
2. You can get the CFG for C-programming language at Appendix A-13 in Kernighan, B. W. and Ritchie, D. M., The C Programming Language, PHI.

TO BE DONE - programming assignment

• Use the YACC parser generator to generate a LALR(1) parser for the Simple-C programming language
• Interface parser with an the LEX based lexical analyser to get a fully working parser lexical analyzer pair

Input for this assignment

The input will be Simple-C programs, which may be wrong or correct syntactically and semantically. You will have to output both syntax and semantic errors in the Input.

Example Input Programs

Example 1: Correct Simple-C Program

int main()
{

      int fn1 = 1;
      int fn2 = 1 ;
      int i=0;
      int n;
      int fn=0;
     
      read(n);
      if(n < 1)
            print(0);
      else
      {
            while(i < n)
            {
                  fn = fn1 + fn2;
                  print(fn);
                  fn2 = fn1;
                  fn1 = fn;
                  i++;
            }

      }     

}

The above program should be accepted by the parser.

Example 2: Wrong Simple-C Program

int main()
{

      int r;
      int p          /* Syntactic error here, missing semicolon */
      int int j;     /* Parse error here, keyword int occurs two times */
      int total=0;
      int i;
      
      read(r);
      read(p);
      scanf (j;      /* unrecognized token here: scanf and mismatched parentheses*/
      for(i = r; i < p; i+= j)
            total = total + j;
      print(total);
}

Output Expected

Each grammar rule reduction should be printed as it occurs.

Example

Files To Be Submitted

• Individual submissibles, to be submitted by everyone, individually:
  1. Description of own contribution
• Group submissibles, to be submitted by any group member:
  1. Your LEX file *.l
  2. Your YACC file *.y
  3. Sample input file in.txt
  4. Makefile
  5. README.txt

Marking Guidelines

You are to use the YACC based LALR(1) parser for the Simple-C programming language to generate 3-address code. Use the lex generated lexical analyzers to work with the parser that you generate. Your makefile should include a target for generating an executable from the 3-address code that you generate using a standard assembler. It should also include necessary commands to compile the programs generated by lex and yacc.

The 3-address code file should be generated as a result of make all.

The other specifications are same as for the assignment on LALR(1) Parser Generator for Simple-C

To understand how parameter passing for subroutine calls should be handled, generate the assembly for simple `C' programs using gcc -S and analyze the resulting assembly code. You should use printf() to output values computed in your program.

Files To Be Submitted

• Individual submissibles, to be submitted by everyone, individually:
  1. Description of own contribution
• Group submissibles, to be submitted by any group member:
  1. Your LEX file *.l
  2. Your YACC file *.y
  3. Sample input file in.txt
  4. Makefile
  5. README.txt

Marking Guidelines