TABLE OF CONTENTS

S No. Practical Signature

1. Short Note on LEX tool.

2. Short Note on YACC Tool.

3. Program for Token separation with a given expression

4. Program to identify whether a given line is a comment or not

5. Program to check whether a given identifier is valid or not

6. Program to recognize strings under ‘a’, ‘a+b+’, ‘abb’

7. Program to simulate lexical analyser for validating operators

8. Program for implementation of Operator Precedence Parser

9. Program for implementation of LL (1) Parser

10. Program for implementation of LALR Parser

2
 PROGRAM-1
SHORT NOTE ON LEX TOOL
LEX
A lex is a tool used to generate a lexical analyzer.
The lexical analyzer is a program that transforms an input stream into a sequence of
tokens.
It reads the input stream and produces the source code as output through implementing
the lexical analyzer in the C program.
Creating a lexical analyzer with LEX

Function of LEX

• Firstly lexical analyzer creates a program lex.1 in the Lex language. Then Lex
compiler runs the lex.1 program and produces a C program [Link].c.
• Finally C compiler runs the [Link].c program and produces an object program
[Link].
• [Link] is lexical analyzer that transforms an input stream into a sequence of
tokens.

Structure of LEX Programs

3
• Declarations:
This are instructions for the C compiler.
They are used for include header files, defining global variables and constants
and declaration of functions.
They consist of two parts, auxiliary declarations and regular definitions.
They are not processed by the lex tool instead are copied by the lex to the
output file [Link].c file.
Auxiliary declarations are written in C and enclosed with ‘%{‘ and ‘%}’.
• Transformation Rules:
These consist of regular expressions(patterns to be matched) and code
segments(corresponding code to be executed).
• Auxiliary functions:
After C code is generated for the rules specified in the previous section, this
code is placed into a function called yylex().
These functions are compiled separately and loaded with lexical analyzer.
Declarations and functions are then copied to the [Link].c file which is
compiled using the command gcc [Link].c.

4
 PROGRAM-2
SHORT NOTE ON YACC TOOL
YACC
YACC stands for Yet Another Compiler Compiler.
YACC provides a tool to produce a parser for a given grammar.
YACC is a program designed to compile a LALR (1) grammar.
It is used to produce the source code of the syntactic analyzer of the language
produced by LALR (1) grammar.
The input of YACC is the rule or grammar and the output is a C program.
Input: A CFG- file.y
Output: A parser [Link].c (yacc)
The output file “[Link]” contains the parsing tables.
The file “[Link].h” contains declarations.
The parser called the yyparse ().
Parser expects to use a function called yylex () to get tokens.
Basic operational sequence:
This file contains the desired grammar in YACC format.
It shows the YACC program.
It is the c source program created by YACC.
C Compiler
Executable file that will parse grammar given in gram.Y

5
 PROGRAM-3
PROGRAM FOR TOKEN SEPARATION WITH A GIVEN
EXPRESSION

#include <stdbool.h>
#include <stdio.h>
#include <string.h>

#include <stdlib.h>
// Returns 'true' if the character is a DELIMITER.
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);
}

// Returns 'true' if the character is an OPERATOR.

bool isOperator(char ch)
{
if (ch == '+' || ch == '-' || ch == '*' ||
ch == '/' || ch == '>' || ch == '<' ||
ch == '=')

return (true);

return (false);
}

6
// Returns 'true' if the string is a VALID IDENTIFIER.
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);
}
// Returns 'true' if the string is a KEYWORD.

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); }
// Returns 'true' if the string is an INTEGER.
bool isInteger(char* str)

7
{
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);
}

// Returns 'true' if the string is a REAL NUMBER.

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;

8
 }
return (hasDecimal);

}
// Extracts the SUBSTRING.
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);

}
// Parsing the input STRING.
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

9
 || (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;

}
// DRIVER FUNCTION

int main()
{
// maximum length of string is 100 here

char str[100] = "int a = b + 1c; "; parse(str);

// calling the parse function

return (0);
}

Output:
'int' IS A KEYWORD

10
'a' IS A VALID IDENTIFIER '=' IS
AN OPERATOR
'b' IS A VALID IDENTIFIER
'+' IS AN OPERATOR
'1c' IS NOT A VALID IDENTIFIER

11
 PROGRAM-4
