COMPILER DESIGN LAB

ALL PROGRAMS DOCUMENTS

Program to construct a Recursive Descent Parser:

#include<stdio.h>

#include<string.h>

int i=0,e=0,n=0,j,l;

char str[50];

void E();

void F();

void E_();

void T();

void T_();

void ed();

int main()

{

printf("Recursive Descent Parser\n\n");

printf("\tE->TE'\n\tE'->+TE'/e\n\tT->FT'\n\tT'->*FT'/e\n\tF->(E)|id");

printf("\nEnter the input exp:");

scanf("%s",str);

l=strlen(str);

E();

if(e>0)

printf("String is not accepted");

else

{

if(n==0 && e==0 && i==1)

printf("String is not ACCEPTED");

else

printf("String is ACCEPTED");

}

}

void E()

{

T();

E_();

}

void T()

{

F();

T_();

}

void T_()

{

if(str[i]=='*')

{

i++;

F();

T_();

}

}

void E_()

{

if(str[i]=='+')

{

i++;

T();

E_();

}

              else

                    e++;

}

void F()

{

if(str[i]=='i'&&str[i+1]=='d')

i+=2;

else if (str[i]=='(')

{

i++;

n++;

E();

ed();

}

else

e++;

}

void ed()

{

if (str[i]==')')

{

i++;

n--;

T_();

E_();

}

else

e++;

}

OUTPUT:

FIRST & FOLLOW PROGRAM

#include<stdio.h>

#include<string.h>

#define max 20

char prod[max][10];

char ter[10],nt[10];

char first[10][10],follow[10][10];

int eps[10];

int count=0;

int findpos(char ch)

{

int n;

for(n=0;nt[n]!='\0';n++)

if(nt[n]==ch)

break;

if(nt[n]=='\0')

return 1;

return n;

}

int IsCap(char c)

{

if(c >= 'A' && c<= 'Z')

return 1;

return 0;

}

void add(char *arr,char c)

{

int i,flag=0;

for(i=0;arr[i]!='\0';i++)

{

if(arr[i] == c)

{

flag=1;

break;

}

}

if(flag!=1)

arr[strlen(arr)] = c;

}

void addarr(char *s1,char *s2)

{

int i,j,flag=99;

for(i=0;s2[i]!='\0';i++)

{

flag=0;

for(j=0;;j++)

{

if(s2[i]==s1[j])

{

flag=1;

break;

}

if(j==strlen(s1) && flag!=1)

{

s1[strlen(s1)] = s2[i];

break;

}

}

}

}

void addprod(char *s)

{

int i;

prod[count][0] = s[0];

for(i=3;s[i]!='\0';i++)

{

if(!IsCap(s[i]))

add(ter,s[i]);

prod[count][i-2] = s[i];

}

prod[count][i-2] = '\0';

add(nt,s[0]);

count++;

}

void findfirst()

{

int i,j,n,k,e,n1;

for(i=0;i<count;i++)

{

for(j=0;j<count;j++)

{

n = findpos(prod[j][0]);

if(prod[j][1] == (char)238)

eps[n] = 1;

else

{

for(k=1,e=1;prod[j][k]!='\0' && e==1;k++)

{

if(!IsCap(prod[j][k]))

{

e=0;

add(first[n],prod[j][k]);

}

else

{

n1 = findpos(prod[j][k]);

addarr(first[n],first[n1]);

if(eps[n1] == 0)

e=0;

}

}

if(e==1)

eps[n]=1;

}

}

}

}

void findfollow()

{

int i,j,k,n,e,n1;

n = findpos(prod[0][0]);

add(follow[n],'$');

for(i=0;i<count;i++)

{

for(j=0;j<count;j++)

{

k = strlen(prod[j])-1;

for(;k>0;k--)

{

if(IsCap(prod[j][k]))

{

n=findpos(prod[j][k]);

if(prod[j][k+1] == '\0') // A -> aB

{

n1 = findpos(prod[j][0]);

addarr(follow[n],follow[n1]);

}

if(IsCap(prod[j][k+1])) // A -> aBb

{

n1 = findpos(prod[j][k+1]);

addarr(follow[n],first[n1]);

if(eps[n1]==1)

{

n1=findpos(prod[j][0]);

addarr(follow[n],follow[n1]);

}

}

else if(prod[j][k+1] != '\0')

add(follow[n],prod[j][k+1]);

}

}

}

}

}

void main()

{

char s[max],i;

printf("\nEnter the productions(type 'end' at the last of the production)\n");

scanf("%s",s);

while(strcmp("end",s))

{

addprod(s);

scanf("%s",s);

}

findfirst();

findfollow();

printf("NT.....First \t Follow\n");

printf("--------------------------\n");

for(i=0;i<strlen(nt);i++)

{

printf("%c\t",nt[i]);

printf("%s",first[i]);

if(eps[i]==1)

printf("%c\t",(char)238);

else

printf("\t");

printf("%s\n",follow[i]);

}

printf("--------------------------\n");

}

OUTPUT:

LEXICAL ANALYZER PROGRAM FOR VALIDATING IDENTIFIERS,OPERATORS,COMMENTS AND KEYWORDS

#include <stdbool.h>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

bool isDelimiter(char ch)

{

if (ch == ' ' || ch == '+' || ch == '-' || ch == '*' ||

ch == '/' || ch == ',' || ch == ';' || ch == '>' ||

ch == '<' || ch == '=' || ch == '(' || ch == ')' ||

ch == '[' || ch == ']' || ch == '{' || ch == '}')

return (true);

return (false);

}

