00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00028
00029 #ifndef _CHART
00030 #define _CHART
00031
00032 #include <list>
00033 #include <vector>
00034 #include <string>
00035
00036 #include "tree.h"
00037 #include "language.h"
00038 #include "grammar.h"
00039
00043
00044 class edge : public rule {
00045
00046 private:
00048 list<string> matched;
00049
00050
00051 list<pair<int,int> > backpath;
00052
00053 public:
00055 edge(const string&, const list<string> &, const int posgov);
00056 edge();
00057
00058
00059
00061 const list<string> get_matched() const;
00063 const list<pair<int,int> > get_backpath() const;
00065 bool active() const;
00067 void shift(int,int);
00068
00069 };
00070
00074
00075 class cell : public list<edge> {};
00076
00077
00082
00083 class chart : vector<cell> {
00084
00085 private:
00086
00088 int size;
00089 const grammar *gram;
00090
00092 bool better_edge(const edge &, const edge&) const;
00094 list<pair<int,int> > cover (int a, int b) const;
00096 int index(int i, int j) const;
00099 bool can_extend(const string &, int, int) const;
00102 void find_all_rules(const edge &, cell &, int, int) const;
00104 bool check_match(const string &, const string &) const;
00105
00106 void dump() const;
00107
00108 public:
00110 chart();
00111
00113 int get_size() const;
00115 cell get_cell(int, int) const;
00116
00118 void load_sentence(const sentence &);
00119
00121 void set_grammar(const grammar &);
00122
00124 void parse();
00125
00127 parse_tree get_tree(int, int, const string & ="") const;
00128 };
00129
00130 #endif
00131
00132
00133
00134
00135