COMPILER DESIGN

Exercise 4

23BCE1526
SWAYAM PANI

Q1.

Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define ID 0
#define PLUS 1
#define MUL 2
#define LPAREN 3
#define RPAREN 4
#define END 5

#define E 0
#define E1 1
#define T 2
#define T1 3
#define F 4

const char *table[5][6] = {

/* id + * ( ) $ */
/*E*/ { "TQ", "", "", "TQ", "", "" },
/*Q*/ { "", "+TQ", "", "", "ε", "ε" },
/*T*/ { "FR", "", "", "FR", "", "" },
/*R*/ { "", "ε", "*FR", "", "ε", "ε" },
/*F*/ { "i", "", "", "(E)", "", "" }
};

typedef struct {
char data[1000];
int top;
} Stack;

void push(Stack *s, char c) {

s->data[++(s->top)] = c;
}

char pop(Stack *s) {

if (s->top == -1) return '\0';
return s->data[(s->top)--];
}

char peek(Stack *s) {

if (s->top == -1) return '\0';
return s->data[s->top];
}
int term_index(char c) {
if (c == 'i') return ID;
if (c == '+') return PLUS;
if (c == '*') return MUL;
if (c == '(') return LPAREN;
if (c == ')') return RPAREN;
if (c == '$') return END;
return -1;
}

int nonterm_index(char c) {
if (c == 'E') return E;
if (c == 'Q') return E1; // using Q for E'
if (c == 'T') return T;
if (c == 'R') return T1; // using R for T'
if (c == 'F') return F;
return -1;
}

int predictive_parse(const char *input) {

Stack stack;
stack.top = -1;

push(&stack, '$');
push(&stack, 'E');

int ip = 0;

while (1) {
char X = peek(&stack);
char a = input[ip];

if (X == '$' && a == '$') {

return 1; // ACCEPT
}

if (isupper(X)) {
int row = nonterm_index(X);
int col = term_index(a);
if (row == -1 || col == -1) return 0;

const char *prod = table[row][col];

if (prod[0] == '\0') {
return 0; // no production => error
}

pop(&stack);

if (strcmp(prod, "ε") != 0) {

for (int i = strlen(prod) - 1; i >= 0; i--) {

push(&stack, prod[i]);
}
}
}
else { // Terminal
if (X == a) {
pop(&stack);
 ip++;
} else {
return 0; // mismatch
}
}
}
}

int main() {
char input[100];

printf("Enter input string (use 'i' for id). Example: i+i*i+i\n");

scanf("%s", input);

strcat(input, "$");

if (predictive_parse(input))
printf("ACCEPTED\n");
else
printf("REJECTED\n");

return 0;
}

Output:
Q2
Code:
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAXSTACK 1000

#define MAXINPUT 1000

enum {NT_S = 0, NT_L = 1, NT_P = 2};

int term_index(char c) {
if (c == '(') return 0;
if (c == 'a') return 1;
if (c == ',') return 2;
if (c == ')') return 3;
if (c == '$') return 4;
return -1;
}

const char *table[3][5] = {

// '(' 'a' ',' ')' '$'
{ "(L)", "a", "", "", "" }, // S
{ "SP", "SP", "", "", "" }, // L (S P where P = L')
{ "", "", ",SP", "ε", "" } // P (L')
};

typedef struct {
char data[MAXSTACK];
int top;
} Stack;

void init(Stack *s) { s->top = -1; }

int empty(Stack *s) { return s->top == -1; }
void push(Stack *s, char c) { if (s->top < MAXSTACK-1) s->data[++(s->top)] = c; }
char pop(Stack *s) { if (s->top == -1) return '\0'; return s->data[(s->top)--]; }
char peek(Stack *s) { if (s->top == -1) return '\0'; return s->data[s->top]; }

void print_stack(Stack *s) {

// print top -> ... -> bottom
printf("Stack(top->...): ");
for (int i = s->top; i >= 0; --i) putchar(s->data[i]);
}

void normalize_input(const char *raw, char *out) {

int j = 0;
for (int i = 0; raw[i] != '\0'; ++i) {
char c = raw[i];
if (isspace((unsigned char)c)) continue;

if (c == 'a' || c == '(' || c == ')' || c == ',') {

out[j++] = c;
 } else {

out[j++] = c;
}
}
out[j] = '\0';
}

int nonterm_row(char c) {
if (c == 'S') return NT_S;
if (c == 'L') return NT_L;
if (c == 'P') return NT_P;
return -1;
}

