Roll No:
EXERCISE – 6
Aim: Design Operator Precedence Parsing for the given language.
Description:
An operator precedence parser is a bottom-up parser that interprets an operator grammar. This parser is
only used for operator grammars. Ambiguous grammars are not allowed in any parser except operator
precedence parser. A grammar is said to be operator precedence grammar if it has two properties:
→ No R.H.S. of any production has a∈.
→ No two non-terminals are adjacent.
Operator precedence can only established between the terminals of the grammar. It ignores the non-
terminal.
There are the three operator precedence relations:
1. a ⋗ b means that terminal "a" has the higher precedence than terminal "b".
2. a ⋖ b means that terminal "a" has the lower precedence than terminal "b".
3. a ≐ b means that the terminal "a" and "b" both have same precedence.
Precedence table:
Parsing Action
→ Both end of the given input string, add the $ symbol.
→ Now scan the input string from left right until the ⋗ is encountered.
→ Scan towards left over all the equal precedence until the first left most ⋖ is encountered.
→ Everything between left most ⋖ and right most ⋗ is a handle.
→ $ on $ means parsing is successful.
Algorithm:
1. Push onto stack.
2. Read first input symbol and push it onto stack
3. Do
a. Obtain OP relation between the top terminal symbol on the stack and the next input symbol.
b. If the OP relation is <o or =o.
c. Then.
d. Stack input symbol.
e. Else { relation is >o }
24 | P a g e
Roll No:
f. Pop top of the stack into handle, include non-terminal symbol if appropriate.
g. Obtain the relation between the top terminal symbol on the stack and the leftmost terminal
symbol in the handle.
h. While the OP relation between terminal symbols is =o Do.
i. Pop top terminal symbol and associated non-terminal symbol on stack into handle.
j. Obtain the OP relation between the top terminal symbol on the stack and the leftmost
terminal symbol in the handle.
k. Match the handle against the RHS of all productions.
l. Push N onto the stack
4. Until end-of-file and only and N are on the stack
Note: The algorithm above does not detect any syntax errors which we will talk about later.
Program:
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
char *input;
int i=0;
char lasthandle[6],stack[50],handles[][5]={")E(","E*E","E+E","i","E^E"};
int top=0,l;
char prec[9][9]={
'>', '>','<','<','<','<','<','>','>', '>', '>','<','<','<','<','<','>','>', '>', '>','>','>', '<','<','<','>','>',
'>','>','>','>','<','<','<','>','>', '>', '>','>','>', '<','<','<', '>', '>','>', '>','>','>','>','e','e','>','>',
'<', '<', '<', '<','<','<','<','>','e', '>', '>','>', '>','>','e','e', '>','>', '<', '<','<','<','<','<','<','<','>',
};
int getindex(char c) {
switch(c) {
case '+':return 0;
case '-':return 1;
case '*':return 2;
case '/':return 3;
case '^':return 4;
case 'i':return 5;
case '(':return 6;
case ')':return 7;
case '$':return 8;
}
25 | P a g e
Roll No:
}
int shift() {
stack[++top]=*(input+i++);
stack[top+1]='\0';
}
int reduce() {
int i,len,found,t;
for(i=0;i<5;i++) {
len=strlen(handles[i]);
if(stack[top]==handles[i][0]&&top+1>=len) {
found=1;
for(t=0;t<len;t++) {
if(stack[top-t]!=handles[i][t]) {
found=0;
break;
}
}
if(found==1) {
stack[top-t+1]='E';
top=top-t+1;
strcpy(lasthandle,handles[i]);
stack[top+1]='\0';
return 1;
}
}
}
return 0;
}
void dispstack() {
int j;
for(j=0;j<=top;j++)
printf("%c",stack[j]);
}
void dispinput() {
26 | P a g e
Roll No:
int j;
for(j=i;j<l;j++)
printf("%c",*(input+j));
}
void main() {
int j;
input=(char*)malloc(50*sizeof(char));
printf("\nEnter the string:");
scanf("%s",input);
input=strcat(input,"$");
l=strlen(input);
strcpy(stack,"$");
printf("\nSTACK\tINPUT\tACTION");
while(i<=l) {
shift();
printf("\n");
dispstack();
printf("\t");
dispinput();
printf("\tShift");
if(prec[getindex(stack[top])][getindex(input[i])]=='>') {
while(reduce()) {
printf("\n");
dispstack();
printf("\t");
dispinput();
printf("\tReduced: E->%s",lasthandle);
}
}
}
if(strcmp(stack,"$E$")==0)
printf("\nAccepted;");
else
printf("\nNot Accepted;");
27 | P a g e
Roll No:
Output:
Enter the string: i*(i+i)*i
Stack Input Action
$i *(i+i)*i$ Shift
$E *(i+i)*i$ Reduced: E->i
$E* (i+i)*i$ Shift
$E*( i+i)*i$ Shift
$E*(i +i)*i$ Shift
$E*(E +i)*i$ Reduced: E->i
$E*(E+ i)*i$ Shift
$E*(E+i )*i$ Shift
$E*(E+E )*i$ Reduced: E->i
$E*(E )*i$ Reduced: E->E+E
$E*(E) *i$ Shift
$E*E *i$ Reduced: E->)E(
$E *i$ Reduced: E->E*E
$E* i$ Shift
$E*i $ Shift
$E*E $ Reduced: E->i
$E $ Reduced: E->E*E
$E$ Shift
$E$ Shift
Accepted
28 | P a g e
