Construct a recursive descent parser for an
expression
#include<stdio.h>
#include<string.h>
#include<ctype.h>
char input[100];
int i = 0, error = 0;
void E();
void Eprime();
void T();
void Tprime();
void F();
void E() {
// E → T E'
T();
Eprime();
}
void Eprime() {
// E' → + T E' | ε
if (input[i] == '+') {
i++;
T();
Eprime();
}
}
void T() {
// T → F T'
F();
Tprime();
}
void Tprime() {
// T' → * F T' | ε
if (input[i] == '*') {
i++;
F();
Tprime();
}
}
void F() {
// F → ( E ) | id
if (input[i] == '(') {
i++;
E();
if (input[i] == ')')
i++;
else
error = 1;
} else if (isalpha(input[i])) { // Handling identifiers (like variables)
i++;
while (isalnum(input[i]) || input[i] == '_') {
i++;
}
} else {
error = 1; // Error if it's not a valid factor (like an identifier or expression)
}
}
int main() {
printf("Enter an arithmetic expression: \n");
// Using fgets instead of gets
fgets(input, sizeof(input), stdin);
// Removing trailing newline character from fgets input if present
size_t len = strlen(input);
if (len > 0 && input[len - 1] == '\n') {
input[len - 1] = '\0';
}
E(); // Start the parsing process with E (Expression)
if (strlen(input) == i && error == 0) {
printf("\nAccepted..!!!\n");
} else {
printf("\nRejected..!!!\n");
}
return 0;
}
Output
➢ Enter an arithmetic expression:
a+(b*c
Rejected..!!!
➢ Enter an arithmetic expression:
(a+b)*c
Accepted..!!!
➢ Enter an arithmetic expression:
a+b*
Rejected..!!!
Construct a Shift Reduce Parser for a given language.
#include <stdio.h>
#include <string.h>
char input[16], stack[15];
int top = -1, i = 0;
void shift();
void reduce();
int main() {
printf("Enter input string (e.g., id+id*id): ");
fgets(input, sizeof(input), stdin);
// Remove trailing newline
size_t len = strlen(input);
if (len > 0 && input[len - 1] == '\n') input[len - 1] = '\0';
printf("\nStack\tInput\tAction\n");
while (i < strlen(input)) {
shift(); // Shift each symbol onto the stack
reduce(); // Try to reduce if possible
}
return 0;
}
void shift() {
stack[++top] = input[i++]; // Shift input to stack
stack[top + 1] = '\0'; // Null-terminate stack string
printf("$%s\t%s$\tShift\n", stack, input + i);
}
void reduce() {
// Reduce 'id' to 'E'
if (top >= 1 && stack[top - 1] == 'i' && stack[top] == 'd') {
top -= 1; // Pop 'id'
stack[top] = 'E'; // Replace with 'E'
stack[top + 1] = '\0'; // Null-terminate stack string
printf("$%s\t%s$\tReduce id to E\n", stack, input + i);
}
// Reduce 'E+E' or 'E*E' to 'E'
if (top >= 2 && stack[top - 2] == 'E' && (stack[top - 1] == '+'
|| stack[top - 1] == '*') && stack[top] == 'E') {
top -= 2; // Pop 'E+E' or 'E*E'
stack[top] = 'E'; // Replace with 'E'
stack[top + 1] = '\0'; // Null-terminate stack string
printf("$%s\t%s$\tReduce E%cE to E\n", stack, input + i,
stack[top + 1]);
}
// Reduce '(E)' to 'E'
if (top >= 2 && stack[top - 2] == '(' && stack[top - 1] == 'E'
&& stack[top] == ')') {
top -= 2; // Pop '(E)'
stack[top] = 'E'; // Replace with 'E'
stack[top + 1] = '\0'; // Null-terminate stack string
printf("$%s\t%s$\tReduce (E) to E\n", stack, input + i);
}
}
OUTPUT
enter input string (e.g., id+id*id): id+id
