ALGORITHM:
- Get the input expression and store it in the input buffer.
- Read the data from the input buffer one at the time and convert in to corresponding Non Terminal using production rules available.
- Perform push & pop operation for LR parsing table construction.
- Display the result with conversion of corresponding input symbols to production and production reduction to start symbol. No operation performed on the operator.
Algorithm Explanation:
Input Expression:
- The algorithm begins by getting the input expression from the user and storing it in an input buffer. This is typically a string representing a mathematical or logical expression.
Reading Input:
- It reads the data from the input buffer character by character. For each character, it attempts to convert it into a corresponding non-terminal using production rules.
Push & Pop Operations:
- The algorithm performs push and pop operations on a stack to manage the current state of the parsing process. This stack helps in managing the order of operations and productions applied during parsing.
Display Result:
- Finally, the result is displayed, showing how the input symbols have been converted to productions and how reductions have occurred to derive the start symbol of the grammar. Note that operators do not perform any specific operations in this parsing process.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char stack[30];
int top = -1;
void push(char c) {
top++;
stack[top] = c;
}
char pop() {
char c;
if (top != -1) {
c = stack[top];
top--;
return c;
}
return 'x'; // Return 'x' if the stack is empty
}
void printstat() {
int i;
printf("\n\t\t\t $");
for (i = 0; i <= top; i++)
printf("%c", stack[i]);
}
void main() {
int i, j, l;
char s1[20], ch1, ch2, ch3;
printf("\n\n\t\t LR PARSING");
printf("\n\t\t ENTER THE EXPRESSION: ");
scanf("%s", s1);
l = strlen(s1);
printf("\n\t\t $");
for (i = 0; i < l; i++) {
if (s1[i] == 'i' && s1[i + 1] == 'd') { // Assume 'id' is a terminal
s1[i] = ' '; // Replace 'id' with a space
s1[i + 1] = 'E'; // Map 'id' to non-terminal 'E'
printstat();
printf(" id");
push('E'); // Push non-terminal onto the stack
printstat();
} else if (s1[i] == '+' || s1[i] == '-' || s1[i] == '*' || s1[i] == '/') {
push(s1[i]); // Push operator onto the stack
printstat();
}
}
printstat();
// Process the stack until it's empty
while (top >= 0) {
ch1 = pop();
if (ch1 == 'x') { // If the stack is empty
printf("\n\t\t\t $");
break;
}
if (ch1 == '+' || ch1 == '/' || ch1 == '*' || ch1 == '-') {
ch3 = pop();
if (ch3 != 'E') { // Check if the top of the stack is 'E'
printf("error");
exit(1);
} else {
push('E'); // If 'E' is found, push it back
printstat();
}
}
ch2 = ch1; // Assign for future operations
}
getch(); // Wait for user input before closing
}
Key Components:
Stack Operations:
- The stack is implemented using an array, where
pushandpopfunctions manage the stack operations. Thetopvariable tracks the current top of the stack.
- The stack is implemented using an array, where
Input Handling:
- The program accepts an expression from the user. It specifically looks for the sequence “id” to represent an identifier and maps it to a non-terminal ‘E’.
Production Rules:
- The program checks for operators (‘+’, ‘-‘, ‘*’, ‘/’) and applies rules as needed. If a valid sequence is found (like an operator followed by ‘E’), it processes it accordingly.
Error Handling:
- Basic error handling is implemented; if the expected non-terminal isn’t found when processing an operator, it prints “error” and exits.
Display Function:
- The
printstatfunction visually represents the contents of the stack, helping to understand the state of parsing at various stages.
- The
OUTPUT: LR PARSING ENTER THE EXPRESSION id+id*id-id $ $id $E $E+ $E+id $E+E $E+E* $E+E*id $E+E*E $E+E*E- $E+E*E-id $E+E*E-E $E+E*E-E $E+E*E $E $
