trjhtr

I'm writing a small C program for elimination of chain rules from a context-free grammar.
My idea is to rewrite the rules of the grammar in a specific useful order: making groups of productions that start with the same non-terminal, the group of the axiom being the first one in the list.
In each group, chain rules are listed first, other rules follow them.
In this way a sequence (index) of non-terminals of the left sides is formed. Each non-terminal can be identified uniquely by its number in the sequence.

Then, matrix representation of the chain rules is used (an oriented graph, I think): the row index corresponds to the LHS non-terminal, and the column index is for the RHS non-terminal.
The obtained table is later filled to account all the new productions that should be included in the grammar after the chain rules are eliminated.

Finally, the table is used for the output of the modified production set.

I'm interested if simpler approaches are possible, and in case they are impossible, what can be corrected in my code.

Type definitions and functions.

#include <stdlib.h>
#include <ctype.h>
#include <limits.h>

typedef struct 
 char nt; // non-terminal
 const char *replace;
 Rule;

typedef struct 
 char axiom;
 unsigned int size;
 Rule *rules;
 Grammar;

typedef struct 
 unsigned int size;
 bool *table;
 Table;

typedef struct 
 unsigned int cntNT;
 char *strNT;
 int *startPos;
 int *chains;
 int *nonChains;
 Table *table;
 Index;


int checkGrammar(Grammar *grammar)

 if (!grammar)
 return 1;
 if (!grammar->rules)
 return 2;
 for (unsigned int i = 0; i < grammar->size; ++i)
 if (!grammar->rules[i].replace)
 return 3;
 return 0;


int checkIndex(Index *index)


int swap(Rule *a, Rule *b)

 if (!a 

int initRule(Rule *rule, char nt, const char *str)

 if (!rule)
 return 1;
 if (!str)
 return 2;

 rule->nt = nt;
 rule->replace = str;
 return 0;


int findPos(const char *str, char c)

 if (!str)
 return -INT_MIN;

 const char *ptr = strchr(str, c);
 if (!ptr)
 return -1;
 else
 return ptr - str;


int presortGrammar(Grammar *grammar, Index *index)

 if (checkGrammar(grammar) 

int processGrammar(Grammar *grammar, Index *index)


int printGrammar(Grammar *grammar)

 if (checkGrammar(grammar))
 return 1;

 for (unsigned int i = 0; i < grammar->size; ++i) 
 Rule rule = grammar->rules[i];
 printf("%c -> %sn", rule.nt, rule.replace);
 
 puts("");
 return 0;


int printGrammarWithoutChains(Grammar *grammar, Index *index)

 if (checkGrammar(grammar))
 return 1;
 if (checkIndex(index))
 return 2;

 int size = index->cntNT;
 char *strNT = index->strNT;
 Rule *rules = grammar->rules; 

 int *startPos = index->startPos;
 int *chains = index->chains;
 int *nonChains = index->nonChains;
 bool *table = index->table->table;

 for (int i = 0; i < size; ++i) 
 if (chains[i]) 
 for (int j = 0; j < size; ++j)
 if (table[size * i + j])
 for (int k = startPos[j] + chains[j];
 k < startPos[j] + chains[j] + nonChains[j]; ++k)
 printf("%c -> %sn", strNT[i], rules[k].replace);
 

 for (int k = startPos[i] + chains[i];
 k < startPos[i] + chains[i] + nonChains[i]; ++k)
 printf("%c -> %sn", strNT[i], rules[k].replace);
 
 puts("");
 return 0;


int printTable(Index *index)

 if (checkIndex(index))
 return 1;

 int size = index->table->size;
 bool *table = index->table->table;
 char *strNT = index->strNT;
 printf("%*c", 3, ' ');
 for (int i = 0; i < size; ++i)
 printf("%2c ", strNT[i]);
 puts("");
 for (int i = 0; i < size; ++i) 
 printf("%c 
 puts("");
 return 0;


int initTable(Grammar *grammar, Index *index)

 if (checkGrammar(grammar))
 return 1;
 if (checkIndex(index))
 return 2;

 int cntNT = index->cntNT;
 bool *table = (bool *)calloc(cntNT * cntNT, sizeof(bool));
 if (!table)
 return 3;

 index->table->table = table;
 index->table->size = cntNT;
 const char *strNT = index->strNT;
 int *startPos = index->startPos;
 int *chains = index->chains;
 Rule *rules = grammar->rules;

 for (int i = 0; i < cntNT; ++i) 
 for (int k = startPos[i]; k < startPos[i] + chains[i]; ++k) 
 int j = findPos(strNT, *(rules[k].replace));
 // unproductive symbols in chain rules are actually removed here.
 if (j >= 0)
 table[cntNT * i + j] = true;
 
 return 0;


int fillTable(Table *matrix)

 if (!matrix)
 return 1;
 if (!matrix->table)
 return 2;

 int size = matrix->size;
 bool *table = matrix->table;
 for (int i = 0; i < size; ++i) 
 for (int j = 0; j < size; ++j) 
 if (table[size * i + j]) 
 for (int k = 0; k < size; ++k)
 if (table[size * j + k])
 table[size * i + k] = true;

 // clearing the main diagonal
 // chain rules of the type A -> A are excluded
 for (int i = 0; i < size; ++i)
 table[size * i + i] = false;
 return 0;


int freeMemory(Index *index)

 if (checkIndex(index))
 return 1;

 free(index->strNT);
 free(index->startPos);
 free(index->chains);
 free(index->nonChains);
 free(index->table->table);
 return 0;

A possible main():

int main()

 Grammar grammar;
 grammar.axiom = 'S';
 grammar.size = 8;
 grammar.rules = malloc(grammar.size * sizeof(*(grammar.rules)));
 if (!grammar.rules) 
 puts("malloc() ERROR! Grammar initialization failed!");
 return -1;
 
 Rule *rules = grammar.rules;
 initRule(rules + 0, 'S', "aFb");
 initRule(rules + 1, 'S', "A");
 initRule(rules + 2, 'A', "aA");
 initRule(rules + 3, 'A', "B");
 initRule(rules + 4, 'B', "aSb");
 initRule(rules + 5, 'B', "S");
 initRule(rules + 6, 'F', "bc");
 initRule(rules + 7, 'F', "bFc");

 puts("This context-free grammar was entered:");
 printGrammar(&grammar);

 Index index;
 Table table;
 index.table = &table;
 int statusPresortGrammar = presortGrammar(&grammar, &index);
 if (statusPresortGrammar) 
 printf("Halting. presortGrammar() returned ERROR code %i.n",
 statusPresortGrammar);
 return 1;
 

 int statusProcessGrammar = processGrammar(&grammar, &index);
 if (statusProcessGrammar) 
 printf("Halting. processGrammar() returned ERROR code %i.n",
 statusProcessGrammar);
 return 1;
 
 puts("The grammar after re-ordering:");
 printGrammar(&grammar);

 int statusInitTable = initTable(&grammar, &index);
 if (statusInitTable) 
 printf("Halting. initTable() returned ERROR code %i.n",
 statusInitTable);
 return 1;
 
 puts("Matrix representation of the chain rules:");
 printTable(&index);
 puts("Table filling results (all the long chain substitutions are contracted):");
 fillTable(index.table);
 printTable(&index);

 puts("An equivalent grammar without chain rules:");
 printGrammarWithoutChains(&grammar, &index);

 freeMemory(&index);
 return 0;

Output:

This context-free grammar was entered:
S -> aFb
S -> A
A -> aA
A -> B
B -> aSb
B -> S
F -> bc
F -> bFc

The grammar after re-ordering:
S -> A
S -> aFb
A -> B
A -> aA
B -> S
B -> aSb
F -> bc
F -> bFc

Matrix representation of the chain rules:
 S A B F
S | 0 1 0 0
A | 0 0 1 0
B | 1 0 0 0
F | 0 0 0 0

Table filling results (all the long chain substitutions are contracted):
 S A B F
S | 0 1 1 0
A | 1 0 1 0
B | 1 1 0 0
F | 0 0 0 0

An equivalent grammar without chain rules:
S -> aA
S -> aSb
S -> aFb
A -> aFb
A -> aSb
A -> aA
B -> aFb
B -> aA
B -> aSb
F -> bc
F -> bFc