bool isOperator(char ch)

{

if (ch == '+' || ch == '-' || ch == '*' ||

ch == '/' || ch == '>' || ch == '<' ||

ch == '=')

return (true);

return (false);

}

bool validIdentifier(char* str)

{

if (str[0] == '0' || str[0] == '1' || str[0] == '2' ||

str[0] == '3' || str[0] == '4' || str[0] == '5' ||

str[0] == '6' || str[0] == '7' || str[0] == '8' ||

str[0] == '9' || isDelimiter(str[0]) == true)

return (false);

return (true);

}

bool isKeyword(char* str)

{

if (!strcmp(str, "if") || !strcmp(str, "else") ||

!strcmp(str, "while") || !strcmp(str, "do") ||

!strcmp(str, "break") ||

!strcmp(str, "continue") || !strcmp(str, "int")

|| !strcmp(str, "double") || !strcmp(str, "float")

|| !strcmp(str, "return") || !strcmp(str, "char")

|| !strcmp(str, "case") || !strcmp(str, "char")

|| !strcmp(str, "sizeof") || !strcmp(str, "long")

|| !strcmp(str, "short") || !strcmp(str, "typedef")

|| !strcmp(str, "switch") || !strcmp(str, "unsigned")

|| !strcmp(str, "void") || !strcmp(str, "static")

|| !strcmp(str, "struct") || !strcmp(str, "goto"))

return (true);

return (false);

}

bool isInteger(char* str)

{

int i, len = strlen(str);

if (len == 0)

return (false);

for (i = 0; i < len; i++) {

if (str[i] != '0' && str[i] != '1' && str[i] != '2'

&& str[i] != '3' && str[i] != '4' && str[i] != '5'

&& str[i] != '6' && str[i] != '7' && str[i] != '8'

&& str[i] != '9' || (str[i] == '-' && i > 0))

return (false);

}

return (true);

}

bool isRealNumber(char* str)

{

int i, len = strlen(str);

bool hasDecimal = false;

if (len == 0)

return (false);

for (i = 0; i < len; i++) {

if (str[i] != '0' && str[i] != '1' && str[i] != '2'

&& str[i] != '3' && str[i] != '4' && str[i] != '5'

&& str[i] != '6' && str[i] != '7' && str[i] != '8'

&& str[i] != '9' && str[i] != '.' ||

(str[i] == '-' && i > 0))

return (false);

if (str[i] == '.')

hasDecimal = true;

}

return (hasDecimal);

}

char* subString(char* str, int left, int right)

{

int i;

char* subStr = (char*)malloc(

sizeof(char) * (right - left + 2));

for (i = left; i <= right; i++)

subStr[i - left] = str[i];

subStr[right - left + 1] = '\0';

return (subStr);

}

void parse(char* str)

{

int left = 0, right = 0;

int len = strlen(str);

while (right <= len && left <= right) {

if (isDelimiter(str[right]) == false)

right++;

if (isDelimiter(str[right]) == true && left == right) {

if (isOperator(str[right]) == true)

printf("'%c' IS AN OPERATOR\n", str[right]);

right++;

left = right;

} else if (isDelimiter(str[right]) == true && left != right

|| (right == len && left != right)) {

char* subStr = subString(str, left, right - 1);

if (isKeyword(subStr) == true)

printf("'%s' IS A KEYWORD\n", subStr);

else if (isInteger(subStr) == true)

printf("'%s' IS AN INTEGER\n", subStr);

else if (isRealNumber(subStr) == true)

printf("'%s' IS A REAL NUMBER\n", subStr);

else if (validIdentifier(subStr) == true

&& isDelimiter(str[right - 1]) == false)

printf("'%s' IS A VALID IDENTIFIER\n", subStr);

else if (validIdentifier(subStr) == false

&& isDelimiter(str[right - 1]) == false)

printf("'%s' IS NOT A VALID IDENTIFIER\n", subStr);

left = right;

}

}

return;

}

int main()

{

char str[100];

printf("ENTER THE STRING:\n");

scanf("%[^\n]s",str);

parse(str); 

return (0);

}

output:

            

PROGRAM TO REMOVE LEFT RECURSTION FROM THE GRAMMER.

#include<stdio.h>  

#include<string.h>  

#define SIZE 10  

  int main () 

  {  

       char non_terminal;  

       char beta,alpha;  

       int num,i;  

       char production[10][SIZE];  

       int index=3; 

       printf("Enter Number of Production : ");  

       scanf("%d",&num);  

       printf("Enter the grammar as E->E-A :\n");  

       for(i=0;i<num;i++)

   {  

            scanf("%s",production[i]);  

       }  

       for(i=0;i<num;i++)

   {  

            printf("\nGRAMMAR : : : %s",production[i]);  

            non_terminal=production[i][0];  

            if(non_terminal==production[i][index])

{  

                 alpha=production[i][index+1];  

                 printf(" is left recursive.\n");  

                 while(production[i][index]!=0 && production[i][index]!='|')  

                      index++;  

                 if(production[i][index]!=0) {  

                      beta=production[i][index+1];  

                      printf("Grammar without left recursion:\n");  

                      printf("%c->%c%c\'",non_terminal,beta,non_terminal);  

                      printf("\n%c\'->%c%c\'|E\n",non_terminal,alpha,non_terminal);  

                 }  

                 else  

                      printf(" can't be reduced\n");  

            }  

            else  

                 printf(" is not left recursive.\n");  

                 index=3;  

       }  

  }   

OUTPUT: