Experiment-7
Operator Precedence Parser
Objective:
To develop an Operator Precedence Parser for a given language.
Concept:
1. Operator Precedence Parsing is a bottom-up parsing technique.
2. It uses operator precedence relations (<, >, =) to decide parsing actions.
3. Parsing Table is created using precedence relations.
Algorithm:
1. Construct the operator precedence table.
2. Read input expression symbol by symbol.
3. Use stack operations based on precedence relations.
4. Reduce until the expression is fully parsed.
Implementation in C:
#include <stdio.h>
#include <string.h>
char precedence[5][5] = {
{'>', '>', '<', '<', '>'},
{'>', '>', '<', '<', '>'},
{'>', '>', '>', '>', '>'},
{'<', '<', '<', '<', '='},
{'>', '>', '>', '>', '>'}
};
char symbols[] = {'+', '-', '*', '/', 'i'};
int getIndex(char ch) {
for (int i = 0; i < 5; i++)
if (symbols[i] == ch) return i;
return -1;
}
void parse(char *input) {
char stack[20] = "$";
int top = 1, i = 0;
printf("\nParsing Steps:\n");
while (i < strlen(input)) {
char topSymbol = stack[top - 1];
char currSymbol = input[i];
int row = getIndex(topSymbol);
int col = getIndex(currSymbol);
if (row == -1 || col == -1) {
printf("Invalid Expression!\n");
return;
}
if (precedence[row][col] == '<' || precedence[row][col] == '=') {
stack[top++] = currSymbol;
i++;
} else {
while (precedence[getIndex(stack[top - 2])][col] == '>') {
top--;
}
}
printf("Stack: %s, Input: %s\n", stack, input + i);
}
}
int main() {
char input[20];
printf("Enter expression: ");
scanf("%s", input);
parse(input);
return 0;
}
Experiment-8
Simulate First and Follow of a Grammar
Objective:
To compute First and Follow sets for a given grammar.
Concept:
1. First Set: Contains terminals that appear first in derivations.
2. Follow Set: Contains terminals that can appear immediately after a non-terminal.
Algorithm:
1. Compute First set:
o If terminal, add to First.
o If non-terminal, recursively compute First.
2. Compute Follow set:
o Start with $ for the start symbol.
o Use production rules to determine Follow.
Implementation in C:
c
CopyEdit
#include <stdio.h>
#include <string.h>
#define MAX 10
char productions[MAX][MAX];
char first[MAX][MAX];
char follow[MAX][MAX];
int numProductions;
void computeFirst(char symbol, char *result) {
for (int i = 0; i < numProductions; i++) {
if (productions[i][0] == symbol) {
if (!isupper(productions[i][2])) {
strncat(result, &productions[i][2], 1);
} else {
computeFirst(productions[i][2], result);
}
}
}
}
void computeFollow(char symbol, char *result) {
if (symbol == productions[0][0]) {
strcat(result, "$");
}
for (int i = 0; i < numProductions; i++) {
for (int j = 2; j < strlen(productions[i]); j++) {
if (productions[i][j] == symbol) {
if (productions[i][j + 1] != '\0') {
char temp[MAX] = "";
computeFirst(productions[i][j + 1], temp);
strcat(result, temp);
} else {
computeFollow(productions[i][0], result);
}
}
}
}
}
int main() {
printf("Enter number of productions: ");
scanf("%d", &numProductions);
printf("Enter productions (E->T+E format):\n");
for (int i = 0; i < numProductions; i++)
scanf("%s", productions[i]);
char firstSet[MAX] = "", followSet[MAX] = "";
computeFirst(productions[0][0], firstSet);
computeFollow(productions[0][0], followSet);
printf("\nFirst(%c) = {%s}\n", productions[0][0], firstSet);
printf("Follow(%c) = {%s}\n", productions[0][0], followSet);
return 0;
}
