DFA LL1

#include <stdio.h> #include <string.h> #define NUM_STATES 7 #define NUM_INPUTS 3 // DFA states enum { D0, D1, D2, D3, D4, D5, DEAD }; // Input mapping: a -> 0, b -> 1, other -> 2 int get_input(char c) { if (c == 'a') return 0; if (c == 'b') return 1; return 2; // invalid input } // Accepting states with token labels const char* accepting_tokens[NUM_STATES] = { "", // D0 -> accepting "a*", // D1 "a*b+", // D2 "a*", // D3 "a*b+", // D4 "a*b+,abb", NULL // DEAD }; int main() { // DFA transition table: next_state[current_state][input_symbol] int next_state[NUM_STATES][NUM_INPUTS] = { /* D0 */ { D1, D2, DEAD }, /* D1 */ { D3, D4, DEAD }, /* D2 */ { DEAD, D2, DEAD }, /* D3 */ { D3, D2, DEAD }, /* D4 */ { DEAD, D5, DEAD }, /* D5 */ { DEAD, D2, DEAD }, /* DEAD */{ DEAD, DEAD, DEAD } }; char str[100]; printf("Enter a string: "); scanf("%s", str); int state = D0; for (int i = 0; str[i] != '\0'; i++) { int input = get_input(str[i]); state = next_state[state][input]; if (state == DEAD) break; } // Check if the final state is accepting if (accepting_tokens[state] != NULL) { printf("%s Accepted by DFA: %s\n", str, accepting_tokens[state]); } else { printf("%s Rejected by all patterns\n", str); } return 0; } #include <stdio.h> #include <string.h> #define MAXSTACK 200 #define MAXTOK 200 #define MAXSYM 50 // ---------------------- // Grammar // E → T E' // E' → + T E' | ε // T → id // ---------------------- char *NT[] = {"E","Eprime","T"}; #define NNT 3 char *TERMINALS[] = {"id","+","$"}; #define NTER 3 char *RHS[] = { "T Eprime", // 1 "+ T Eprime", // 2 "", // 3 epsilon "id" // 4 }; // LL(1) table: nonterminal x terminal -> production index int TABLE[NNT][NTER] = { {1,0,0}, // E {0,2,3}, // E' {4,0,0} // T }; // ---------------------- // Stack // ---------------------- char stack[MAXSTACK][MAXSYM]; int top = -1; void push(char *s){ strcpy(stack[++top], s); } char* pop(){ return (top>=0)?stack[top--]:NULL; } void print_stack(){ printf("["); for(int i=top;i>=0;i--){ printf("%s",stack[i]); if(i>0) printf(", "); } printf("]"); } // ---------------------- // Helpers // ---------------------- int find_nt(char *x){ for(int i=0;i<NNT;i++) if(strcmp(NT[i],x)==0) return i; return -1; } int find_t(char *x){ for(int i=0;i<NTER;i++) if(strcmp(TERMINALS[i],x)==0) return i; return -1; } int tokenize(char *line, char tokens[][MAXSYM]){ int n=0; char *p = strtok(line," \t\n"); while(p){ strcpy(tokens[n++], p); p=strtok(NULL," \t\n"); } if(n==0 || strcmp(tokens[n-1],"$")!=0) strcpy(tokens[n++], "$"); return n; } // ---------------------- // Parser // ---------------------- int main(){ char line[500]; printf("Enter input string (tokens separated by spaces, e.g. 'id + id'):\n"); fgets(line,sizeof(line),stdin); char input[MAXTOK][MAXSYM]; int n = tokenize(line, input); printf("\nTokens detected:\n"); for(int i=0;i<n;i++) printf("%s ",input[i]); printf("\n\n"); push("$"); push(NT[0]); // start symbol int ip=0; printf("%-25s %-10s %-10s %-25s\n","Stack","Lookahead","Top","Production Applied"); printf("-------------------------------------------------------------------\n"); while(top>=0){ //get top of stack char X[MAXSYM]; strcpy(X,pop()); //lookahead char *a = input[ip]; printf("%-25s %-10s %-10s ","" , a, X); //check if top of stack is terminal int tindex = find_t(X); if(tindex!=-1){ // terminal if(strcmp(X,a)==0){ printf("%-25s\n","match"); //moving to next input token ip++; } else { //will be printed on production applied column of output printf("REJECTED\n"); return 0; } print_stack(); printf("\n"); continue; } int ntindex = find_nt(X); int aindex = find_t(a); //check if something out of grammar if(ntindex==-1 || aindex==-1){ printf("REJECTED\n"); return 0; } //find production rule from 2D parsing table int prod = TABLE[ntindex][aindex]; if(prod==0){ printf("REJECTED\nNo rule for (%s,%s)\n", X,a); return 0; } if(strlen(RHS[prod-1])==0) printf("%-25s\n","epsilon"); else printf("%-25s\n", RHS[prod-1]); //push the production rule to stack if(strlen(RHS[prod-1])>0){ char temp[200]; strcpy(temp,RHS[prod-1]); char *p = strtok(temp," "); char symbols[10][MAXSYM]; int k=0; while(p){ strcpy(symbols[k++],p); p=strtok(NULL," "); } for(int i=k-1;i>=0;i--) push(symbols[i]); } print_stack(); printf("\n"); } //if finally stack empty then accepted if(strcmp(input[ip],"")==0) printf("\nACCEPTED\n"); else printf("\nREJECTED: input not fully consumed\n"); return 0; }