KATHIR COLLEGE OF ENGINEERING

Approved by AICTE / Affiliated to Anna University

Accredited by NAAC with ‘A+’ Grade
Neelambur, Coimbatore–641062

COMPUTER SCIENCE AND ENGINEERING

CS3501-COMPILER DESIGN

NAME :
REGISTER NO :
YEAR : III
SEMESTER : V
ACADEMIC YEAR : 2023-2024(ODD SEM)
BATCH :
 COMPUTER SCIENCE AND ENGINEERING

Bonafide Certificate

This is to certify that the record work for

CS3501-COMPILER DESIGN is the bonafide record of work done by

Mr. /Ms.……………………………………………

[Link]……………………

in V Semester of B.E Computer Science and Engineering during the academic

year 2023– 2024(ODD SEM).

Staff in-Charge Head of the Department

Submitted for the Practical Examination held on …………………

Internal Examiner External Examiner

S. PAGE FACULTY
DATE NAME OF THE EXPERIMENT MARKS
NO. NO. SIGNATURE
Using the LEX tool, Develop a lexical
analyzer to recognize a few patterns in C.
(Ex. identifiers, constants, comments,
1. operators etc.). Create a symbol table,
while recognizing identifiers.

Implement a Lexical Analyzer using LEX Tool

2.

Generate YACC specification for a few

syntactic categories.

a. Program to recognize a valid

arithmetic expression that uses
operator +, -, * and /.
b. Program to recognize a valid variable
3. which starts with a letter followed by
any number of letters or digits.
c. Program to recognize a valid control
structures syntax of C language (For
loop, while loop, if-else, if-else-if,
switch-case, etc.).
d. Implementation of calculator using LEX
and YACC.

Generate three address code for a simple

4.
program using LEX and YACC.
Implement type checking using Lex and
5.
Yacc.
Implement simple code optimization
techniques (Constant folding, Strength
6.
reduction and Algebraic transformation)

Implement back-end of the compiler for

which the three address code is given as
7. input and the 8086 assembly language code
is produced as output.

CONTENT BEYOND SYLLABUS

Implementation Of L-R Parser
8.
Ex. No: 01 Using the LEX tool, Develop a lexical analyzer to recognize a few
Date: patterns in C. (Ex. identifiers, constants, comments, operators
etc.). Create a symbol table, while recognizing identifiers.

Aim:

To write a program for implementing a Lexical analyser using LEX tool and a symbol
table, while recognizing identifiers.

Algorithm:
1. Start the program.
2. Lexically analyze a C-like input source code.
3. identifying and categorizing identifiers, constants, comments, and operators/special
characters.
4. Build a symbol table by adding identifiers and assigning addresses to them.
5. Display the identified tokens and the generated symbol table.
6. Stop the program.

Program:
%{
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_IDENT_LENGTH 50
#define MAX_SYMBOLS 100

typedef struct {
char name[MAX_IDENT_LENGTH + 1];
int address;
} Symbol;

Symbol symbol_table[MAX_SYMBOLS];
int symbol_count = 0;
int current_address = 1000;

void addSymbol(char* name) {

Symbol new_symbol;
strcpy(new_symbol.name, name);
new_symbol.address = current_address;
symbol_table[symbol_count++] = new_symbol;
 current_address += 4; // Assuming each variable occupies 4 bytes
}
%}

%option noyywrap

letter [a-zA-Z]
digit [0-9]
identifier {letter}({letter}|{digit})*
constant {digit}+
comment "\\/\\/.+\\n|\\/\\*(.|\\n)*?\\*\\/"

%%

{identifier} {
printf("Identifier: %s\n", yytext);
addSymbol(yytext);
}

{constant} {
printf("Constant: %s\n", yytext);
}

{comment} {
printf("Comment: %s\n", yytext);
}

[ \t\n] ; // Ignore whitespace and newline

. {
printf("Operator/Special Character: %s\n", yytext);
}

%%

int main() {
yyin = fopen("input.c", "r");
yylex();
fclose(yyin);

// Display symbol table

printf("\nSymbol Table:\n");
printf("Name\t\tAddress\n");
for (int i = 0; i < symbol_count; ++i) {
printf("%s\t\t%d\n", symbol_table[i].name, symbol_table[i].address);
}

return 0;
}

Input.c:

#include <stdio.h>

