Course Material for Compilers,ADSL and DBMS

Unit I 1)Explain Role of Lexical Analyzer in Compiler 2)  Explain use of yyleng, yytext, yylval, yywrap in yacc.. Unit II 1)Construct LR(0) item-set for following grammar. E E + E | E * E | id where + , * , id are terminals. 2) Explain left factoring with example. Unit III 1)Generate Quadruple for a = b + (c * d) / f 2) Explain  Intermediate code generation of declaration statement. Unit IV 1)Explain Parameter passing methods along with suitable example [8] b) Explain Function Call and Return with suitable example Unit V 1)Explain Simple Code Generator Algorithms along with suitable example. [8] 2) What is DAG? Explain the role of DAG in Code Generation Unit VI 1)What is loop transformations? What are its types 2)Explain Following Data Flow Properties Available Expressions, Reaching Definitions

Unit Wise Assignments  Unit I 1)Explain  LEX features and specification. 2)Write regular expression for comment,operators,datatype,identifier ,keywords. Unit II 1) Expalin automatic construction of parsers using YACC. (Explain for calculator with lex and yacc specifications) 2) Explain Need of semantic analysis. Unit III 1)Explain with exampleThree-Address codes: Quadruples, Triples and Indirect Triples 2)Explain S and L attributed grammar Unit iv 1)Explain Activation Record, 2)Explain display mechanism Unit V 1)Explain Issues in code generation. 2)Explain Register allocation and Assignment, Unit VI 1) Explain common sub-expression elimination, variable propagation, code movement, strength reduction, dead code elimination. 2)Explain Data flow equations and iterative data flow analysis.

// A C++ program to print topological sorting of a DAG #include<iostream> #include <list> #include <stack> using namespace std; // Class to represent a graph class Graph { int V; // No. of vertices' // Pointer to an array containing adjacency listsList list<int> *adj; // A function used by topologicalSort void topologicalSortUtil(int v, bool visited[], stack<int> &Stack); public: Graph(int V); // Constructor // function to add an edge to graph void addEdge(int v, int w); // prints a Topological Sort of the complete graph void topologicalSort(); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } // A recursive function used by topologicalSort void Graph::topologicalSortUtil(int v, bool visited[], stack<int> &Stack) { // Mark the current node as visited. visited[v] = true;

//C code for  A Register Allocation algorithm that translates the given code into one with a fixed number of registers. #include<stdlib.h> #include<stdio.h> /* We will implement DAG as Strictly Binary Tree where each node has zero or two children */ struct bin_tree { char data; int label; struct bin_tree *right, *left; }; typedef struct bin_tree node; /* R is stack for storing registers */ int R[10]; int top; /* op will be used for opcode name w.r.t. arithmetic operator e.g. ADD for + */ char *op; /* insertnode() and insert() functions are for adding nodes to tree(DAG) */void insertnode(node **tree,char val) { node *temp = NULL; if(!(*tree)) { temp = (node *)malloc(sizeof(node)); temp->left = temp->right = NULL; temp->data = val; temp->label=-1; *tree = temp; } } void insert(node **tree,char val) { char l,r; int numofchildren; insertnode(tree, val); printf("\nEnter number of children of %c:",val); scanf("%d&quo

//c code for illustrating Code optimization #include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> struct TAC { char res[5]; char op[2]; char arg1[5]; char arg2[5]; }quad[10]; struct ref { char * id; int label; struct node *ptr; }ref[10]; int cnt=0; int n; typedef struct node { struct node *left; struct node *right; char * val; char arg1[10]; char arg2[10]; char lable1; char label2; }node; struct node *nptr; struct node *ptr; void printtree(); node * mknode(node *left,node *right,char *val,char *arg1,char *arg2,char l1,char l2); int search(char*); void main() { int i,sres; printf("Enter how many TAC"); scanf("%d",&n); for(i=0;i<n;i++) { printf("Enter res"); scanf("%s",quad[i].res); printf("Enter op"); scanf("%s",quad[i].op); printf("Enter arg1"); scanf("%s",quad[i].arg1); printf("Enter arg2"

