Lab-Assignments (Groups and Marks)
        Assignment 1
        Tiny C
        Assignment 2

  Lectures   : 	Mon - 4, Tue - 1,2, Thu -3 
  Room #     :  CSE 119
  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.

General Guidelines

• 2 person per group.
• Online assessment will  be done.
• Code also need to be submitted. .
• Each member of the group should specify what he/she has done.
• Code Quality - Guidelines
• Checking code quality

You have to implement the following two algorithms

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

The input alphabet will be-

• a-z (small letters)
• +, ., *, (, ),epsilon (Note. + is used in lieu of '|')

• (a)
• ( (b) | (c) )
• ( (d)* )
• ( ( (a).( ( (c) | (d) )* ) ) | (f) )

Marking Guidelines

Output formats

• All the states would be numbered from 0 onwards and the start state be represented by 0
• The accepting states would be represented by the state number followed by (-) wherever they are mentioned. say 4- , 5- etc.
• The states for which there are no transitions for a given alphabet would be represented by (=) and for the states to which there are mulitple transitions for a given input, the states would be comma separated without spaces say 3,4

• All the states would be derived from the corresponding NFA via subset construction and should be given in the starting of the output (see example below).
• All the states would be capitalized Ascii acharacters A-Z and the start state be represented by A
• The accepting states would be represented by the state letter followed by (-) wherever they are mentioned. say D- , E- etc.
• The states for which there are no transitions for a given alphabet would be represented by (=)

* Evaluation of items (B) and (D) will be done in the lab. The output format for the NFA would be-

Please be present on 06/08/2007 to show your code.

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

Tiny-C Specification

1. Data types: int, char, float
2. Array Support: only single dimensional as in C
Ex: int a[10];
Multiple variable declarations should be supported. The format is as in C.
Ex: int a, b;
      int a[10],b[5];
3. Global variables
4. Composite statement is enclosed within braces { . . .}.
5. Assignment operator: = .
Ex: a = 10;
Continued assingment should also be supported
Ex: a = b = 10;
6. Binary Arithmetic operators. +, -, *
7. Unary Arithmetic operator. ++, ** (only postfix)
8. Boolean operators: ==, >, <
9. Binary Logical operator : &&, ||
10. Unary logical operator : !
11. Unary operator: -
12. Input / Output Constructs:
1. read(x) - Read into variable x
2. print(x) - Write variable x to output
13. Conditional statement:
if (condition) composite-statement [else composite-statement]
14. Loops:
a. For loop as in C
b. While loop as in C
15. Program entry point defined by keyword "main"
Programes written in Tiny-C can use identifiers consisting of any alpha-numeric characters, starting with only _ or [a..z] or [A..Z]
 

Example

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

        }
        
        print(sum);
}

Assignment 2: Understanding and working with Lex

(2) You have to implement a Lexical Analyzer for Tiny-C programming language using LEX tools. The specifications of Tiny-C is given above.

Specifications of Lexical Analyzer:
(a) The name of the scanner function should be "int yylex()", it returns the integer as token.
(b) Each token may have some attributes. For example : If the token corresponds to "integer constant" than yylex() returns an integer corresponding to "integer constant" but the value of "integer constant" is its attribute. Such attributes should be made available to the future stages of compilation through a global variable of C-Union type which holds atleast the following attributes :
- Value of the integer constant in case of integer token
- Value of the floating point constant in case of floating point token
- character string for other cases. Like it will have the name of the identifier in case of identifier token
(c) Output Format : Print only the token name in a new line, ' <token name>newline '. In case of integer constant and floating point constant print ' <token name>tabspace<value>newline '. In case of identifier or literal constant print ' <token name>tabspace<character string>newline '. Nothing else should be outputed.

Specification of Token Names is as follows: