Konwersja Gramatyki bezkontekstowej do Postaci Normalnej Chomskyego

Question

Dzień dobry,

piszę zamianę Gramatyki bezkontekstowej do postaci normalnej Chomskyego, znalazłem opis na Wikipedii - Konwersja Wikipedia i próbuję to zaimplementować, jednak przy drugim kroku mój program daje nieprawidłowe rezultaty, a trzeciego kroku nie rozumiem.

Na angielskiej wikipedii opis konwersji jest o wiele bardziej rozbudowany - Angielska wersja.

Moje pytanie - czy ktoś ma/mógłby podzielić się implementacją w C/C++ tego algorytmu żeby można było poczytać i krok po kroku prześledzić?

Tutaj zamieszczam przykładowy input:

S:bA|aB
A:bAA|aSb|a
B:aaBB|b

Answer 1

Wystarczy zajrzeć na lepszą stronę Wikipedii:

https://en.wikipedia.org/wiki/Chomsky_normal_form

Poszukać głębiej:

https://www.tutorialspoint.com/automata_theory/chomsky_normal_form.htm

http://stackoverflow.com/questions/4883769/chomsky-normal-form

https://github.com/nikos912000/chomsky-normal-form

https://github.com/search?utf8=%E2%9C%93&q=chomsky+normal+form+cnf&type=

 edit: https://github.com/search?l=C%2B%2B&q=chomsky+normal+form+cnf&type=Code&utf8=%E2%9C%93

Następnie pomyślec jak to zrobić w C++. Masz już tyle materiału, że dostosowanie tego do narzędzia (języka) nie stanowi żadnego problemu.

Comments

#include <iostream>

using namespace std;

int symbol_nieterminalny(string produkcja) {
    for(unsigned i=0; i<produkcja.size(); ++i) {
        if (produkcja[i] >= 97 && produkcja[i] <= 122) {
            return i;
        }
    }
    return -1;
}

int znak_podzialu(string produkcja) {
    for(unsigned i=0; i<produkcja.size(); ++i) {
        if (produkcja[i] == '|') {
            return i;
        }
    }
    return -1;
}

int regula_lancuchowa(string produkcja) {
    for(unsigned i=0; i<produkcja.size(); ++i) {
        if (produkcja[i] >= 65 && produkcja[i] <= 90 && produkcja[i] != produkcja[0]) {
            return i;
        }
    }
    return -1;
}

string pobierz_regule(unsigned liczba_zmiennych, string *tablica_produkcji, char symbol_startowy) {
    for(unsigned i=0; i<liczba_zmiennych; ++i) {
        if(tablica_produkcji[i][0] == symbol_startowy) {
            return tablica_produkcji[i].substr(3, tablica_produkcji[i].length());
        }
    }
    return "";
}

unsigned dodaj_regule(unsigned liczba_zmiennych, string *tablica_produkcji, string regula) {
    for(unsigned i=0; i<liczba_zmiennych; ++i) {
        if(tablica_produkcji[i] == regula) {
            return liczba_zmiennych;
        }
    }
    tablica_produkcji[liczba_zmiennych] = regula;
    return ++liczba_zmiennych;
}

void wyswietl(unsigned liczba_zmiennych, string *tablica_produkcji) {
    for(unsigned i=0; i<liczba_zmiennych; ++i) {
        cout<<tablica_produkcji[i]<<endl;
    }
    cout<<endl;
}

int main() {
    string badane_slowo; unsigned liczba_zmiennych; string *tablica_produkcji;
    badane_slowo = "baa";
    liczba_zmiennych = 3;
    tablica_produkcji = new string[liczba_zmiennych*100];
    tablica_produkcji[0] = "S->bA|aB";
    tablica_produkcji[1] = "A->bAA|aSb|a";
    tablica_produkcji[2] = "B->aaBB|b";

    /**
     * Zastąpienie symboli terminalnych, symbolami nieterminalnymi
     */
    unsigned limit = liczba_zmiennych;
    for(unsigned i=0; i<limit; ++i) {
        while(symbol_nieterminalny(tablica_produkcji[i]) != -1) {
            int pozycja = symbol_nieterminalny(tablica_produkcji[i]);
            char znak = tablica_produkcji[i][pozycja];
            tablica_produkcji[i][pozycja] = znak-48;
            string regula = " -> ";
            regula[0] = znak-48;
            regula[3] = znak;
            liczba_zmiennych = dodaj_regule(liczba_zmiennych, tablica_produkcji, regula);
        }
    }

    wyswietl(liczba_zmiennych, tablica_produkcji);

    /**
     * Odpowiednie wydzielenie produkcji
     */
    for(unsigned i=0; i<liczba_zmiennych; ++i) {
        while(znak_podzialu(tablica_produkcji[i]) != -1) {
            int pozycja = znak_podzialu(tablica_produkcji[i]);
            string regula = tablica_produkcji[i].substr(0, pozycja);
            liczba_zmiennych = dodaj_regule(liczba_zmiennych, tablica_produkcji, regula);
            string czesc1 = tablica_produkcji[i].substr(0, 3);
            string czesc2 = tablica_produkcji[i].substr(pozycja+1, tablica_produkcji[i].length());
            tablica_produkcji[i] = czesc1 + czesc2;
        }
    }

    wyswietl(liczba_zmiennych, tablica_produkcji);


    /**
     * Eliminacja reguł łańcuchowych
     */
    for(unsigned i=0; i<liczba_zmiennych; ++i) {
        int pozycja = regula_lancuchowa(tablica_produkcji[i]);
        if (pozycja == -1) {
            continue;
        }
        char symbol_startowy = tablica_produkcji[i][pozycja];
        string regula = pobierz_regule(liczba_zmiennych, tablica_produkcji, symbol_startowy);
        string czesc1 = tablica_produkcji[i].substr(0, pozycja);
        string czesc2 = tablica_produkcji[i].substr(pozycja + 1, tablica_produkcji[i].length());
        tablica_produkcji[i] = czesc1 + regula + czesc2;
    }

    wyswietl(liczba_zmiennych, tablica_produkcji);


    return 0;
}

/*
void CFG::toCNF(){
    /*
     * add a variable for every terminal
     *
    std::map<std::string, std::vector<std::string> >::iterator it;
    for (unsigned int i = 0; i< terminals_.size(); i++){
        variables_.push_back(utilities::lowToUp(terminals_[i]));
        for (it = rules_.begin(); it != rules_.end(); it++){
            for (unsigned int e = 0; e < it->second.size(); e++){
                it->second[e] = utilities::replacestring(it->second[e], terminals_[i],
                                                         utilities::lowToUp(terminals_[i]));
            }
        }

    }
    /*
     * now we need to eleminate all replacement rules; greater then 3;
     *
    std::map<std::string, std::vector<std::string> > newmap;
    std::string newvar = "A";
    for (it = rules_.begin(); it != rules_.end(); it++){
        // dla każdej produkcji w tablicy produkcji
        for (unsigned int t = 0; t < it->second.size(); t++){
            // dla każdej zasady w produkcji
            if (it->second[t].size() <= 2){
                newmap[it->first].push_back(it->second[t]);
            }
            else if(it->second[t].length() > 2){
                std::string ruler = it->second[t];
                std::string firstvar = it->first;
                while (ruler.length() > 2){
                    bool invar = true;
                    while(invar){
                        invar = false;
                        for (unsigned int r; r < variables_.size(); r++){
                            if(variables_[r] == newvar){
                                newvar = utilities::nextstring(newvar);
                                invar = true;
                            }
                        }
                    }
                    std::string back = ruler.substr(0,1) + newvar;
                    newmap[firstvar].push_back(back);
                    ruler = ruler.substr(1);
                    firstvar = newvar;
                    variables_.push_back(firstvar);
                }
            }
        }
    }
    rules_ = newmap;
}
/* */

 

Bardzo dziękuję za te linki.​​ Piszę program na podstawie, kodu zamieszczonego pod mainem(znalezionego w tych adresach) oraz linków do wikipedii. Kod na którym bazuję biorę stąd: https://github.com/TREK-TMS-BB/TMS-BB/blob/56d1f9a5972ed4e2aaf8b011a08a2d2538d9b3c2/src/CFG.cpp

Zawiesiłem się jednak w kroku "Eliminacja reguł łańcuchowych".