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

TEXT EDITOR

PASS2 OF DIRECTLINKING LOADER

PROGRAM:

#include<stdio.h>

#include<conio.h>

#include<string.h>

#include<stdlib.h>

struct exttable

{

  char csect[20],sname[20];

  int padd,plen;

}estab[20];

struct objectcode

{

  unsigned char code[15];

  int add;

}obcode[500];

void main()

PASS1 OF DIRECT LINKING LOADER

PROGRAM:

#include<stdio.h>

#include<conio.h>

#include<string.h>

struct estab

{

char csname[10];

char extsym[10];

int address;

int length;

}es[20];

void main()

{

  char input[10],name[10],symbol[10],ch;

  int count=0,progaddr,csaddr,add,len;

  FILE *fp1,*fp2;

  clrscr();

  fp1=fopen("LINP.DAT","r");

  fp2=fopen("LOADMAP.DAT","w");

  printf("\n\nEnter the address where the program has loaded: ");

  scanf("%x",&progaddr);

  csaddr=progaddr;

  fprintf(fp2,"CS_NAME\tEXT_SYM_NAME\tADDRESS\tLENGTH\n");

  fprintf(fp2,"------------------------------\n");

  fscanf(fp1,"%s",input);

  while(strcmp(input,"END")!=0)

Relocation loader using C

IMPLEMENTATION OF RELOCATION LOADER

AIM

To implement relocation loader using C.

ALGORITHM

1.Enter new starting location to which object has ti be relocated.

2.Read the content of the input file as strings one at a time in an array input.

3.Transfer the string read in array input into another array output until it is incremented.

4.Move consecutive next 3 strings into array “output”.

5.Cover current location bit associated with each text record to binary form.

6.Make necessary changes in corresponding words of object code and store the updated object code into array “output”.

7.Move object code for which corresponding  relocation bit is not set directly to the array “output” from array “input” without any change.

8.Repeat step 2 to 8 until end record is encountered.

9.If the object code is in character form ,convert into internal hexadecimal representation.

10.Move object code to specified location in memory

11.Write starting LOCCTR value of block of object code and the corresponding internal hexadecimal representative to the output files.

Absolute loader

IMPLEMENTATION OF ABSOLUTE LOADER

AIM

To implement absolute loader using C.

ALGORITHM

1.Read loader record and filter the starting location and other details.

2.Read the first text record.

3.If the object code is in character form convert it into internal hexadecimal representation.

4.Move object code to specified location in memory.

5.Write starting location couter value of block of object code and corresponding internal hexadecimal representation to the output file.

6.Read next record from the input file.

7.Close all opened files and exit.

PROGRAM:

#include<stdio.h>

C-program for implementing a macro processor.

IMPLEMENTATION OF MACRO PROCESSOR

AIM

To write a C-program for implementing a macro processor.

ALGORITHM

1.Get the state from input file.

2.From the line read,check if opcode is directive “MACRO” if so then number of macro “n” must be incremented.

3.Repeat step 1 and 2 until end of file is encountered.

4.Open “n” number of files in write mode.These files will later hold body of “n” macro respectively.

5.Rewind the input file pointer.

6.If opcode is “MACRO”

7.Enter macro name present in operand file field into array names “m”.

8.Write line to expanded output file.

9.Enter lines in body of each macro into corresponding files already opened in file.

10.Write body of each macro to be expanded output file also until “END” is reached.

11.Else if OPCODE is “CALL” the line must be a macro invocation statement so the macro body is retrieved from the corresponding file.

12.Write all the remaining lines directly to expanded lines.

PROGRAM:

#include<stdio.h>

single pass assembler using C

IMPLEMENTATION OF SINGLE PASS ASSEMBLER

AIM

To implement single pass assembler using C.

ALGORITHM

1.Read first line from the intermediate file.

2.Check to see if the opcode from the first line read is “START”.If so then write label,opcode and operand field values of corresponding statement directly to final output files.

3.Start the following processing for other lines in intermediate file if it is not a comment line until an “END” statement is reached.

4.Start writing labels LOCCTR opcode and operand fields of corresponding statements to the output file along with the object code.The object code is found by assembling each statement opcode machine equivalent with the label address.

5.If there is no symbol or label in the operand field , then the operand address is assigned as zero and it is assembled with object code of instruction.

6.If OPCODE is BYTE,WORD,RESB etc are convert constants to object code close operand file and exit.

PASS2_OF_2_PASS_ASSEMBLER

IMPLEMENTATION OF PASS-2 OF 2-PASS ASSEMBLER

AIM

To write a C-program to implement pass-2  assembler.

ALGORITHM

1.Read first line from the intermediate file.

2.Check to see if the opcode from the first line read is “START”.If so then write label,opcode and operand field values of corresponding statement directly to final output files.

3.Start the following processing for other lines in intermediate file if it is not a comment line until an “END” statement is reached.

4.Start writing labels LOCCTR opcode and operand fields of corresponding statements to the output file along with the object code.The object code is found by assembling each statement opcode machine equivalent with the label address.

5.If there is no symbol or label in the operand field , then the operand address is assigned as zero and it is assembled with object code of instruction.

6.If OPCODE is BYTE,WORD,RESB etc are convert constants to object code close operand file and exit.

PROGRAM:

#include<stdio.h>

PASS1_OF_2_PASS_ASSEMBLER

IMPLEMENTATION OF PASS-1 OF TWO PASS ASSEMBLER

AIM

To write a C-program to implement pass-1 assembler ie object code.

ALGORITHM

1.Read first line from the input file.

2.Check to see if the opcode from the first line read is “START”.If so then write label opcode and            operand field values of corresponding statement directly to find output files.

3.Start the following processing for other lines in input file if it is not a comment line until an “END” statement is reached.

4.Start writing label LOCCTR opcode and operand fields of corresponding statement to the output file along with object code.The object code is found by assembling each statement opcode machine equivalent with label address.

5.If there is no symbol or label in the operand field,then the operand address is assigned as zero and it is assembled with object code of instruction.

6.Ip OPCODE is BYTE,WORD,RESB etc are convert constants to object code.close operand file and exit.

PROGRAM:

#include<stdio.h>

SYMBOL TABLE

SYMBOL TABLE

AIM

To write a program in C to implement symbol table.

ALGORITHM

1.Create a structure having member variable and values

2.Display the option and get choice from the user

3.I f choice 1 call create()

4.If choice 2 call insert()

5.If choice 3 call modify()

6.If choice 4 call search()

7.If choice 5 call display()

8.Exit

9.create()

                Do till less than 3

                Get input from the user for variables and values

10.insert()

                Get number of records to insert.

                a.Do till i is less than sum of I and number of records to insert.

                b.Get input for symbol name and value

11.modify()

                Get record or symbol name to modify

                If it is equal to  any symbol name then print “record found”

                Else print “record not found”

                Get the value for corresponding symbol name

12.search()

                Get the symbol name to modify

If it is present in table then print “record found”

Else print “record not found”

Get the value for corresponding symbol name

13.display()

                Do till k is less than tottal number of records.

                Print the symbil name and values.

Distributed Computing University questions 2011

Answer ALL questions.
1. What are the disadvantages of distributed systems?
2. Differentiate between tightly coupled and loosely coupled systems.
3. What is predicate addressing?
4. What do you mean by server crashes and client crashes?
5. What is Synchronization?
6. Explain remote access model.
7. Discuss Fault Tolerance Issues.
8. Write a note on Concurrency Control.
9. What is a query in Distributed DBMS? Explain.
10. What is call by reference? Give an example.
PART B — (4 ? 10 = 40 marks)