int main()
{
int number = 42;
printf("The number is: %d\n", number);
return 0;
}
Output:

Result:
Thus, the above program to develop the lexical analyzer , recognize a few patterns
and a symbol table, while recognizing identifiers. in lex has been executed successfully, and
the output has been verified.
Ex. No: 02
Implement a Lexical Analyzer using LEX Tool.
Date:

Aim:
To write a program to implement the Lexical Analyzer using lex tool.

Algorithm:
1. Start the program
2. Lex program consists of three parts.
3. Declaration %%
4. Translation rules %%
5. Auxiliary procedure.
6. The declaration section includes declaration of variables, main test, constants and
regular
7. Definitions.
8. Translation rule of lex program are statements of the form
9. P1{action}
10. P2{action}
11. ……
12. ……
13. Pn{action}
14. Write program in the vi editor and save it with .1 extension.
15. Compile the lex program with lex compiler to produce output file as [Link].c.
16. Eg. $ lex filename.1
17. $gcc [Link].c-11
18. Compile that file with C compiler and verify the output.

Program:
#include <stdio.h>
#include <ctype.h>
#include <conio.h>
#include <string.h>
char vars[100][100];
int vcnt;
char input[1000], c;
char token[50], tlen;
int state = 0, pos = 0, i = 0, id;
char *getAddress(char str[])
{
 for (i = 0; i < vcnt; i++)
if (strcmp(str, vars[i]) == 0)
return vars[i];
strcpy(vars[vcnt], str);
return vars[vcnt++];
}
int isrelop(char c)
{
if (c == '+' || c == '-' || c == '*' || c == '/' || c == '%' || c == '^')
return 1;
else
return 0;
}
int main(void)
{
//clrscr();
printf("Enter the Input String:");
gets(input);
do
{
c = input[pos];
putchar(c);
switch (state)
{
case 0:
if (isspace(c))
printf("\b");
if (isalpha(c))
{
token[0] = c;
tlen = 1;
state = 1;
}
if (isdigit(c))
state = 2;
if (isrelop(c))
state = 3;
if (c == ';')
printf("\t<3,3>\n");
if (c == '=')
printf("\t<4,4>\n");
break;
case 1:
if (!isalnum(c))
{
token[tlen] = '\o';
printf("\b\t<1,%p>\n", getAddress(token));
state = 0;
 pos--;
}
else
token[tlen++] = c;
break;
case 2:
if (!isdigit(c))
{
printf("\b\t<2,%p>\n", &input[pos]);
state = 0;
pos--;
}
break;
case 3:
id = input[pos - 1];
if (c == '=')
printf("\t<%d,%d>\n", id * 10, id * 10);
else
{
printf("\b\t<%d,%d>\n", id, id);
pos--;
}
state = 0;
break;
}
pos++;
} while (c != 0);
getch();
return 0;
}

Output:

Result:
Thus, the program for the exercise on lexical analysis using lex has been successfully
executed and output is verified
Ex. No: 03
Generate YACC Specification For A Few Syntactic Categories.
Date:

Aim:
To write a program for implementing a calculator for computing the given expression
using semantic rules of the YACCtool.

Algorithm:
1. A Yacc source program has three parts as follows:
Declarations
%% translation rules
%% supporting C routines
2. Declarations Section:
i. This section contains entries that:
ii. Include standard I/O header file.
iii. Define global variables.
iv. Define the list rule as the place to start processing.
v. Define the tokens used by the parser.
vi. Define the operators and their precedence.
3. Rules Section:
The rules section defines the rules that parse the input stream. Each rule of a
grammar production and the associated semantic action.
4. Programs Section:
The programs section contains the following subroutines. Because
thesesubroutines are included in this file, it is not necessary to use the yacc
library when processing this file.
5. Main- The required main program that calls the yyparse subroutine to start the
program.
6. yyerror(s) -This error-handling subroutine only prints a syntax error message.
7. yywrap -The wrap-up subroutine that returns a value of 1 when the end of input
occurs. The [Link] file contains include statements for standard input and output,
as programmar file information if we use the -d flag with the yacc command. The
[Link].h file contains definitions for the tokens that the parser program uses.
8. [Link] contains the rules to generate these tokens from the input stream.
Program:
a. Program to recognize a valid arithmetic expression that uses operator +, -, * and /.
Lex Part:

%{
#include<stdio.h> #include"[Link].h" extern int yylval;
%}
%%
[0-9]+ {
yylval=atoi(yytext); return NUM;
}
[\t] ;
\n return 0;
. return yytext[0];
%%

Yacc Part:

%{
#include<stdio.h>
%}
%token NUM
%left '+' '-'
%left '*' '/'
%left '(' ')'
%%
expr: e{
printf("result:%d\n",$$); return 0;
}
e:e'+'e {$$=$1+$3;}
|e'-'e {$$=$1-$3;}
|e'*'e {$$=$1*$3;}
|e'/'e {$$=$1/$3;}
|'('e')' {$$=$2;}
| NUM {$$=$1;}
;
%%
main()
{
printf("\n enter the arithematic expression:\n"); yyparse();
printf("\nvalid expression\n");
}
yyerror()
{
printf("\n invalid expression\n"); exit(0);
}
Output:
$ lex prog5.l
$ yacc -d prog5.y
$ cc -c [Link].c [Link].c
$ cc -o [Link] [Link].o [Link].o -lfl
$ ./[Link]
enter the arithematic expression: 5+6 result:11
valid expression

b. Program to recognize a valid variable which starts with a letter followed by any
number of letters or digits.
%{
#include <stdio.h>
#include <ctype.h>
%}
%token let dig
%%
TERM : XTERM „\n‟
{ printf ( “\nAccepted\n” ); exit(0); }
| error
{ yyerror ( “Rejected\n” ); }
;
XTERM : XTERM let
|XTERM dig
|let
%%
yylex()
{
char ch;
while ( ( ch = getchar ( ) ) == ‟ ‟ ) ;
if ( isalpha (ch) )
return let;
if ( isdigit (ch) ) return dig;
return ch;
}
main()
{
}
printf (“Enter a variable : ”); yyparse ();
yyerror(char *s)
{
printf (“%s”, s);
}
Output:

c. Program to recognize a valid control structures syntax of C language (For loop. while
loop, if-else, if-else-if, switch-case, etc.).
Cal.l

%{
#include<stdio.h> #include<math.h> #include"[Link].h"
%}
%%
([0-9]+|([0-9]*\.[0-9]+)([eE][-+]?[0-9]+)?) {[Link]=atof(yytext); return
NUMBER;}
MEM {return MEM;} [\t];
\$ {return 0;}
\n {return yytext[0];}
. {return yytext[0];}
%%

Cal.y

%{
%}
#include<stdio.h>
#include<math.h>
double memvar;
%union
{
double dval;
}
%token<dval> NUMBER
%token<dval> MEM
%left '-' '+'
%left '*' '/'
%nonassoc UMINUS
%type<dval> expression
%%
start:statement '\n'
|start statement '\n'
statement:MEM '=' expression {memvar=$3;}
COMPILATION OUTPUT FILE PRODUCED
$ yacc -d Y4.y [Link].c , [Link].h
$ cc [Link].c -ll [Link] (PARSER)
./[Link] Running parser
Input OUTPUT
Enter a variable : asd12 Accepted
Enter a variable : 12adr Rejected
|expression {printf("answer=%g\n",$1);}
;
expression:expression'+'expression {$$=$1+$3;}
|expression'-'expression {$$=$1-$3;}
|expression'*'expression {$$=$1*$3;}
|expression'/'expression {if($3==0) yyerror("divide by zero");
else
$$=$1/$3;
};
expression:'-'expression %prec UMINUS {$$= -$2;}
|'('expression')' {$$=$2;}
|NUMBER {$$=$1;}
|MEM {$$=memvar;};
%%
int main(void)
{
printf("Enter the expression"); yyparse();
printf("\n\n"); return 0;
}
int yywrap()
{
return 0;
}
int yyerror(char *error)
{
printf("%s\n",error); return 0;
}

Output:
d. Implementation of calculator using LEX and YACC
%{
#include<stdio.h>
int op=0,i;
float a,b;
%}
dig[0-9]+|([0-9]*)"."([0-9]+)
add "+"
sub "-"
mul"*"
div "/"
pow "^"
ln \n
%%
{dig}{digi();}
{add}{op=1;}
{sub}{op=2;}
{mul}{op=3;}
{div}{op=4;}
{pow}{op=5;}
{ln}{printf("\n the result:%f\n\n",a);}
%%
digi()
{
if(op==0)
a=atof(yytext);
else
{
b=atof(yytext);
switch(op)
{
case 1:a=a+b;
break;
case 2:a=a-b;
break;
case 3:a=a*b;
break;
case 4:a=a/b;
break;
case 5:for(i=a;b>1;b--)
a=a*i;
break;
}
op=0;
}
}
main(int argv,char *argc[])
{
yylex();
}
yywrap()
{
return 1;
}

Output:
Lex cal.l
Cc [Link].c-ll
[Link] 4*8
The result=32

Result:
Thus, the program for the exercise on the syntax using YACC has been executed Successfully
and Output is verified.
Ex. No: 04 Generate three address code for a simple program using LEX and
Date: YACC.

Aim:
To write a C program to generate a three address code for a given expression.

Algorithm:
1. Begin the program.
2. The expression is read from the file using a file pointer.
3. Each string is read and the total no. of strings in the file is calculated.
4. Each string is compared with an operator; if any operator is seen then the previous string
and next string are concatenated and stored in a first temporary value and the three address
code expression is printed.
5. Suppose if another operand is seen then the first temporary value is concatenated to the
next string using the operator and the expression is printed.
6. The final temporary value is replaced to the left operand value.
7. End the program.

Program:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>
struct three
{
char data[10], temp[7];
} s[30];
int main()
{
char d1[7], d2[7] = "t";
int i = 0, j = 1, len = 0;
FILE *f1, *f2;
//clrscr();
f1 = fopen("[Link]", "r");
f2 = fopen("[Link]", "w");
while (fscanf(f1, "%s", s[len].data) != EOF)
len++;
itoa(j, d1, 7);
strcat(d2, d1);
strcpy(s[j].temp, d2);
strcpy(d1, "");
 strcpy(d2, "t");
if (!strcmp(s[3].data, "+"))
{
fprintf(f2, "%s=%s+%s", s[j].temp, s[i + 2].data, s[i + 4].data);
j++;
}
else if (!strcmp(s[3].data, "-"))
{
fprintf(f2, "%s=%s-%s", s[j].temp, s[i + 2].data, s[i + 4].data);
j++;
}
for (i = 4; i < len - 2; i += 2)
{
itoa(j, d1, 7);
strcat(d2, d1);
strcpy(s[j].temp, d2);
if (!strcmp(s[i + 1].data, "+"))
fprintf(f2, "\n%s=%s+%s", s[j].temp, s[j - 1].temp, s[i +
2].data);
else if (!strcmp(s[i + 1].data, "-"))
fprintf(f2, "\n%s=%s-%s", s[j].temp, s[j - 1].temp, s[i +
2].data);
strcpy(d1, "");
strcpy(d2, "t");
j++;
}
fprintf(f2, "\n%s=%s", s[0].data, s[j - 1].temp);
fclose(f1);
fclose(f2);
getch();
return 0;
}

Output:
Sample input: [Link]
out = in1 + in2 + in3 - in4
Sample output: [Link]
t1=in1+in2
t2=t1+in3
t3=t2-in4
out=t3

Result:
Thus, a C program to generate a three address code for a given expression is written,
executed and the output is verified.
Ex. No: 05
Implement Type Checking Using Lex And Yacc.
Date:

Aim:
To write a C program for implementing type checking for given expression.

Algorithm:
1. Start a program.
2. Include all the header files.
3. Initialize all the functions and variables.
4. Get the expression from the user and separate into the tokens.
5. After separation, specify the identifiers, operators and number.
6. Print the output.
7. Stop the program.

Program:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>

char str[50], opstr[75];

int f[2][9] = {{2, 3, 4, 4, 4, 0, 6, 6, 0}, {1, 1, 3, 3, 5, 5, 0, 5, 0}};
int col, col1, col2;
char c;

int swt()
{
switch (c)
{
case '+':
col = 0;
break;
case '-':
col = 1;
break;
case '*':
col = 2;
break;
case '/':
col = 3;
break;
case '^':
 col = 4;
break;
case '(':
col = 5;
break;
case ')':
col = 6;
break;
case 'd':
col = 7;
break;
case '$':
col = 8;
break;
default:
printf("\nTERMINAL MISMATCH\n");
exit(1);
}
getch();
return 0;
}

int main()
{
int i = 0, j = 0, col1, cn, k = 0;
int t1 = 0, foundg = 0;
char temp[20];

printf("\nEnter arithmetic expression:");

scanf("%s", str);

while (str[i] != '\0')

i++;

str[i] = '$';
str[++i] = '\0';
printf("%s\n", str);

come:
i = 0;
opstr[0] = '$';
j = 1;
c = '$';
swt();
col1 = col;
c = str[i];
swt();
col2 = col;
if (f[1][col1] > f[1][col2])
{
opstr[j] = '>';
j++;
}
else if (f[1][col1] < f[1][col2])
{
opstr[j] = '<';
j++;
}
else
{
opstr[j] = '=';
j++;
}

while (str[i] != '$')

{
c = str[i];
swt();
col1 = col;
c = str[++i];
swt();
col2 = col;

opstr[j] = str[--i];
j++;

if (f[0][col1] > f[1][col2])

{
opstr[j] = '>';
j++;
}
else if (f[0][col1] < f[1][col2])
{
opstr[j] = '<';
j++;
}
else
{
opstr[j] = '=';
j++;
}
i++;
}

opstr[j] = '$';
opstr[++j] = '\0';
printf("\nPrecedence Input:%s\n", opstr);

i = 0;
j = 0;

while (opstr[i] != '\0')

{
foundg = 0;

while (foundg != 1)
{
if (opstr[i] == '\0')
goto redone;

if (opstr[i] == '>')
foundg = 1;

t1 = i;
i++;
}

if (foundg == 1)
for (i = t1; i > 0; i--)
if (opstr[i] == '<')
break;

if (i == 0)
{
printf("\nERROR\n");
exit(1);
}

cn = i;
j = 0;
i = t1 + 1;

while (opstr[i] != '\0')

{
temp[j] = opstr[i];
j++;
i++;
}

temp[j] = '\0';
opstr[cn] = 'E';
opstr[++cn] = '\0';
strcat(opstr, temp);
 printf("\n%s", opstr);

i = 1;
}

redone:
k = 0;

while (opstr[k] != '$')

{
k++;

if (opstr[k] == '<')
{
printf("\nError");
exit(1);
}
}

if ((opstr[0] == '$') && (opstr[2] == '$'))

goto sue;

i = 1;

while (opstr[i] != '\0')

{
c = opstr[i];

if (c == '+' || c == '*' || c == '/' || c == '$')

{
temp[j] = c;
j++;
}

i++;
}

temp[j] = '\0';
strcpy(str, temp);
goto come;

sue:
printf("\nSuccess");
getch();
return 0;
}
Output:

Result:
Thus, the program has been executed successfully and Output is verified.
Ex. No: 06
Date: Implement Simple Code Optimization Techniques.

Aim:
To write a program for optimization of the given input code using constant folding
technique.

Algorithm:
1. Read the input code from a file.
2. Use fgetc() function to read the characters from the file.
3. Split those in to operators and operands.
4. Implement code optimization algorithm.
5. Print the result in the output file.

Program:
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
struct ConstFold
{
char new_Str[10];
char str[10];
} Opt_Data[20];

void ReadInput(char Buffer[], FILE *Out_file);

int Gen_token(char str[], char Tokens[][10]);
int New_Index = 0;

int main()
{
FILE *In_file, *Out_file;
char Buffer[100], ch;
int i = 0;
In_file = fopen("d :\\[Link]", "r");
Out_file = fopen("d :\\[Link]", "w");
// clrscr();
while (1)
{
ch = fgetc(In_file);
i = 0;
while (1)
 {
if (ch == "\n")
break;
Buffer[i++] = ch;
ch = fgetc(In_file);
if (ch == EOF)
break;
} // End while
if (ch == EOF)
break;
Buffer[i] = "\0";
ReadInput(Buffer, Out_file);
}
return 0;
}

void ReadInput(char Buffer[], FILE *Out_file)

{
char temp[100], Token[10][10];
int n, i, j, flag = 0;
strcpy(temp, Buffer);
n = Gen_token(temp, Token);
for (i = 0; i < n; i++)
{
if (!strcmp(Token[i], "="))
{
if (isdigit(Token[i + 1][0]) || Token[i + 1][0] == ".")
{
flag = 1;
strcpy(Opt_Data[New_Index].new_Str, Token[i - 1]);
strcpy(Opt_Data[New_Index++].str, Token[i + 1]);
}
}
}
if (!flag)
{
for (i = 0; i < New_Index; i++)
{
for (j = 0; j < n; j++)
{
if (!strcmp(Opt_Data[i].new_Str, Token[j]))
strcpy(Token[j], Opt_Data[i].str);
}
}
}
fflush(Out_file);
strcpy(temp, "");
for (i = 0; i < n; i++)
 {
strcat(temp, Token[i]);
if (Token[i + 1][0] != "," || Token[i + 1][0] != ",")
strcat(temp, " ");
}
strcat(temp, "\n\0");
fwrite(&temp, strlen(temp), 1, Out_file);
}

int Gen_Token(char str[], char Token[][10])

{
int i = 0;
int j = 0, k = 0;
while (str[k] != "\0")
{
j = 0;
while (str[k] == " " || str[k] == "\t")
k++;
while ((str[k]) != (" " && str[k] != "\0" && str[k] != "" = "" &&
str[k] != "/" && str[k] != "+" && str[k] != "-" && str[k] != "*‟" && str[k] !=
"," && str[k] != ";"))
Token[i][j++] = str[k++];
Token[i++][j] = "\0";
if (str[k] == "=" || str[k] == "/" || str[k] == "+" || str[k] == "-"
|| str[k] == "*" || str[k] == "*" || str[k] == "," || str[k] == ";")
{
Token[i][0] = str[k++];
Token[i++][1] = "\0";
}
if (str[k] == "\0")
break;
return i;
}
}
Output :
SAMPLE INPUT FILE : [Link]

#include main()
{
float pi=3.14,r,a;
a = pi*r*r;
printf(“a = %f”,a);
return 0;
}

OUTPUT FILE: [Link]

#include main()

{
float pi = 3.14, r, a;
a = 3.14 * r * r;
printf(“a = %f”,a);
return 0;
}

RESULT:
Thus, the program for code optimization was implemented, executed and verified.
Ex. No: 07
IMPLEMENTATION OF BACK END OF COMPILER.
Date:

Aim :
To implement the back end of the compiler which takes the three address code and
produces the 8086 assembly language instructions that can be assembled and run using a
8086assembly.

Algorithm:
1. Start the program.
2. Get the three variables from statements and stored in the text file [Link].
3. Compile the program and give the path of the source file.
4. Execute the program.
5. Target code for the given statement was produced.
6. Stop the program.

Program:
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <stdlib.h>
int main()
{
int i = 2, j = 0, k = 2, k1 = 0;
char ip[10], kk[10];
FILE *fp;
// clrscr();
printf("\nEnter the filename of the intermediate code: ");
scanf("%s", &kk);
fp = fopen(kk, "r");
if (fp == NULL)
{
printf("\nError in Opening the file");
getch();
}
//clrscr();
while (!feof(fp))
{
fscanf(fp, "%s\n", ip);
printf("\t\t%s\n", ip);
}
rewind(fp);
 printf("\n \n");
printf("\tStatement \t\t target code\n");
printf("\n \n");
while (!feof(fp))
{
fscanf(fp, "%s", ip);
printf("\t%s", ip);
printf("\t\tMOV %c,R%d\n\t", ip[i + k], j);
if (ip[i + 1] == '+')
printf("\t\tADD");
else
printf("\t\tSUB");
if (islower(ip[i]))
printf("%c,R%d\n\n", ip[i + k1], j);
else
printf("%c,%c\n", ip[i], ip[i + 2]);
j++;
k1 = 2;
k = 0;
}
printf("\n \n");
getch();
fclose(fp);
return 0;
}
Output:

Result:
Thus, the above the program is executed and the required output is obtained.
Ex. No: 08
Date: IMPLEMENTATION OF LR PARSER

Aim:
To write a C program to construct LR Parsing Table.

Algorithm:
1. Start the program.
2. Read the context free grammar.
3. Get the input from the user
4. Push into stack do step 5 to 7.
5. Otherwise goto step 8.
6. If the starting symbol of inp is terminal then shift it into stack by pushing top+=1.
7. Reduce the terminal as stack content by the production.
8. Goto step 4.
9. Stop the program.

Program:
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <string.h>

int ptab[12][10] = {{5, 0, 0, 4, 0, 0, 1, 2, 3}, {0, 6, 0, 0, 0, 100, 0, 0,

0}, {0, -2, 7, 0, -2, -2, 0, 0, 0}, {0, -4, -4, 0, -4, -4, 0, 0, 0}, {5, 0, 0,
4, 0, 0, 8, 2, 3}, {0, -6, -6, 0, -6, -6, 0, 0, 0}, {5, 0, 0, 4, 0, 0, 0, 9,
3}, {5, 0, 0, 4, 0, 0, 0, 0, 10}, {0, 6, 0, 0, 11, 0, 0, 0, 0}, {0, -1, 7, 0,
-1, -1, 0, 0, 0}, {0, -3, -3, 0, -3, -3, 0, 0, 0}, {0, -5, -5, 0, -5, -5, 0,
0, 0}};
char NT[8] = " EETTFF";
char prodn[7][10] = {"", "E+T", "T", "T*F", "F", "(E)", "i"};
int const IDR = 0, PLU = 1, AST = 2, OPS = 3, CPS = 4, DOL = 5, E = 6, T = 7,
F = 8;
char input[20], stack[20] = "0", tok[10], st[10], rel[20], in;
int top = 0, cur = 0, invalid = 0, sttop = 0, stlen = 0, reln, i = 0, j = 0;

int shift()
{
int i, j;
char ip[20];
sprintf(rel, "%c%d", input[0], reln);
strcat(stack, rel);
 if (reln >= 10)
top = strlen(stack) - 2;
else
top = strlen(stack) - 1;
for (i = 1, j = 0; i < strlen(input); i++, j++)
ip[j] = input[i];
ip[j] = '\0';
strcpy(input, ip);
printf("\t\t\t shift");
printf("\n %s \t\t\t %s", stack, input);
return 0;
}

int reduce()
{
int plen = 0, ntcount = 0;
char nt, ch, cat[10];
reln = reln * -1;
nt = NT[reln];
plen = strlen(prodn[reln]);
for (i = strlen(stack) - 1; i >= 0; i--)
{
ch = stack[i];
if (!(ch >= 48 && ch <= 57))
ntcount++;
if (ntcount == plen)
break;
}
stack[i] = '\0';
sprintf(cat, "%c", nt);
strcat(stack, cat);
get(0);
sprintf(cat, "%d", ptab[sttop][cur]);
strcat(stack, cat);
printf("\t\treduce%c->%s", NT[reln], prodn[reln]);
printf("\n%s\t\t\t%s", stack, input);
top = strlen(stack) - strlen(cat);
return 0;
}

int get(int ipflag)

{
int diff, l = 0, m = 0;
if (ipflag)
{
in = input[0];
stlen = strlen(stack);
if (stlen - 1 == top)
 sprintf(st, "%c", stack[top]);
else
{
for (l = top; l <= stlen; l++)
st[m++] = stack[l];
st[m] = '\0';
}
sttop = atoi(st);
}
else
{
in = stack[i];
sprintf(st, "%c", stack[i - 1]);
sttop = atoi(st);
}
switch (in)
{
case 'i':
cur = IDR;
break;
case '+':
cur = PLU;
break;
case '*':
cur = AST;
break;
case '(':
cur = OPS;
break;
case ')':
cur = CPS;
break;
case '$':
cur = DOL;
break;
case 'E':
cur = E;
break;
case 'T':
cur = T;
break;
case 'F':
cur = F;
break;
default:
printf("\n %d invalid input symbol", stack[top]);
invalid = 1;
break;
 }
return 0;
}

int main()
{
// clrscr();
printf("\n LR PARSER \n");
printf("\n given cfg");
for (i = 1; i < 7; i++)
{
printf("\n %c->%s", NT[i], prodn[i]);
}
printf("\n enter the input string: ");
scanf("%s", input);
printf("\n input:%s\n stack \t\t input \t\t\t action \n %s\t\t\t %s$",
input, stack, input);
strcat(input, "$");
while (!invalid)
{
stlen = strlen(stack);
get(1);
reln = ptab[sttop][cur];
if (reln > 0 && reln != 100)
shift();
else if (reln < 0)
reduce();
else if (reln == 100)
break;
else
invalid = 1;
}
if (invalid)
printf("\n rejected");
else
printf("\n accepted");
getch();
return 0;
}
Output:

RESULT:
Thus, the C program to implement L-R Parser is executed and verified successfully.