int predictive_parse(const char *input_raw) {

char in_norm[MAXINPUT];
normalize_input(input_raw, in_norm);

char input[MAXINPUT];
strcpy(input, in_norm);
strcat(input, "$");

Stack st;
init(&st);
push(&st, '$');
push(&st, 'S'); // start symbol

int ip = 0;

printf("Parsing input: %s\n", input);

printf("-----------------------------------------\n");
printf("Step | ");
printf("Stack | ");
printf("Input | ");
printf("Action\n");
printf("-----------------------------------------\n");

int step = 0;
while (1) {
step++;
printf("%4d | ", step);
print_stack(&st);
printf(" | %s", &input[ip]);

int cur_len = 0;
printf(" | ");

char X = peek(&st);
char a = input[ip];

if (X == '$' && a == '$') {

printf("Both $ -> ACCEPT\n");
return 1;
}
 if (X == 'S' || X == 'L' || X == 'P') {
int row = nonterm_row(X);
int col = term_index(a);
if (col == -1) {
printf("ERROR: unexpected input symbol '%c'\n", a);
return 0;
}
const char *prod = table[row][col];
if (prod == NULL || strlen(prod) == 0) {
printf("ERROR: no production for (%c, %c)\n", X, a);
return 0;
}

pop(&st); // remove non-terminal

if (strcmp(prod, "ε") != 0) {

for (int i = strlen(prod) - 1; i >= 0; --i) {

push(&st, prod[i]);
}
printf("%c -> %s\n", X, prod);
} else {
// epsilon production
printf("%c -> ε\n", X);
}
} else {

if (X == a) {
pop(&st);
ip++;
printf("match '%c'\n", a);
} else {
printf("ERROR: terminal mismatch: stack has '%c' but input has '%c'\n", X, a);
return 0;
}
}
}
}

int main() {
char line[512];

printf("Enter input string (allowed tokens: a ( ) , ). Example: (a,(a,a)) \n");

if (!fgets(line, sizeof(line), stdin)) return 0;
// strip newline
line[strcspn(line, "\n")] = '\0';

int res = predictive_parse(line);

printf("-----------------------------------------\n");
if (res) printf("Result: ACCEPTED\n");
else printf("Result: REJECTED\n");

return 0;
}
Output:
Q3.
Code:
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAXSTACK 1000

typedef struct {
char data[MAXSTACK];
int top;
} Stack;

void init(Stack *s) { s->top = -1; }

int empty(Stack *s) { return s->top == -1; }
void push(Stack *s, char c) { if (s->top < MAXSTACK-1) s->data[++(s->top)] = c; }
char pop(Stack *s) { if (s->top == -1) return '\0'; return s->data[(s->top)--]; }
char peek(Stack *s) { if (s->top == -1) return '\0'; return s->data[s->top]; }

int predictive_parse(const char *input) {

Stack st;
init(&st);
push(&st, '$');
push(&st, 'S');

int ip = 0;
char a = input[ip];

while (!empty(&st)) {
char X = peek(&st);

if (X == '$' && a == '$') return 1;

if (X == 'S') {
if (a == 'a') { // could be AB or D a
pop(&st);
// To handle "ab" lookahead
if (input[ip+1] == 'b') { // A -> ab case
push(&st, 'B'); push(&st, 'A');
} else { // "D a" case
push(&st, 'a'); push(&st, 'D');
}
} else if (a == 'c') {
pop(&st); push(&st, 'B'); push(&st, 'A');
} else if (a == 'f') {
pop(&st); push(&st, 'a'); push(&st, 'D');
} else return 0;
}
else if (X == 'A') {
if (a == 'a' && input[ip+1] == 'b') {
pop(&st); push(&st, 'b'); push(&st, 'a');
} else if (a == 'c') {
pop(&st); push(&st, 'c');
} else return 0;
}
else if (X == 'B') {
if (a == 'd') {
pop(&st); push(&st, 'C'); push(&st, 'd');
} else return 0;
}
 else if (X == 'C') {
if (a == 'e') {
pop(&st); push(&st, 'C'); push(&st, 'e');
} else { pop(&st); } // ε
}
else if (X == 'D') {
if (a == 'f') {
pop(&st); push(&st, 'D'); push(&st, 'f');
} else { pop(&st); } // ε
}
else { // terminal
if (X == a) {
pop(&st); ip++; a = input[ip];
} else return 0;
}
}
return 0;
}

int main() {
char str1[] = "abdee$";
char str2[] = "efffba$";

printf("Testing abdee: %s\n", predictive_parse(str1) ? "ACCEPTED" : "REJECTED");

printf("Testing efffba: %s\n", predictive_parse(str2) ? "ACCEPTED" : "REJECTED");

return 0;
}

Output: