Experiment-5

Aim:- Construct a Shift Reduce Parser for given production rule

E→ E+E
E→ E*E
E→ id

Theory:-A shift-reduce parser is a type of bottom-up parser used in compiler design to analyze the
syntax of programming languages. It attempts to construct a parse tree for an input string by using a
stack and following a set of grammar rules in reverse (from right to left).

Code:-

#include <stdio.h>
#include <string.h>

int isAccepted(const char* input) {

char stack[100];
int top = -1;
int i = 0;
char temp[3];

while (input[i] != '\0') {

// Shift one character
stack[++top] = input[i++];

// Try to reduce
while (top >= 1 && stack[top - 1] == 'i' && stack[top] == 'd') {
top--; // remove 'd'
stack[top] = 'E'; // replace 'i' with 'E'
}

while (top >= 2 && stack[top] == 'E' &&

(stack[top - 1] == '+' || stack[top - 1] == '*') &&
stack[top - 2] == 'E') {
top -= 2;
stack[top] = 'E';
}
}

// Final reduction
while (top >= 2 && stack[top] == 'E' &&
(stack[top - 1] == '+' || stack[top - 1] == '*') &&
stack[top - 2] == 'E') {
top -= 2;
 stack[top] = 'E';
}

return (top == 0 && stack[0] == 'E');

}

int main() {
char input[100];
printf("Enter input string=" );
scanf("%s", input);

if (isAccepted(input)) {
printf("String is accepted.\n");
} else {
printf("String is not accepted.\n");
}

return 0;
}

Output :-
 EXPERIMENT NO.- 6

Aim: Implementation of an Operator Precedence Parser for a given Language .

PROCEDURE:

 Let the input string to be initially the stack contains, when the reduce action takes place, we
have to reach create parent child relationship.
 See IP to pointer to the first symbol of input string and repeat forever if only $ is on the input
accept and break else begin.
 Let 'd’ be the top most terminal on the stack and 'b' be current input IF(ab)
 Repeat pop the stack until the top most terminal is related by < to the terminal most recently
popped else error value routine end.

CODE:
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>

// Precedence table
char q[9][9] = {
{'>', '>', '<', '<', '<', '<', '>', '<', '>'}, // +
{'>', '>', '<', '<', '<', '<', '>', '<', '>'}, // -
{'>', '>', '>', '>', '<', '<', '>', '<', '>'}, // *
{'>', '>', '>', '>', '<', '<', '>', '<', '>'}, // /
{'>', '>', '<', '<', '<', '<', '>', '<', '>'}, // ^
{'<', '<', '<', '<', '<', '<', '=', '<', 'E'}, // (
{'>', '>', '>', '>', '>', 'E', '>', 'E', '>'}, // )
{'>', '>', '>', '>', '>', 'E', '>', 'E', '>'}, // a (operand)
{'<', '<', '<', '<', '<', '<', 'E', '<', 'A'} // $
};

char st[30], qs[30];

int top = -1, r = -1, p = 0;

// Push function
void push(char a) {
top++;
st[top] = a;
}

// Pop function
char pop() {
char a = st[top];
top--;
return a;
}

// Find index in precedence table

int find(char a) {
switch (a) {
case '+': return 0;
case '-': return 1;
case '*': return 2;
case '/': return 3;
case '^': return 4;
case '(': return 5;
case ')': return 6;
case 'a': return 7;
case '$': return 8;
default: return -1;
}
}

// Display shift action

void display(char a) {
printf("\n Shift %c", a);
}

// Display reduce action

void display1(char a) {
if (isalpha(a))
printf("\n Reduce E -> %c", a);
else if ((a == '+') || (a == '-') || (a == '*') || (a == '/') || (a == '^'))
printf("\n Reduce E -> E %c E", a);
else if (a == ')')
printf("\n Reduce E -> ( E )");
}

// Precedence relation check

int rel(char a, char b, char d) {
if (isalpha(a) != 0)
a = 'a';
if (isalpha(b) != 0)
b = 'a';

if (q[find(a)][find(b)] == d)
return 1;
else
return 0;
}

// Main function
void main() {
char s[100];
 int i = -1;

clrscr();

printf("\n\tOperator Precedence Parser\n");

printf("\nEnter the Arithmetic Expression ending with $: ");
gets(s);

push('$');

while (1) {
if ((s[p] == '$') && (st[top] == '$')) {
printf("\n\nAccepted");
break;
} else if (rel(st[top], s[p], '<') || rel(st[top], s[p], '=')) {
display(s[p]);
push(s[p]);
p++;
} else if (rel(st[top], s[p], '>')) {
do {
r++;
qs[r] = pop();
display1(qs[r]);
} while (!rel(st[top], qs[r], '<'));
} else {
printf("\n\nError: Invalid expression.");
break;
}
}

getch();
}

OUTPUT:
Enter the Arithmetic Expression End with $: a-(b*c)^d$

Shift a
Reduce E -> a

Shift -
Shift (
Shift b
Reduce E -> b

Shift *
Shift c
Reduce E -> c
Reduce E -> E * E

Shift )
Reduce E -> ( E )

Shift ^
Shift d
Reduce E -> d
Reduce E -> E ^ E

Reduce E -> E - E

Accepted
 EXPERIMENT NO.- 7

AIM: Write program to find Simulate First and Follow of any given grammar.

Thoery:

• FIRST of a non-terminal is the set of terminals that begin the strings derivable from that non-
terminal.
• FOLLOW of a non-terminal is the set of terminals that can appear immediately to the right of
that non-terminal in some sentential form.
• These sets are used in the construction of LL(1) parsers to make parsing decisions.
• The FIRST set helps predict which production to use based on the next input symbol.
• The FOLLOW set is essential for handling ε-productions and ensuring correct parsing table
entries.

CODE:
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 20

char production[MAX][20];
char first[MAX][20];
char follow[MAX][20];
int n;

void findFirst(int i, char result[]);

void findFollow(int i, char result[]);

// Append unique characters to a set

void addToSet(char set[], char val) {
for (int i = 0; set[i] != '\0'; i++) {
if (set[i] == val)
return;
}
int len = strlen(set);
set[len] = val;
set[len + 1] = '\0';
}

// Merge two sets uniquely

void mergeSets(char dest[], char src[]) {
for (int i = 0; src[i] != '\0'; i++) {
addToSet(dest, src[i]);
}
}

// Compute FIRST of a non-terminal

void findFirst(int i, char result[]) {
char symbol = production[i][0];
char *prodBody = strchr(production[i], '>') + 1;

for (int j = 0; prodBody[j] != '\0'; j++) {

char current = prodBody[j];

if (islower(current) || current == '+' || current == '*' || current == '(' || current == ')') {

addToSet(result, current);
break;
} else if (current == '#') {
addToSet(result, '#');
break;
} else {
// Non-terminal
for (int k = 0; k < n; k++) {
if (production[k][0] == current) {
char temp[20] = "";
findFirst(k, temp);
mergeSets(result, temp);

if (strchr(temp, '#') == NULL)

break;
}
}

if (strchr(result, '#') == NULL)

break;
}
}
}

// Compute FOLLOW of a non-terminal

void findFollow(int i, char result[]) {
char symbol = production[i][0];

if (i == 0) {
addToSet(result, '$'); // Start symbol gets '$'
}

for (int j = 0; j < n; j++) {

char *rhs = strchr(production[j], '>') + 1;
for (int k = 0; rhs[k] != '\0'; k++) {
if (rhs[k] == symbol) {
if (rhs[k + 1] != '\0') {
char next = rhs[k + 1];
 if (islower(next) || next == '+' || next == '*' || next == '(' || next == ')') {
addToSet(result, next);
} else {
for (int m = 0; m < n; m++) {
if (production[m][0] == next) {
char temp[20] = "";
findFirst(m, temp);
if (strchr(temp, '#') != NULL) {
char tempFollow[20] = "";
findFollow(j, tempFollow);
mergeSets(result, tempFollow);
}
for (int x = 0; temp[x] != '\0'; x++) {
if (temp[x] != '#')
addToSet(result, temp[x]);
}
}
}
}
} else {
if (production[j][0] != symbol) {
char temp[20] = "";
findFollow(j, temp);
mergeSets(result, temp);
}
}
}
}
}
}

int main() {
printf("Enter the number of productions: ");
scanf("%d", &n);

printf("Enter productions (e.g., E->E+T):\n");

for (int i = 0; i < n; i++) {
scanf("%s", production[i]);
first[i][0] = '\0';
follow[i][0] = '\0';
}

for (int i = 0; i < n; i++) {

findFirst(i, first[i]);
}

for (int i = 0; i < n; i++) {

findFollow(i, follow[i]);
 }

printf("\nNon-Terminal\tFIRST\tFOLLOW\n");
for (int i = 0; i < n; i++) {
printf("%c\t\t%s\t%s\n", production[i][0], first[i], follow[i]);
}

return 0;
}

OUTPUT:

Enter the number of productions: 4

Enter productions:
E->TR
R->+TR
R->#
T→a

Non-Terminal FIRST FOLLOW

E a $
R +# $
T a +
 EXPERIMENT NO.- 8

AIM: WAP to recognize a valid Arithmetic Expression that uses operator +, -, * , and / .

THEORY: Flex (Fast lexical Analyzer Generator) is a tool/computer program for generating lexical
analyzers (scanners or lexers) written by Vern Paxson in C around 1987. Lex reads an input stream
specifying the lexical analyzer and outputs source code implementing the lexer in the C programming
language. The function yylex() is the main flex function which runs the Rule Section.

CODE:
#include <stdio.h>
#include <ctype.h>
#include <string.h>

// Function to check if a character is an operator

int isOperator(char ch) {
return (ch == '+' || ch == '-' || ch == '*' || ch == '/');
}

// Function to validate the arithmetic expression

int isValidExpression(char expr[]) {
int len = strlen(expr);

if (len == 0)
return 0;

// Expression should not start or end with an operator

if (isOperator(expr[0]) || isOperator(expr[len - 1]))
return 0;

for (int i = 0; i < len; i++) {

char ch = expr[i];

// Allow digits and operators

if (!isdigit(ch) && !isOperator(ch) && ch != ' ')
return 0;

// No two consecutive operators allowed

if (i > 0 && isOperator(ch) && isOperator(expr[i - 1]))
return 0;
}

return 1;
}

int main() {
char expr[100];
 printf("Enter an arithmetic expression: ");
fgets(expr, sizeof(expr), stdin);

// Remove newline character if present

expr[strcspn(expr, "\n")] = '\0';

if (isValidExpression(expr))
printf("Valid Arithmetic Expression ✅\n");
else
printf("Invalid Arithmetic Expression ❌\n");

return 0;
}

Output :

Input: 12 + 5 * 3
Output: Valid Arithmetic Expression ✅

Input: +23*4
Output: Invalid Arithmetic Expression ❌

Input: 5 / * 3
Output: Invalid Arithmetic Expression ❌