LL1 parser implementation in c
#include<stdio.h>
#include<string.h>
struct production
{
char variable;
char value[10][100];
};
int main()
{
char variable[10];
char c;
int j=0;
printf("Enter the variables");
for(int i=0;i<100;i++)
{
c=getchar();
if(c=='\n');
else if(c!=EOF)
{
variable[j]=c;
j++;
}
else
{
variable[j]=-1;
j++;
break;
}
}
char terminal[10];
printf("Enter the terminals");
j=0;
for(int i=0;i<100;i++)
{
c=getchar();
if(c=='\n');
else if(c!=EOF)
{
terminal[i]=c;
j++;
}
else
{
terminal[i]=-1;
j++;
break;
}
}
int i=0;
while(variable[i]!=-1)
{
int j=0;
int k=0;
int lr=0;
int cr=0;
while(j==0)
{
struct production prod;
prod.variable=variable[i];
printf("Enter the production of %c",variable[i]);
scanf("%s",&prod.value[k]);
if(prod.variable!=prod.value[k][0])
{
printf("%c->%s\n",prod.variable,prod.value[k]);
lr=1;
}
printf("Enter 0 to enter another production of %c",variable[i]);
scanf("%d",&j);
if(lr==1)
{
cr++;
}
if(cr!=0)
{
int k=0;
if(prod.variable==prod.value[k][0])
{
printf("%c->%sU'\n",prod.variable,prod.value[k+1]);
printf("U->");
int l=1;
int len=strlen(prod.value[k]);
while(l!=len)
{
printf("%c",prod.value[k][l]);
l++;
}
printf("|e");
}
}
k++;
}
i++;
}
return 0;
}
Write a program in c to implement nfa to dfa .
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
char NFA_FILE[MAX_LEN];
char buffer[MAX_LEN];
int zz = 0;
struct DFA {
char *states;
int count;
} dfa;
int last_index = 0;
FILE *fp; int symbols;
void reset(int ar[], int size) {
int i;
for (i = 0; i < size; i++) {
ar[i] = 0;
}
}
void check(int ar[], char S[]) {
int i, j;
int len = strlen(S);
for (i = 0; i < len; i++) {
j = ((int)(S[i]) - 65);
ar[j]++;
}
}
void state(int ar[], int size, char S[]) {
int j, k = 0;
for (j = 0; j < size; j++) {
if (ar[j] != 0)
S[k++] = (char)(65 + j);
}
// mark the end of the state
S[k] = '\0';
}
// To pick the next closure from closure set
int closure(int ar[], int size) {
int i;
for (i = 0; i < size; i++) {
if (ar[i] == 1)
return i;
} return (100); }
int indexing(struct DFA *dfa) {
int i;
for (i = 0; i < last_index; i++) {
if (dfa[i].count == 0)
return 1;
}
return -1;
}
void Display_closure(int states, int closure_ar[],
char *closure_table[],
char *NFA_TABLE[][symbols + 1],
char *DFA_TABLE[][symbols]) {
int i;
for (i = 0; i < states; i++) {
reset(closure_ar, states);
closure_ar[i] = 2;
if (strcmp(&NFA_TABLE[i][symbols], "-") != 0) {
strcpy(buffer, &NFA_TABLE[i][symbols]);
check(closure_ar, buffer);
int z = closure(closure_ar, states);
while (z != 100)
{
if (strcmp(&NFA_TABLE[z][symbols], "-") != 0) {
strcpy(buffer, &NFA_TABLE[z][symbols]);
check(closure_ar, buffer);
}
closure_ar[z]++;
z = closure(closure_ar, states);
}
}
printf("\n e-Closure (%c) :\t", (char)(65 + i));
bzero((void *)buffer, MAX_LEN);
state(closure_ar, states, buffer);
strcpy(&closure_table[i], buffer);
printf("%s\n", &closure_table[i]);
}}
int new_states(struct DFA *dfa, char S[]) {
int i;
for (i = 0; i < last_index; i++) {
if (strcmp(&dfa[i].states, S) == 0)
return 0;
}
strcpy(&dfa[last_index++].states, S);
dfa[last_index - 1].count = 0;
return 1;
}
void trans(char S[], int M, char *clsr_t[], int st,
char *NFT[][symbols + 1], char TB[]) {
int len = strlen(S);
int i, j, k, g;
int arr[st];
int sz;
reset(arr, st);
char temp[MAX_LEN], temp2[MAX_LEN];
char *buff;
for (i = 0; i < len; i++) {
j = ((int)(S[i] - 65));
strcpy(temp, &NFT[j][M]);
if (strcmp(temp, "-") != 0) {
sz = strlen(temp);
g = 0;
while (g < sz) {
k = ((int)(temp[g] - 65));
strcpy(temp2, &clsr_t[k]);
check(arr, temp2);
g++;
} } }
bzero((void *)temp, MAX_LEN);
state(arr, st, temp);
if (temp[0] != '\0') {
strcpy(TB, temp);
} else
strcpy(TB, "-"); }
printf("\t\t DFA TRANSITION STATE TABLE \t\t \n\n");
printf("\n STATES OF DFA :\t\t");
for (i = 1; i < last_index; i++)
printf("%s, ", &dfa_states[i].states);
printf("\n");
printf("\n GIVEN SYMBOLS FOR DFA: \t");
for (i = 0; i < symbols; i++)
printf("%d, ", i);
printf("\n\n");
printf("STATES\t");
for (i = 0; i < symbols; i++)
printf("|%d\t", i);
printf("\n");
printf("--------+-----------------------\n");
for (i = 0; i < zz; i++) {
printf("%s\t", &dfa_states[i + 1].states);
for (j = 0; j < symbols; j++) {
printf("|%s \t", &DFA_TABLE[i][j]);
} printf("\n");
}}
int main() {
struct DFA *dfa_states = malloc(MAX_LEN * (sizeof(dfa)));
states = 6, symbols = 2;
printf("\n STATES OF NFA :\t\t");
for (i = 0; i < states; i++)
printf("%c, ", (char)(65 + i));
printf("\n");
printf("\n GIVEN SYMBOLS FOR NFA: \t");
for (i = 0; i < symbols; i++)
printf("%d, ", i);
printf("eps");
printf("\n\n");
char *NFA_TABLE[states][symbols + 1];
char *DFA_TABLE[MAX_LEN][symbols];
strcpy(&NFA_TABLE[0][0], "FC");
strcpy(&NFA_TABLE[0][1], "-");
strcpy(&NFA_TABLE[0][2], "BF");
strcpy(&NFA_TABLE[1][0], "-");
strcpy(&NFA_TABLE[1][1], "C");
strcpy(&NFA_TABLE[1][2], "-");
strcpy(&NFA_TABLE[2][0], "-");
strcpy(&NFA_TABLE[2][1], "-");
strcpy(&NFA_TABLE[2][2], "D");
strcpy(&NFA_TABLE[3][0], "E");
printf("\n NFA STATE TRANSITION TABLE \n\n\n");
printf("STATES\t");
for (i = 0; i < symbols; i++)
printf("|%d\t", i);
printf("eps\n");
printf("--------+------------------------------------\n");
for (i = 0; i < states; i++) {
printf("%c\t", (char)(65 + i));
for (j = 0; j <= symbols; j++) {
printf("|%s \t", &NFA_TABLE[i][j]);
}
printf("\n");
}
int closure_ar[states];
char *closure_table[states];
Display_closure(states, closure_ar, closure_table, NFA_TABLE, DFA_TABLE);
strcpy(&dfa_states[last_index++].states, "-");
dfa_states[last_index - 1].count = 1;
bzero((void *)buffer, MAX_LEN);
strcpy(buffer, &closure_table[0]);
strcpy(&dfa_states[last_index++].states, buffer);
int Sm = 1, ind = 1;
int start_index = 1;
while (ind != -1) {
dfa_states[start_index].count = 1;
Sm = 0;
for (i = 0; i < symbols; i++) {
trans(buffer, i, closure_table, states, NFA_TABLE, T_buf);
strcpy(&DFA_TABLE[zz][i], T_buf);
Sm = Sm + new_states(dfa_states, T_buf);
}
ind = indexing(dfa_states);
if (ind != -1)
strcpy(buffer, &dfa_states[++start_index].states);
zz++;
}
Display_DFA(last_index, dfa_states, DFA_TABLE);
return 0; }