PROGRAM TO IDENTIFY WHETHER A GIVEN LINE IS
A COMMENT OR NOT
#include<stdio.h>
#include<conio.h
> void main() {
char com[30];
int i=2,a=0;

clrscr();
printf("\n Enter comment:"); gets(com);
if(com[0]=='/') { if(com[1]=='/')
printf("\n It is a comment"); else
if(com[1]=='*') {
for(i=2;i<=30;i++) {
if(com[i]=='*'&&com[i+1]=='/')
{ printf("\n It is a comment");
a=1; break;
}
else
continue;
}
if(a==0) printf("\n It is not a
comment");
}

else printf("\n It is not a

comment"); }

else printf("\n It is not a

comment"); getch();

12
}

Output:
Input: Enter comment: //hello
Output: It is a comment
Input: Enter comment: hello

Output: It is not a comment

13
 PROGRAM-5
PROGRAM TO TEST WHETHER A GIVEN IDENTIFIER IS
VALID OR NOT
#include<stdio.h>
#include<conio.h
>
#include<ctype.h
>
void main(){ char
a[10];
int flag, i=1; clrscr(); printf("\n
Enter an identifier:"); gets(a);
if(isalpha(a[0])) flag=1; else
printf("\n Not a valid identifier");
while(a[i]!='\0'){
if(!isdigit(a[i])&&!isalpha(a[i]))
{ flag=0; break; } i++;}
if(flag==1) printf("\n Valid
identifier"); getch();}

Output:
Enter an identifier: first
Valid identifier
Enter an identifier:1aqw
Not a valid identifier

14
 PROGRAM-6
PROGRAM TO RECOGNIZE STRINGS UNDER 'A', 'A*B+',
'ABB'
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
void main()
{
char s[20],c;
int state=0,i=0;
clrscr(); printf("\n Enter a
string:"); gets(s);
while(s[i]!='\0')
{
switch(state) {
case 0:
c=s[i++];
if(c=='a')
state=1; else
if(c=='b')
state=2; else
state=6; break;
case 1:
c=s[i++];
if(c=='a')
state=3; else
if(c=='b')
state=4;

15
else state=6;
break; case 2:
c=s[i++];
if(c=='a')
state=6; else
if(c=='b')
state=2; else
state=6; break;
case 3:
c=s[i++];
if(c=='a')
state=3; else
if(c=='b')
state=2; else
state=6; break;
case 4:
c=s[i++];
if(c=='a')
state=6; else
if(c=='b')
state=5; else
state=6; break;
case 5:
c=s[i++];
if(c=='a')
state=6; else
if(c=='b')
state=2; else
state=6; break;

16
case 6:
printf("\n %s is
not
recognised.",s);
exit(0);
}}
if(state==1) printf("\n %s is accepted under
rule 'a'",s); else if((state==2)||(state==4))
printf("\n %s is accepted under rule
'a*b+'",s); else if(state==5) printf("\n %s is
accepted under rule 'abb'",s); getch();
}

Output:
Enter a String: aaaabbbbb aaaabbbbb is
accepted under rule 'a*b+' Enter a
string: cdgs cdgs is not recognized

17
 PROGRAM-7
PROGRAM TO SIMULATE LEXICAL ANALYSER FOR
VALIDATING OPERATORS
#include<stdio.h>
#include<conio.h
> void main(){
char s[5]; clrscr();
printf("\n Enter any operator:");
gets(s); switch(s[0]){ case'>':
if(s[1]=='=') printf("\n Greater
than or equal"); else printf("\n
Greater than"); break;
case'<': if(s[1]=='=') printf("\n
Less than or equal"); else
printf("\nLess than"); break;
case'=': if(s[1]=='=')
printf("\nEqual to");
else
printf("\nAssignment");
break;
case'!': if(s[1]=='=')
printf("\nNot Equal");
else

printf("\n Bit Not");

break; case'&':
if(s[1]=='&')
printf("\nLogical

18
AND"); else printf("\n
Bitwise AND"); break;
case'|': if(s[1]=='|') printf("\nLogical
OR"); else printf("\nBitwise OR");
break; case'+': printf("\n Addition");
break; case'-':
printf("\nSubstraction"); break;
case'*': printf("\nMultiplication");
break; case'/': printf("\nDivision");
break; case'%': printf("Modulus");
break; default: printf("\n Not a
operator"); } getch();
}

Output:
Enter any operator: *
Multiplication

19
 PROGRAM-8
PROGRAM TO IMPLEMENT OPERATOR PRECEDENCE
PARSER
#include<stdio.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; 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 MISSMATCH\n");
exit(1);

break;
}
// return 0;
}

main() { int
i=0,j=0,col1,cn,k=0;
int t1=0,foundg=0;
char temp[20];
clrscr();
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]='$';

20
j=1; c='$';
swt();
col1=col;
c=str[i]; swt();
col2=col;
if(f[1][col1]>f[2][col2]
) { opstr[j]='>'; j++;
}
else
if(f[1][col1]<f[2][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++;

21
}
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';

22
strcat(opstr,temp);
printf("\n%s",opstr);
i=1;
}
redone:k=0;

while(opstr[k]!='\0')
{ 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("\n
success"); return 0;
}

Output:
Enter the arithmetic expression
(d*d)+d$

(d*d)+d$
Precedence input:$<(<d>*<d>)>+<d>$

23
$<(E*<d>)>+<d>$
$<(E*E)>+<E>$

$E+<E>$
$E+E$
Precedence input:$<+>$

$E$
Success

24
 PROGRAM-9
PROGRAM FOR IMPLEMENTATION OF LL(1) PARSER
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
char s[20],stack[20];
void main()
{
char m[5][6][3]={"tb"," "," ","tb"," "," "," ","+tb"," "," ","n","n","fc"," "," ","fc"," "," ","
","n","*fc"," a ","n","n","i"," "," ","(e)"," "," "}; int
size[5][6]={2,0,0,2,0,0,0,3,0,0,1,1,2,0,0,2,0,0,0,1,3,0,1,1,1,0,0,3,0,0};
int i,j,k,n,str1,str2; clrscr();
printf("\n Enter the input string: ");
scanf("%s",s); strcat(s,"$");
n=strlen(s); stack[0]='$';
stack[1]='e'; i=1; j=0;
printf("\nStack Input\n");
printf("__________________\n");

while((stack[i]!='$')&&(s[j]!='$'))
{
if(stack[i]==s[j])
{ i--
;
j++
;

}
switch(stack[i])
{

25
case 'e': str1=0;
break; case 'b':
str1=1; break;
case 't': str1=2;
break; case 'c':
str1=3; break;
case 'f': str1=4; break;
}
switch(s[j])

{
case 'i': str2=0;
break; case '+':
str2=1; break;
case '*': str2=2;
break;
case '(': str2=3; break;
case ')': str2=4;
break; case '$':
str2=5; break;

}
if(m[str1][str2][0]=='\0')
{
printf("\nERROR");

exit(0);
}
else if(m[str1][str2][0]=='n')
i--;

26
else
if(m[str1][str2][0]=='i')
stack[i]='i'; else
{
for(k=size[str1][str2]-1;k>=0;k--)
{
stack[i]=m[str1][str2][k];
i++;
} i--
;
}
for(k=0;k<=i;k++)
printf(" %c",stack[k]);
printf(" ");
for(k=j;k<=n;k++)
printf("%c",s[k]);
printf(" \n ");
}

printf("\n SUCCESS");
getch();
}

Output:
Enter the input string:i*i+i

Stack INPUT
$bt i*i+i$
$bcf i*i+i$
$bci i*i+i$

27
$bc *i+i$
$bcf* *i+i$
$bcf i+i$
$bci i+i$
$bc +i$
$b +i$
$bt+ +i$
$bt i$
$bcf i$
$ bci i$
$bc $
$b $
$ $

success

28
 PROGRAM-10
PROGRAM FOR IMPLEMENTATION LALR PARSER
/*LALR PARSER
E->E+T E-
>T
T->T*F
T->F

F->(E)
F->i
*/
#include<stdio.h>

#include<conio.h>
#include<stdlib.h>
#include<string.h> void
push(char *,int *,char);
char stacktop(char *); void
isproduct(char,char);
int ister(char); int isnter(char); int
isstate(char); void error(); void
isreduce(char,char); char
pop(char *,int *); void printt(char
*,int *,char [],int); void rep(char
[],int); struct action{ char
row[6][5]; }; const struct action
A[12]={
{"sf","emp","emp","se","emp","emp"},
{"emp","sg","emp","emp","emp","acc"},

{"emp","rc","sh","emp","rc","rc"},

29
{"emp","re","re","emp","re","re"},
{"sf","emp","emp","se","emp","emp"},

{"emp","rg","rg","emp","rg","rg"},
{"sf","emp","emp","se","emp","emp"},
{"sf","emp","emp","se","emp","emp"},

{"emp","sg","emp","emp","sl","emp"},
{"emp","rb","sh","emp","rb","rb"
},
{"emp","rb","rd","emp","rd","rd"
},
{"emp","rf","rf","emp","rf","rf"}
}; struct gotol{ char r[3][4]; };
const struct gotol G[12]={
{"b","c","d"},
{"emp","emp","emp"},
{"emp","emp","emp"},

{"emp","emp","emp"},
{"i","c","d"},
{"emp","emp","emp"},

{"emp","j","d"},
{"emp","emp","k"},
{"emp","emp","emp"},
{"emp","emp","emp"}, };

char ter[6]={'i','+','*',')','(','$'}; char

nter[3]={'E','T','F'}; char
states[12]={'a','b','c','d','e','f','g','h','m','j','k','l'};
char stack[100];
int top=-1;

30
char temp[10]; struct
grammar {
char left; char
right[5];
};
const struct grammar rl[6]={
{'E',"e+T"},
{'E',"T"},

{'T',"T*F"},
{'T',"F"},
{'F',"(E)"},
{'F',"i"}, };
void main() { char
inp[80],x,p,dl[80],y,bl='a'; int
i=0,j,k,l,n,m,c,len; clrscr();
printf(" Enter the input :");
scanf("%s",inp);
len=strlen(inp); inp[len]='$';
inp[len+1]='\0';
push(stack,&top,bl);
printf("\n stack \t\t\t input");
printt(stack,&top,inp,i); do {
x=inp[i];
p=stacktop(stack);
isproduct(x,p);
if(strcmp(temp,"emp")==0)
error();

31
if(strcmp(temp,"acc")==0)

break;
else { if(temp[0]=='s') {
push(stack,&top,inp[i]);
push(stack,&top,temp[1])
;
i++; } else {
if(temp[0]=='r') {
j=isstate(temp[1]);
strcpy(temp,rl[j-
2].right); dl[0]=rl[j-
2].left; dl[1]='\0';
n=strlen(temp);
for(k=0;k<2*n;k++)
pop(stack,&top);
for(m=0;dl[m]!='\0';m+
+)
push(stack,&top,dl[m]);
l=top; y=stack[l-1];
isreduce(y,dl[0]);
for(m=0;temp[m]!='\0';m++)
push(stack,&top,temp[m]); } } }
printt(stack,&top,inp,i);
}
while(inp[i]!='\0');

if(strcmp(temp,"acc")==0)
printf(" \n accept the input ");
else printf(" \n do not accept the
input "); getch();

32
}
void push(char *s,int *sp,char item) {
if(*sp==100)
printf(" stack is full
"); else { *sp=*sp+1;
s[*sp]=item; } } char
stacktop(char *s){
char i;
i=s[top];
return i; }
void isproduct(char x,char p) {
int k,l;
k=ister(x); l=isstate(p);
strcpy(temp,A[l-1].row[k-
1]);
}
int ister(char x) {
int i;

for(i=0;i<6;i++)
if(x==ter[i])
return i+1; return
0; } int
isnter(char x) {
int i;
for(i=0;i<3;i++)
if(x==nter[i])

return i+1; return

0;
}

33
int isstate(char p) {
int i;

for(i=0;i<12;i++)
if(p==states[i])
return i+1; return
0;
}
void error() { printf(" error
in the input "); exit(0);
}

void isreduce(char x,char p) {

int k,l;
k=isstate(x); l=isnter(p);
strcpy(temp,G[k-1].r[l-1]);
} char pop(char *s,int *sp)
{ char item; if(*sp==-1)
printf(" stack is empty ");
else {
item=s[*sp]; *sp=*sp-1; } return item; }
void printt(char *t,int *p,char inp[],int i)
{ int r;

printf("\n");
for(r=0;r<=*p;r++)

rep(t,r); printf("\t\t\t");
for(r=i;inp[r]!='\0';r++)
printf("%c",inp[r]);
}

34
void rep(char t[],int r)
{ char c; c=t[r];
switch(c) { case 'a':
printf("0"); break;
case 'b': printf("1");
break;
case 'c': printf("2");
break;
case 'd': printf("3");
break;
case 'e': printf("4"); break;
case 'f': printf("5");

break;
case 'g': printf("6");
break;
case 'h': printf("7");
break; case 'm':
printf("8"); break;

case 'j': printf("9");

break; case 'k':
printf("10"); break;
case 'l': printf("11");
break; default
:printf("%c",t[r]); break;
}

Output:
Enter the input: i*i+1

35
Stack input

0
i*i+i$
0i5
*i+i$
0F3
*i+i$
0T2
*i+i$
0T2*7
i+i$
0T2*7i5 +i$
0T2*7i5F10 +i$
0T2 +i$
0E1 +i$
0E1+6 i$
0E1+6i5 $
0E1+6F3 $
0E1+6T9 $
0E1 $
accept the input*/

36