PRINCIPLES OF COMPILER DESIGN

CS1352                       PRINCIPLES OF COMPILER DESIGN               3  1  0  100

 

AIM

At the end of the course the student will be able to design and implement a simple compiler.

OBJECTIVES

·          To understand, design and implement a lexical analyzer.

·          To understand, design and implement a parser.

·          To understand, design code generation schemes.

·          To understand optimization of codes and runtime environment.

UNIT I                 INTRODUCTION TO COMPILING                         9

Compilers - Analysis of the source program - Phases of a compiler - Cousins of the Compiler - Grouping of Phases - Compiler construction tools - Lexical Analysis - Role of Lexical Analyzer - Input Buffering - Specification of Tokens.

                                                                                                                                                                                     

UNIT II                      SYNTAX ANALYSIS                                                         9         

Role of the parser -Writing Grammars -Context-Free Grammars - Top Down parsing - Recursive Descent Parsing - Predictive Parsing - Bottom-up parsing - Shift Reduce Parsing - Operator Precedent Parsing - LR Parsers - SLR Parser - Canonical LR Parser - LALR Parser.

UNIT III        INTERMEDIATE CODE GENERATION                                  9

Intermediate languages - Declarations - Assignment Statements - Boolean Expressions - Case Statements - Back patching - Procedure calls.

Parse Tree

• Inner nodes of a parse tree are non-terminal symbols.

•  The leaves of a parse tree are terminal symbols.

•  A parse tree can be seen as a graphical representation of a derivation

Ambiguity

Parsing Derivations – Principles of Compiler Design

E Þ E+E

—E+E derives from E

—we can replace  E by E+E

—to able to do this, we have to have a production rule  E®E+E in our grammar.

—

E Þ E+E Þ id+E Þ id+id

—A sequence of replacements of non-terminal symbols is called a derivation of id+id from E.

  Þ   : derives in one step

  Þ  : derives in zero or more steps

  Þ  : derives in one or more steps

Means   E-> E+E -> id + E -> id + id

Parsing – Principles of Compiler Design

Need of a Parser

•Syntax Analyzer creates the syntactic structure of the given source program.

•This syntactic structure is mostly a parse tree.

•Syntax Analyzer is also known as Parser.

•The syntax of a programming is described by a context-free grammar (CFG).

•The syntax analyzer (Parser) checks whether a given source program satisfies the rules implied by a context-free grammar or not.

–If it satisfies, the parser creates the parse tree of that program.

–Otherwise the parser gives the error messages.

Parser

BACKTRACKING ALGORITHM – KNAPSACK PROBLEM

BACKTRACKING ALGORITHM – KNAPSACK PROBLEM

Aim:

            To write a C program to solve the knapsack problem using backtracking algorithm

Algorithm:

            Step 1: Declare the variables, array size and functions

            Step 2: Get the value of number of objects and size of knapsack

Step 3: Enter weight and profit of objects

Step 4: Assign the initial values

Step 5: Call the necessary function and display the profit

Step 6: End of program

Coding:

DIJKSTRA’S ALGORITHM

DIJKSTRA’S ALGORITHM

Aim

            To implement Dijkstra’s algorithm to find the shortest path.

Algorithm

            Step1: [Include all the header files]

            Step2: Call allSelected( )

            Step3: Call Shortpath( )

            Step4: Access the functions from main

            Step5: End

Algorithm For ALLSELECTED( )

            Step1: Initialise i=0

            Step2: Check whether i<max

            Step3: Check whether Selected[i]=0

                        Return 0

            Step4: Else Return 1

            Step5: Return

Algorithm For SHORTPATH( )

            Step1: Initialise i=0 ,  Check i<max

                       Distance[i]=INFINITE

            Step2: Assign selected[current].distance[0]=0,

                        Current=0

            Step3: While(!allSelected(Selected))

                        Perform(Selected[i]= =0)

                        Current=k

                        Selected[current]=1

                        Print k

Coding:

HASHING TECHNIQUE

HASHING TECHNIQUE

Aim:

            To implement a program using Hashing technique.

Algorithm:

            Step1: Include necessary header files

            Step2: Declare necessary variables

            Step3: Check the value of  *S

                        Then call Insert( )

                            Print “Enter the string”

                        Read S

            Step4: Check the value of *S

            Step5: Then print S by calling hGetVal( )

            Step6: Call PrintHash( )

            Step7: End

Algorithm For hINSERT( ):

            Step1: Allocate memory to pointer

            Step2: Assign index            hGetIndex ( )

            Step3: Assign Ptr            Key         Strdup(key)

                                    Ptr         Val         Val

                                    Ptr         next         h[index]

                                    h[index]        Ptr

            Step4: Print “h[index]=key”

            Step5: Return

Algorithm For hGETVALUE( ):

Step1: [Ptr=h[hGetIndex(key)]]

Step2: If[Ptr && strcmp(Ptr        key)]

                        Then Ptr          Ptr        next

Step3: If[Ptr],Check the value of Ptr

                        [Return Ptr        Val]

Step4: [Return -1]

Algorithm For PRINTHASH( ):

PRIORITY QUEUE USING HEAP

PRIORITY QUEUE USING HEAP

Aim:

            To implement priority queue using Heap in C program.

Algorithm:

            Step 1: [Include necessary header files]

            Step 2: [Define maxsize as 15]

            Step 3: [Declare necessary variables]

            Step 4: READ  option, opt

                        IF opt is 1 THEN CALL INSERT()

                        IF opt is 2 THEN CALL DELMAX()

                        IF opt is 3 THEN CALL DIS()

            Step 5: [END OF MAIN FUNCTION]

Algorithm For INSERT()

EXPRESSION TREE

EXPRESSION TREE

Aim:

                                    To write a C program to demonstrate an expression tree.

Algorithm for Main ()

                                    Step 1: [ INCLUDE NECESSARY HEADER FILES]

                                    Step 2: [READ X]

                                    Step 3:[ CALL EXPTREE(),CALL DISPLAY(), CALL INORDER(),CALL

 PREORDER(),CALL EVALUATE ()]

Algorithm for EXPTREE()

            Step 1: Read Character

            Step 2: IF Character        operator then

                        CALL PUSH_OP()

            Step 3: [IF Character has only numbers]

                        IF [ is ALnum( str[i]           1 )] THEN

                        CREATE Newnode

            Step 4: Check for ‘ NULL ‘ condition

            Step 5: ASSIGN priority

            Step 6: IF ( Priority !=0) THEN CALL POP_OP()

            Step 7: IF Character = ‘)’ THEN CALL PUSH_OP()

Algorithm for INORDER (tree t)

BINARY SEARCH TREE

BINARY SEARCH TREE

Aim

To write a C program to implement a stack using binary search tree.

Algorithm

1.                  [Include all the necessary header files.]

2.                  [Declare the structure with all necessary variables.]

3.                  Read x;

4.                  Call INORDER().

5.                  Call PREORDER().

6.                  Call POSTORDER().

7.                  Call display().

8.                   

Algorithm For INSERT(P,X)

POLYNOMIAL MANUPULATION

POLYNOMIAL MANUPULATION

Aim

To implement polynomial manipulation using doubly linked lists.

Algorithm

POLYADD(POLY1: POLY2:POLY)

HEAD:POLY

Step 1: Assign HEAD+=NULL

Step2: While (POLY !=null)

Step3: HEAD=INSERTNODE(HEAD,COPYNODE,(POLY1,1))

Step4: POLY1=POLY1àNEXT

Step5: [End of Step2 while structure]

Step6: While(POLY2 1=NULL)

Step7: HEAD =INSERTNODE(HEAD,COPYNODE(POLY2,1))

Step8: POLY2=POLY2àNEXT

Step9: [End of Step 6 while Structure]

Step10: Return HEAD

END POLYADD()

Algorithm for polynomial subtraction

POLYSUB(POLY1:POLY, POLY2:POLY)

HEAD:POLY

Step1: Assign HEAD=NULL

Step2: While(POLY1!=NULL)

Step3: HEAD=INSERTNODE(HEAD,COPYNODE(POLY1,1))

Step4: POLY1=POLY1à NEXT

Step5: [End of Step2 while Structure]

Step6:While(POLY2!=NULL)

Step7: HEAD=INSERTNODE(HEAD,COPYNODE(POLY2,-1))

Step8: POLY2=POLY2àNEXT

Step9: [End of Step 6 While Structure]

Step10: Return HEAD

END POLYSUB()

Coding:

DOUBLY LINKED LIST – LINKED LIST IMPLEMENTATION

DOUBLY LINKED LIST – LINKED LIST IMPLEMENTATION

      Aim:

         To write a program to implement doubly linked list using linked list.

      Algorithm:

         Step 1: Declare header and pointer variables

         Step 2: Display the choices

         Step 3: If choice is 1 the get the element to be inserted in beginning and call ins_beg function.

         Step 4: If choice is 2 the get the element to be inserted in the end and call the ins_end function

         Step 5: If choice is 3 then get the element to be deleted and call deletion function.

         Step 6: If choice is 4 then call display duncation

         Step 7: If choice is default the exit the program

         Step 8: Terminate the program execution.

      Program:

LINKED LIST IMPLEMENTATION OF SINGLY LINKED LIST

LINKED LIST IMPLEMENTATION OF SINGLY LINKED LIST

Aim:

   To write a program to implement singly linked list using linked list.

Algorithm:

   Step 1: initialize the list as null

   Step 2: Display linked list operations insert, delete and display the result.

   Step 3: If choice is 1 the read element to be inserted and call the insert function

   Step 4: If choice is 2 then read element to be deleted and call the delete function

   Step 5: If choice is 3 then call display function

   Step 6: If choice is default the exit the program.

Prog Code:

LINKED LIST IMPLEMENTATION OF STACK

LINKED LIST IMPLEMENTATION OF STACK

Aim

            To demonstrate linked list implementation of stack using a C program.

Algorithm

            Step 1: [Include all the necessary header files]

            Step 2: [Declare the Variables]

            Step 3: Read operator

            Step 4: IF opt <---THEN

                        Step 4.1: READ n

                        Step 4.2: WHILE (n        n-1)

                                    Step 4.2.1: READ d

                                    Step 4.2.2: CALL INSERT( start , d)

                        Step 4.3: [End of while Structure]

            Step 5: IF opt         2 THEN

                        Step 5.1: READ x

                        Step 5.2: CALL del(start,x)

            Step 6: IF opt            3 THEN

                        Step 6.1: READ x

                        Step 6.2: CALL FIND

            Step 7: IF opt         4 THEN

                        Step 7.1: READ x

                        Step 7.2: CALL FINDPREVIOUS

Step 8: IF opt         5 THEN

                        Step 8.1: READ x

                        Step 8.2: CALL FINDNEXT(start, x)

Step 9: IF opt         6 THEN

            CALL len(Start)

Step 10: IF opt         7 THEN

            CALL printlist(Start)

Step 10: IF opt         8 THEN

            CALL erase (Start)

Step 12: [End of Main]

Algorithm For Find(struct node*p, int x, int *pos)

            Step 1: temp          p

            Step 2 :*pos         1

            Step 3: IF ( TEMP        NULL) THEN

                        RETURN NULL

                        ELSE

                        WHILE ( TEMP!= NULL && TEMP          DATA!= X)

                        ASSIGN 1 TO *POS+1 AND TEMP’S LLINK FIELD TO TEMP

                        RETURN THE TEMP

Algorithm for Previous (struct node*p, int x)

            Step 1: temp          p

            Step2: IF ( TEMP        NULL) THEN

                        RETURN NULL

                        ELSE

                        WHILE (TEMP        LINK != NULL && TEMP       LINK      DATA!= X)

                       

ASSIGN TEMP’S LINK FIELD TO TEMP

                        RETURN THE TEMP

