arne-cl / alt-mulig Goto Github PK

There seems to be a std::ostream --> std:ofstream mismatch:

~/repos/alt-mulig/cpp $ clang --std=c++11 and-or-graph-test.cpp 
and-or-graph-test.cpp:45:25: error: non-const lvalue reference to type 'std::ostream' (aka 'basic_ostream<char>') cannot bind to a temporary of type 'std::ofstream'
      (aka 'basic_ofstream<char>')
  grm_and_or_graph.draw(std::ofstream("cfg.dot"));
                        ^~~~~~~~~~~~~~~~~~~~~~~~
./AndOrGraph.hpp:73:27: note: passing argument to parameter 'dot_out' here
  void draw(std::ostream& dot_out, bool top_down=true) const
                          ^
1 error generated.

Note: there will be n right-hand sides for each left-hand side!

Passen Sie rules_for() an die neue Datenstruktur an (was einfach ist). Wenn ein Nichtterminal nicht im Regelindex gefunden wurde, können Sie ein beliebiges Paar von zwei gleichen Iteratoren über productions (z.B. productions.end()) zurückgeben (was dann einem leeren Intervall entspricht).

Testen Sie rules_for() ausführlich.

Vervollständigen Sie ContextFreeGrammar::read_in() und build_rule_index(); diese Funktion baut die Indexdatenstruktur in rule_index in folgender Weise auf: nach dem Sortieren der eingelesenen Regeln ordnen wir jedem Nichtterminal auf der linken Seite einer Regel den Bereich derjenigen Regeln im Vektor productions zu, die dieses Nichtterminal expandieren. Diesen Bereich repräsentieren wir als ein Paar von Regeliteratoren (=Vektor-Iteratoren) in der üblichen Weise als halboffenes Intervall: die erste Komponente dieses Paars (.first) zeigt auf den Anfang des Bereichs für das Nichtterminal, die zweite Komponente (.second) zeigt auf die Position in productions nach der letzten Regel für das Nichtterminal.

Den Aufbau dieses Index’ kann man durch eine einfache Iteration über den Regelvektor implementieren. Immer wenn sich die linke Regelseite ändert, ist eine Teilbereichsgrenze gefunden. Am Ende des Vektors muss man noch eine Grenzfallbetrachtung anstellen, um den Regelbereich für das letzte Nichtterminal in rule_index einzutragen. Setzen Sie die linke Seite der ersten Regel als Startsymbol der Grammatik fest.

Hinweise: mit std::make_pair können Sie Paare erstellen. Testen Sie cfg_demo mit der beigelegten Beispielgrammatik und testen Sie alles ausführlich auch mit selbst erstellten Grammatiken.

Machen Sie der Erkenner zum Parser!

Eine Klasse ParseForest ist hierfür schon vorgesehen. Intern ist der Parse-Wald ein Und-Oder-Graph, der nur die passiven Kanten (die unter dem “.”-Schlüssel in den maps) enthält.

Die Symbole dieses Und-Oder-Graphen (Template-Parameter!) sind Tripel der Form (unsigned,Symbol,unsigned) wie folgt: wenn beispielsweise eine VP zwischen den Positionen 2 und 5 komplett gefunden wurde, dann enthält der Und-Oder-Graph den Knoten (2,VP,5). (Das ist eigentlich die Bar-Hillel-Shamir-Perles-Konstruktion des Schnitts einer kf. Grammatik mit einem Automaten).

Da die Klasse AndOrGraph auf einem Hash-Container basiert, müssen Sie Hash- und operator==-Funktion für die Tripel bereitstellen.

Den Und-Oder-Graphen können Sie visualisieren oder sogar die Bäume extrahieren.

Bauen Sie den boost-Tokenizer (Sie müssen dazu boost installieren) in den Konstruktor von CFGRule ein und initialisieren Sie lhs und rhs aus den Ergebnissen der Tokenisierung. Vermeiden Sie dabei explizite Schleifen und verwenden Sie stattdessen STL-Funktionalität. Machen Sie umfangreiche Fehlerüberprüfung (kein Pfeil in der Regel, kein Symbol vor dem Pfeil usw.) und geben Sie aussagekräftige Fehlermeldungen auf std::cerr aus (Fehler in welcher Zeile, welche Regel, was ist falsch). Fehlerhafte Regeln sollten nicht in die Grammatik eingefügt werden.

return a const reference.

Symbol (left-hand side) is already known.

According to TH, this doesn't define a total transitive order on the rule set:

    bool operator<(const CFGRule& other) const
    {
        if (lhs < other.lhs) {return true;}
        if (rhs < other.rhs) {return true;}
        return false;
    }

He gave an example using integers, where bad_set uses my function, while good_set uses lexicographical ordering:

Bad set found while trying to find (82,98)
bad_set =  (90,7) (31,98) (44,48) (82,98) (84,88) (71,92)
good_set = (31,98) (44,48) (71,92) (82,98) (84,88) (90,7)

Stellen Sie den Earley-Erkenner fertig.

Hierzu müssen Sie die Funktionen predict(), complete(), lexical_scan() und preterminal_scan() fertigstellen.

Ich habe zwei Versionen von der Scan-Operation, und zwar eine (lexical_scan()), bei der das Lexikon Teil der Grammatik ist und eine, bei der es separat ist (preterminal_scan()). Die erstere ist sehr einfach zu implementieren, hat aber den Nachteil, dass beim Predict-Schritt das gesamte Teillexikon für das gegebene Nichtterminal vorausgesagt wird. preterminal_scan() hingegen greift bei Präterminalen (also den Wortarten, die bei einer Grammatik ohne Lexikonregeln eigentlich die Terminale sind) auf das separate Lexikon zurück.

Bei der Programmierung müssen Sie etwas aufpassen: der Parser ist aus Effizienzgründen ja referenzbasiert, d.h. in den Earley-Items befinden sich Referenzen auf Grammatik-Regeln. Im Fall eines separaten Lexikons müssen wir diese Regeln ad-hoc erzeugen. Damit wir davon Referenzen erzeugen können, müssen die Original mindestens so lange leben wie der Parse-Prozess dauert. Hier eignet sich z.B. eine std::list<CFGRule> als Instanzvariable (ein Vektor ist ungeeignet, wegen seiner Reallokationsstrategie und der nachfolgenden Invalidierung der Referenzen).

Die Wahl, ob separates Lexikon oder nicht, wird durch eine boolsche Variable in earley-parser.cpp gesteuert.

Die Aufgabe erfordert etwa 50 Programmzeilen.

Entwerfen Sie eine Klasse Lexicon, die im Konstruktor einen istream mit einer zweispaltigen (tab-separierten) Textdatei einliest: Spalte 1 Wort, Spalte 2 Wortart (Sie können dazu den Code aus ContextFreeGrammar adaptieren).

Intern soll Ihr Lexikon auf einer hash map (unordered_map) basieren. Beachten Sie, dass ein Wort mehreren Wortarten zugeordnet werden kann. Implementieren Sie alle Funktionen, die ein Parser von einer Lexikonklasse verlangt.

This should work python ner.py < demo.in, but doesn't

readiter() works, but this loop doesn't.

        for X in readiter(fi, F, options.separator):
            feature_extractor(X)
            output_features(fo, X, 'y')

hash() uses unsigned for h, although FNVHash(lhs) returns unsigned long:

  unsigned hash() const
  {
    // Linke Seite
    unsigned h = FNVHash(lhs);
    // Rechte Seite
    for (unsigned i = 0; i < rhs.size(); ++i) {
      // Wir verwenden boost::hash_combine zur Kombination aller Hashwerte
      boost::hash_combine(h, rhs[i]);
    }
    return h;
  }

~/repos/alt-mulig/cpp $ clang -std=c++11 CFGRule.hpp 
CFGRule.hpp:116:7: error: no matching function for call to 'hash_combine'
      boost::hash_combine(h, rhs[i]);
      ^~~~~~~~~~~~~~~~~~~
/usr/include/boost/functional/hash/hash.hpp:245:17: note: candidate function [with T = std::basic_string<char>] not viable: no known conversion from 'unsigned int' to
      'std::size_t &' (aka 'unsigned long &') for 1st argument
    inline void hash_combine(std::size_t& seed, T const& v)
                ^
1 error generated.