202046704 Compiler Design
PRACTICAL 11
Implement a C program to implement operator precedence
parsing.
CODE:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#define MAX 100
char table[6][6] =
{
{ '>', '<', '<', '>', '<', '>' },
{ '>', '>', '<', '>', '<', '>' },
{ '<', '<', '<', '=', '<', ' ' },
{ '>', '>', ' ', '>', ' ', '>' },
{ '>', '>', ' ', '>', ' ', '>' },
{ '<', '<', '<', ' ', '<', ' ' }
};
char symbols[6] = { '+', '*', '(', ')', 'i', '$' };
char stack[MAX];
int top = -1;
void push(char c) { stack[++top] = c; }
char pop() { return stack[top--]; }
char peek() { return stack[top]; }
void printStackInput(char *input[], int i, int n)
{
printf("STACK: ");
12202040501041 Miti Bhatt
202046704 Compiler Design
for (int j = 0; j <= top; j++) printf("%c", stack[j]);
printf("\tINPUT: ");
for (int k = i; k < n; k++) printf("%s", input[k]);
printf("\n");
}
int getIndex(char c)
{
for (int i = 0; i < 6; i++)
if (symbols[i] == c) return i;
return -1;
}
int tokenize(char *expr, char *tokens[])
{
int n = 0;
int len = strlen(expr);
for (int i = 0; i < len; )
{
if (isspace(expr[i]))
{
i++;
continue;
}
if (expr[i] == 'i' && expr[i+1] == 'd')
{
tokens[n++] = "id";
i += 2;
}
else if (strchr("+*()$", expr[i]))
{
12202040501041 Miti Bhatt
202046704 Compiler Design
char *temp = (char*)malloc(2);
temp[0] = expr[i];
temp[1] = '\0';
tokens[n++] = temp;
i++;
}
else
{
printf("ERROR: invalid symbol '%c'\n", expr[i]);
return -1;
}
}
return n;
}
int main()
{
char expr[MAX];
printf("Enter expression (use id for identifier, end with $): ");
char *tokens[MAX];
int n = tokenize(expr, tokens);
if (n == -1) return 1;
push('$');
int i = 0;
printf("\nParsing Steps:\n");
printStackInput(tokens, i, n);
while (1)
{
int k = top;
12202040501041 Miti Bhatt
202046704 Compiler Design
while (k >= 0 && getIndex(stack[k]) == -1) k--;
char a = stack[k];
char *lookahead = tokens[i];
char b;
if (strcmp(lookahead, "id") == 0) b = 'i';
else b = lookahead[0];
if (a == '$' && b == '$')
{
printf("\nACCEPTED\n");
break;
}
int row = getIndex(a);
int col = getIndex(b);
if (row == -1 || col == -1)
{
printf("ERROR: invalid symbol\n");
break;
}
char relation = table[row][col];
if (relation == '<' || relation == '=')
{
push(b);
i++;
printf("Action: SHIFT\n");
printStackInput(tokens, i, n);
12202040501041 Miti Bhatt
202046704 Compiler Design
}
else if (relation == '>')
{
char topSymbol = pop();
if (topSymbol == 'i')
{
printf("Reduce: E → id\n");
push('E');
}
else if (topSymbol == 'E' && peek() == '+')
{
pop();
if (peek() == 'E')
{
pop();
printf("Reduce: E → E+E\n");
push('E');
}
}
else if (topSymbol == 'E' && peek() == '*')
{
pop();
if (peek() == 'E')
{
pop();
printf("Reduce: E → E*E\n");
push('E');
}
12202040501041 Miti Bhatt
202046704 Compiler Design
}
else if (topSymbol == ')' && peek() == 'E')
{
pop();
if (peek() == '(')
{
pop();
printf("Reduce: E → (E)\n");
push('E');
}
}
else
{
printf("ERROR: no valid reduction\n");
break;
}
printStackInput(tokens, i, n);
}
else
{
printf("ERROR: unexpected relation\n");
break;
}
}
return 0;
}
12202040501041 Miti Bhatt
202046704 Compiler Design
OUTPUT:
• Successful parsing
• Unsuccessful Parsing:
12202040501041 Miti Bhatt