Algorithm For Find next(struct node*p, int x)

            Step 1: temp          p

            Step2: IF ( TEMP        NULL) THEN

                        RETURN NULL

                        ELSE

                        WHILE (TEMP        LINK != NULL && TEMP      DATA!= X)

                        ASSIGN TEMP’S LLINK FIELD TO TEMP

                        RETURN THE TEMP’S LINK FIELD

Coding:

ARRAY IMPLEMENTATION OF CIRCULAR QUEUE

ARRAY IMPLEMENTATION OF CIRCULAR QUEUE

Aim

                        To write a c program using arrays for implementing circular queue data structure.

Algorithm

                        Step 1: [Include All Header Files Required]

                        Step 2: [Define the array size as 5 and declare front and rear pointers]

                        Step 3: Declare the functions isEmpty() , isFull(), enqueue(), size(),dequeue(), peek() and

 view()]

                        Step 4: [Call the functions]

                                    Choice :1  CALL enqueue()

                                    Choice :2  CALL deenqueue()

Choice :3  CALL peek()

Choice :4  CALL size()

Choice :5  CALL view()

Algorithm for isEmpty( )

                        Step 1: [Check for underflow]

                                    If ( front         -1 and rear          -1 )

                                    RETURN -1

                        Step 2: Else RETURN 0

                                    [Finish the process]

Algorithm for isFull( )

Step 1: [Check for overflow]

                                    If (= (rear+1)% qsize         front )

                                    RETURN -1

                        Step 2: Else RETURN 0

                                    [Finish the process]

Algorithm for Enqueue( )

STEP 1: If[front= =rear]

                        Initialize front=rear=0

STEP 2: else rear=(rear+1)% qsize

                         Set queue[rear] =value

                         [return]

Algorithm for Dequeue( )

STEP 1: If[front = =rear]

                   1.1: temp=queue[front]

                  1.2: Initialize front=rear=-1

STEP 2:else

                 2.1: front=(front+1)% qsize

                        [return]

Algorithm for Peek( )

STEP 1:If [front= =rear]

STEP 1.1: temp=queue[front]

                            [return]

Algorithm for Size( )

STEP 1:If [front= =rear]

                     1.1: Set f=front

                     1.2: Set count=1

STEP 2: If [front!=rear]

                      2.1: front=(front+1)%qsize

                      2.2: set count=count+1

                             [return]

Algorithm for View( )

STEP 1: If [front = =rear]

                         Write (“Queue is empty”)

STEP 2: else

                         [display elements]        

Coding:

IMPLEMENTATION OF LINEAR QUEUE USING ARRAYS

IMPLEMENTATION OF LINEAR QUEUE USING ARRAYS

Aim

To write a C-program to implement linear queue data structure using arrays.

Algorithm

STEP 1: Start

STEP 2: [Include all header files]

STEP 3: [Declare the variables]

STEP 4: [If n->1 call the function Enqueue( )]

STEP 5: [If n->2 call the function Dequeue( )]

STEP 6: [If n->3 call the function Peep( )]

STEP 7: [If n->4 call the function Size( )]

STEP 8: [If n->5 call the function View( )]

STEP 9: [else Exit( )]

STEP 10: Stop

Algorithm for Enqueue( )

STEP 1: If[front= =rear]

               Initialize front=rear=0

STEP 2: else rear=(rear+1)% qsize

               Set queue[rear] =value

               [return]

Algorithm for Dequeue( )

STEP 1: If[front = =rear]

          1.1: temp=queue[front]

          1.2: Initialize front=rear=-1

STEP 2:else

          2.1: front=(front+1)% qsize

                 [return]

Algorithm for Peep( )

STEP 1:If [front= =rear]

STEP 1.1: temp=queue[front]

                  [return]

Algorithm for Size( )

STEP 1:If [front= =rear]

          1.1: Set f=front

           1.2: Set count=1

STEP 2: If [front!=rear]

          2.1: front=(front+1)%qsize

          2.2: set count=count+1

                 [return]

Algorithm for View( )

STEP 1: If [front = =rear]

               Write (“Queue is empty”)

STEP 2: else

               [display elements]        

             

Coding: