Eliminating chain rules from context-free grammars

Question

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)
{
    if (!index)
        return 1;
    if (!index->strNT)
        return 2;
    if (!index->startPos || !index->chains || !index->nonChains)
        return 3;
    if (!index->table)
        return 4;
    if (!index->table->table)
        return 5;
    return 0;
}

int swap(Rule *a, Rule *b)
{
    if (!a || !b)
        return 1;

    Rule tmp = *a;
    *a = *b;
    *b = tmp;
    return 0;
}

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) || !index)
        return 1;
    char axiom = grammar->axiom;
    int size = grammar->size;
    Rule *rules = grammar->rules;
    int cntNT = 1;

    // searching for a rule which LHS is the axiom
    if (rules[0].nt != axiom) {
        int i;
        for (i = 1; i < size; ++i)
            if (rules[i].nt == axiom)
                break;
        if (i < size)
            swap(rules + i, rules);
        else
            // all the symbols are unreachable!
            return 2;
    }

    char tmp = axiom;
    for (int i = 1; i < size; ++i) {
        if (rules[i].nt != tmp) {
            ++cntNT;
            tmp = rules[i].nt;
        }
        int j = i + 1;
        while (rules[j].nt != tmp && j < size)
            ++j;
        if (j < size && j != i + 1)
            swap(rules + i + 1, rules + j);
    }
    index->cntNT = cntNT;
    return 0;
}

int processGrammar(Grammar *grammar, Index *index)
{
    if (checkGrammar(grammar) || !index)
        return 1;
    int size = grammar->size;
    Rule *rules = grammar->rules;
    int cntNT = index->cntNT;

    char *strNT = (char *)malloc(cntNT + 1); 
    if (!strNT)
        return 2;
    int *startPos = (int *)calloc(cntNT, sizeof(int));
    if (!startPos)
        return 2;
    int *chains = (int *)calloc(cntNT, sizeof(int));
    if (!chains)
        return 2;
    int *nonChains = (int *)calloc(cntNT, sizeof(int));
    if (!nonChains)
        return 2;

    char tmp = rules[0].nt;
    int writePos = 0;
    int start = 0;
    int cntChains = 0;
    int cntNonChains = 0;
    for (int i = 0; i < size; ++i) {
        if (rules[i].nt != tmp) {
            strNT[writePos] = tmp;
            startPos[writePos] = start;
            start = i;
            chains[writePos] = cntChains;
            cntChains = 0;
            nonChains[writePos] = cntNonChains;
            cntNonChains = 0;

            ++writePos;
            tmp = rules[i].nt;
        }

        const char *replace = rules[i].replace;
        if (isupper(*replace) && *(replace + 1) == '\0') {
            swap(rules + start + cntChains, rules + i);
            ++cntChains;
        }
        else 
            ++cntNonChains;
    }
    // calculations for the last non-terminal
    strNT[writePos] = tmp;
    strNT[writePos + 1] = '\0';
    startPos[writePos] = start;
    chains[writePos] = cntChains;
    nonChains[writePos] = cntNonChains;

    // dumping the results
    index->strNT = strNT;
    index->startPos = startPos;
    index->chains = chains;
    index->nonChains = nonChains;
    return 0;
}

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 -> %s\n", 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 -> %s\n", strNT[i], rules[k].replace);
        }

        for (int k = startPos[i] + chains[i];
            k < startPos[i] + chains[i] + nonChains[i]; ++k)
            printf("%c -> %s\n", 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 |", strNT[i]);
        for (int j = 0; j < size; ++j)
            printf("%2i ", table[size * i + j]);
        puts("");
    }
    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