Aim - Generate parse trees using a context-free grammar in C and test with various inputs.
Source Code
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
typedef struct Node {
char data;
struct Node *left, *right;
} Node;
// Function to create a new parse tree node
Node* newNode(char data) {
Node *node = (Node*) malloc(sizeof(Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
char *input;
int pos = 0;
char lookahead;
// Forward declarations for the recursive functions
Node* E();
Node* T();
Node* F();
// Function to get the next token
void nextToken() {
lookahead = input[pos++];
}
// Function to match a specific character and move to the next token
void match(char expected) {
if (lookahead == expected) {
nextToken();
} else {
printf("Error: Expected '%c', but found '%c'\n", expected, lookahead);
exit(1);
}
}
// Recursive descent parsing function for E -> E + T | T
Node* E() {
Node *node = T(); // Parse T first
while (lookahead == '+') {
Node *new_node = newNode('+');
new_node->left = node;
match('+');
new_node->right = T();
node = new_node; // Continue building the tree for E
}
return node;
}
// Recursive descent parsing function for T -> T * F | F
Node* T() {
Node *node = F(); // Parse F first
while (lookahead == '*') {
Node *new_node = newNode('*');
new_node->left = node;
match('*');
new_node->right = F();
node = new_node; // Continue building the tree for T
}
return node;
}
// Recursive descent parsing function for F -> (E) | id
Node* F() {
Node *node;
if (lookahead == '(') {
match('(');
node = E(); // Parse the expression inside parentheses
match(')');
} else if (isalnum(lookahead)) {
node = newNode(lookahead); // Match id (a number or variable)
nextToken();
} else {
printf("Error: Unexpected token '%c'\n", lookahead);
exit(1);
}
return node;
}
// Function to print the parse tree in pre-order (root, left, right)
void printTree(Node *root, int level) {
if (root == NULL) return;
for (int i = 0; i < level; i++) printf(" ");
printf("%c\n", root->data);
printTree(root->left, level + 1);
printTree(root->right, level + 1);
}
int main() {
char inputBuffer[100];
// Get input from the user
printf("Enter an arithmetic expression (only +, *, parentheses, and single digits or
variables):\n");
scanf("%s", inputBuffer);
input = inputBuffer;
pos = 0;
nextToken(); // Initialize lookahead with the first character
Node *parseTree = E(); // Start parsing with E
if (lookahead == '\0') {
printf("Parse tree (Pre-order traversal):\n");
printTree(parseTree, 0); // Print the generated parse tree
} else {
printf("Error: Input not fully consumed, unexpected character '%c'\n", lookahead);
}
return 0;
}
Output1-
Enter an arithmetic expression (only +, *, parentheses, and single digits or variables):
a+b*c
Parse tree (Pre-order traversal):
+
a
*
b
c
Output2-
Enter an arithmetic expression (only +, *, parentheses, and single digits or variables):
d*e+f*g
Parse tree (Pre-order traversal):
+
*
d
e
*
f
g