Contents of tac.l file  %{ #include "y.tab.h" #include <string.h> char * split(char* s,char* delimeter); %} relop >=|<=|>|<|==|!= number [0-9]+ %% [\n\t ]+ {;} "if" {return IF;} "while" {return WHILE;} "for" {return FOR;} "else" {return ELSE;} "int"|"string"|"char"|"double" { return TYPE;} [a-z]([a-z]|[0-9])* { yylval.tuple.result = strdup(yytext); return identifier; } [0-9]+  {yylval.tuple.num= atoi(yytext); return number;} {relop} { yylval.tuple.arg1 =strdup(yytext); return RELOP;}  [-+*=/;] {return yytext[0];} [(){}]               {return yytext[0];} %% int yywrap(void) { return 1; } Contents of tac.y file  %{     int yylex();     void yyerror(char* s);     #include <stdio.h>     #include <stdlib.h>     #include <string.h>     char* symbols[1000];     int symbolValues[1000];     int symbolCounter =

Contents of type1.l file  %{ #include<stdio.h> #include<string.h> #include"y.tab.h" %} %% [a-zA-Z]+[a-zA-Z0-9]*"(" {strcpy(yylval.DataType,yytext);return function;} int|float|char {strcpy(yylval.DataType,yytext); return Type;} [a-zA-Z]+[a-zA-Z0-9]*"," {strcpy(yylval.DataType,yytext);return parameter;} [a-zA-Z]+[a-zA-Z0-9]*"){}" {strcpy(yylval.DataType,yytext);return functionbody; } ");" {strcpy(yylval.DataType,yytext);return functioncall;} [a-zA-Z]+[a-zA-Z0-9]* {strcpy(yylval.ID,yytext); return Name;} [0-9]+ {strcpy(yylval.DataType,"int"); return Type;} [0-9]+.[0-9]+ {strcpy(yylval.DataType,"float"); return Type;} "'"[a-zA-Z]+"'" {strcpy(yylval.DataType,"char"); return Type;} ";" return SC; "=" return EQ; "," return C; "\n" {} %% Contents of type1.y file  %{ #include<stdio.h> #include

File name sym.l %{ #include<stdio.h> #include<string.h> typedef struct node {     char ID[10],DataType[10];     struct node * next; } node_t; node_t *head = NULL,*temp=NULL,*current=NULL; %} %% int|float|char {if(head==NULL){head = (node_t*)malloc(sizeof(node_t)); strcpy(head->DataType,yytext);}else{strcpy(temp->DataType,yytext);}} [a-zA-Z]+[a-zA-Z0-9]* {if(head->next==NULL){strcpy(head->ID,yytext);head->next=NULL;}else{strcpy(temp->ID,yytext);temp->next=NULL;}} ";"  {if(temp==NULL){temp=(struct node*)malloc(sizeof(struct node));head->next=temp;}else{temp->next=(struct node*)malloc(sizeof(struct node));temp=(node_t*)temp->next;}} "\n" {node_t *current = head;     while (current != NULL) {         printf("%s\t%s\n", current->ID,current->DataType);         current = current->next;     }              } %% void main() { yylex(); } int yywrap() { return 1; } /* OUTPUT: ra

file name Cal.l  %{ #include<stdio.h> #include "y.tab.h" //extern int yylval; %} %% [0-9]+ { yylval=atoi(yytext); return NUMBER; } [\n] return 0; . return yytext[0]; %% int yywrap() { return 1; } file name  cal.y %{ #include<stdio.h> int flag=0; %} %token NUMBER %left '+' '-' %left '*' '/' '%' %left '(' ')' %% ArithmeticExpression: E{          printf("\nResult=%d\n",$$);          return 0;         }; E:E'+'E {$$=$1+$3;}  |E'-'E {$$=$1-$3;}  |E'*'E {$$=$1*$3;}  |E'/'E {$$=$1/$3;}  |E'%'E {$$=$1%$3;}  |'('E')' {$$=$2;}  | NUMBER {$$=$1;} ; %% int main() {   yyparse();   if(flag==0)    printf("\nEntered arithmetic expression is Valid\n\n");   return 0; } int yyerror() {    printf("\nEntered arithmetic expression is Invalid\n\n");    flag=1;    return 0; }

%{ int lc=0; %} %% printf printf("\nPrintf found at line no. %d",lc); scanf  printf("\nScanf found at line no. %d",lc); if | else | while | do | switch | case | for | return printf("\n%s Keyword found at line no. %d ",yytext,lc); "void main" printf("\n%s Keyword found at line no. %d ",yytext,lc); \"[^"]*\" printf("\nQuoted string found at line no. %d",lc); #include | #include<stdio.h> printf("\nHeader found at line no. %d",lc); int | float | char | double | long printf("\n%s Datatype found at line no. %d",yytext,lc); ";" | "," | ":" | "{" | "}" | "(" | ")" | "." printf("\n%s Punctuation Symbol found at line no. %d",yytext,lc); [a-z]+[a-z,0-9]* printf("\n %s Variable found at line no. %d\n",yytext,lc); [0-9]+ printf("\n%s Number found at l

1. Implement a Lexical Analyzer using LEX for a subset of C.  2. Implement a parser for an expression grammar using YACC and LEX for the subset of C. Cross check your output with Stanford LEX and YACC. 3. Generate and populate appropriate Symbol Table. 4. Implementation of Semantic Analysis Operations (like type checking, verification of function parameters, variable declarations and coercions) possibly using an Attributed Translation Grammar. 5. Implement the front end of a compiler that generates the three address code for a simple language. 6. A Register Allocation algorithm that translates the given code into one with a fixed number of regsters. 7. Implementation of Instruction Scheduling Algorithm. 8. Implement Local and Global Code Optimizations such as Common Sub-expression Elimination, Copy Propagation, Dead-Code Elimination, Loop and Basic-Block Optimizations.  9. Mini-Project 1: