Back to index

scribus-ng  1.3.4.dfsg+svn20071115
Public Member Functions | Private Member Functions | Private Attributes
desaxe::RuleState Class Reference

private implementation for Digester. More...

Collaboration diagram for desaxe::RuleState:
Collaboration graph
[legend]

List of all members.

Public Member Functions

 RuleState ()
 RuleState (const RuleState &other)
 ~RuleState ()
void addRule (const Xml_string &pattern, Action action)
 adds a rule to the list
void reset ()
 sets the pattern recognizing automaton to its start state
const std::vector< rule_t > & rulesForCurrentState ()
 returns the rules which apply for the currently recognized pattern
void open (const Xml_string &tag)
 enters a new state when tag is read
void close ()
 returns to the old state when the close tag is read
void dump ()
 diagnostics

Private Member Functions

token_t createToken (const Xml_string &tok)
 assigns a unique token to each string
void makeTokens ()
automata::NFA< nfa_state_t,
token_t > * 
createNFA ()
 creates a nondeterministic automaton as base for the DFA
void compileDFA ()
 uses rules and createNFA() to create the DFA and assigns rules to states

Private Attributes

std::vector< rule_trules
 user sets these rules
std::map< Xml_string, token_ttokens
 rule patterns get broken into tokens:
std::vector< nfa_state_taccepting
 lists the accepting (NFA) states for each rule (same sequence as rules)
automata::DFA< dfa_state_t,
token_t > * 
dfa
 the dfa corresponding to the rule patterns
std::vector< dfa_state_tstateStack
 stack of dfa states
bool valid
 is true after compileDFA has run

Detailed Description

private implementation for Digester.

uses a DFA to keep track of the currently recognized pattern(s). if you have no idea what a (non)deterministic finite automaton is you probably don't want to read the rest of this code.

Definition at line 50 of file digester.cpp.


Constructor & Destructor Documentation

Definition at line 209 of file digester.cpp.

                     : rules(), dfa(NULL), stateStack(), valid(false)
{}

Definition at line 212 of file digester.cpp.

                                           : rules(other.rules), dfa(NULL), stateStack(), valid(false)
{}

Definition at line 215 of file digester.cpp.

{
       if (dfa) 
       {
              std::set<dfa_state_t> morituri(dfa->states());
              for (std::set<dfa_state_t>::iterator i=morituri.begin(); i != morituri.end(); ++i) {
                     delete *i;
              }
              delete dfa;
       }
}

Here is the call graph for this function:


Member Function Documentation

void desaxe::RuleState::addRule ( const Xml_string pattern,
Action  action 
)

adds a rule to the list

Definition at line 228 of file digester.cpp.

{
       rules.push_back(std::pair<Xml_string, Action>(pattern,action));
       valid = false;
}

Here is the caller graph for this function:

void desaxe::RuleState::close ( ) [inline]

returns to the old state when the close tag is read

Definition at line 296 of file digester.cpp.

{
       stateStack.pop_back();
}

Here is the caller graph for this function:

void desaxe::RuleState::compileDFA ( ) [private]

uses rules and createNFA() to create the DFA and assigns rules to states

Definition at line 464 of file digester.cpp.

{      
       // build NFA:
       makeTokens(); 
       automata::NFA<nfa_state_t, token_t> *nfa = createNFA();
       // make deterministic:
       CreateDFAState create(rules, accepting);
//     dfa = nfa->constructDFA<dfa_state_t>(create);        // wont work
//     dfa = nfa->constructDFA<dfa_state_t>(create_fun);    // works
//     std::set<nfa_state_t> arg;
//     dfa_state_t res = create(arg);                       // works
//     create("bullshit");                                  // never works :-)
       dfa = nfa->constructDFA<dfa_state_t,CreateDFAState&>(create);   // finally
       delete nfa;
       valid = true;
}

Here is the call graph for this function:

Here is the caller graph for this function:

creates a nondeterministic automaton as base for the DFA

maps paths uniquely to an nfa_state

Definition at line 328 of file digester.cpp.

{
       using automata::NFA;
       
       std::map<path_t, nfa_state_t> nfa_states;
       nfa_states.clear();

       path_t prefix;

       // START and EMPTY are both: tokens and nfa_states
       prefix.push_back(START);
       nfa_states[prefix] = START;
       
       prefix[0] = EMPTY;
       nfa_states[prefix] = EMPTY;
       
       std::set<nfa_state_t> deflt;
       deflt.insert(EMPTY);
       
       NFA<nfa_state_t, token_t> *nfa = new NFA<nfa_state_t, token_t>(START, deflt);
       
       nfa->addState(EMPTY);
       nfa->addInput(ANY);
       nfa->addTransition(EMPTY, ANY, EMPTY);

       for (unsigned int i = 0; i < rules.size(); ++i)
       {
              const std::string currPattern(fromXMLString(rules[i].first));
              const unsigned int len = currPattern.length();
              int pos;
              nfa_state_t lastState;
              
              // determine if this is a start pattern
              prefix.resize(1);
              if (currPattern[0] == '/') {
                     prefix[0] = START;
                     pos = 1;
                     lastState = START;
              }
              else {
                     prefix[0] = EMPTY;
                     pos = 0;
                     lastState = EMPTY;
              }
              
//            std::cerr << "looking at pattern: " << currPattern << "\n";
              // for all prefixes
              do {
                     std::string::size_type pos2 = currPattern.find('/', pos);
                     if (pos2 == std::string::npos)
                            pos2 = len;
                     
                     std::string diff(currPattern.substr(pos, pos2-pos));
                     token_t tok = createToken(fromSTLString(diff));
//                   std::cerr << pos << "-" << pos2 << "\t: " << diff << " = " << tok << "\n";

                     // create loop if REPEAT token
                     if (tok == REPEAT) {
                            nfa->addTransition(lastState, ANY, lastState); //FIXME: that's wrong, need to create repeating state
//                          std::cerr << "T " << lastState << "--*-->" << lastState << "\n";
                            pos = pos2 + 1;
                            continue;
                     }
                     
                     prefix.push_back(tok);
                     // create new state if necessary
                     nfa_state_t nstate;
                     if (nfa_states.find(prefix) != nfa_states.end()) {
                            nstate = nfa_states[prefix];
                     }
                     else {
                            nstate = nfa_states.size();
                            nfa->addState(nstate);
                            nfa_states[prefix] = nstate;
                     }
                     // add transition
                     nfa->addInput(tok);
                     nfa->addTransition(lastState, tok, nstate);
//                   std::cerr << "T " << lastState << "--(" << tok << ")-->" << nstate << "\n";
                     lastState = nstate;
                     pos = pos2 + 1;
              } while(pos < signed(len));
              accepting.push_back(lastState);
//            std::cerr << "accepted in " << lastState << "\n";

              // copy all transition from EMPTY to all other states
              const NFA<nfa_state_t, token_t>::Transitions& transFromEmpty(nfa->transitions(EMPTY));
              std::set<nfa_state_t>::const_iterator it, st;
              NFA<nfa_state_t, token_t>::Transitions::const_iterator tr;
              for (it = nfa->states().begin(); it != nfa->states().end(); ++it) {
                     if (*it == EMPTY)
                            continue;
                     for (tr = transFromEmpty.begin(); tr != transFromEmpty.end(); ++tr)
                            for (st = tr->second.begin(); st != tr->second.end(); ++st)
                                   nfa->addTransition(*it, tr->first, *st);
              }
              
              // ANY transitions
              const std::set<token_t>& inputs(nfa->inputs());
              std::set<token_t>::const_iterator tok;
              for (it = nfa->states().begin(); it != nfa->states().end(); ++it) {
                     const std::set<nfa_state_t>& anyStates(nfa->next(*it, ANY));
                     for (st = anyStates.begin(); st != anyStates.end(); ++st)
                            for (tok=inputs.begin(); tok != inputs.end(); ++tok)
                                   if (*tok != ANY)
                                          nfa->addTransition(*it, *tok, *st);
              }
       }
       return nfa;
}

Here is the call graph for this function:

Here is the caller graph for this function:

assigns a unique token to each string

Definition at line 319 of file digester.cpp.

{
       if (tokens.find(tok) == tokens.end())
              tokens[tok] = tokens.size() + 1;
       return tokens[tok];
}

Here is the caller graph for this function:

diagnostics

Definition at line 244 of file digester.cpp.

{
       std::cout << "Rules:\n";
       for (unsigned int r=0; r<rules.size(); ++r) {
              std::cout << r << ":\t\"" << rules[r].first << "\" accepted in  (" << accepting[r] << ")\n";
       }
       std::cout << "\nTokens:\n";
       for (std::map<Xml_string, token_t>::iterator it=tokens.begin(); it!=tokens.end(); ++it) {
              std::cout << it->first << ":\t--> " << it->second << "\n";
       }
       std::cout << "\nAutomaton:\n";
       const std::set<dfa_state_t>& states(dfa->states());
       const std::set<token_t>& inputs(dfa->inputs());
       std::cout << "STATE";
       for (std::set<token_t>::const_iterator i=inputs.begin(); i != inputs.end(); ++i) {
              std::cout << "\t" << *i;
       }
       std::cout << "\tRULES\n\n";
       for (std::set<dfa_state_t>::const_iterator s=states.begin(); s!=states.end(); ++s) {
              std::cout << (*s)->ID;
              for (std::set<token_t>::const_iterator i=inputs.begin(); i!=inputs.end(); ++i) {
                     dfa_state_t nstate = dfa->next(*s,*i);
                     std::cout << "\t";
                     if (nstate)
                            std::cout << nstate->ID;
                     else
                            std::cout << "--";
              }
              for (std::vector<rule_t>::iterator rs=(*s)->rules.begin(); rs!=(*s)->rules.end(); ++rs)
                     std::cout << "\t\"" << rs->first << "\"";
              std::cout << "\n";
       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void desaxe::RuleState::makeTokens ( ) [private]

Definition at line 308 of file digester.cpp.

{
       tokens.clear();
       tokens[""] = EMPTY;
       tokens["/"] = START;
       tokens["*"] = ANY;
       tokens["**"] = REPEAT;
}

Here is the caller graph for this function:

void desaxe::RuleState::open ( const Xml_string tag) [inline]

enters a new state when tag is read

Definition at line 279 of file digester.cpp.

{
       dfa_state_t nstate = dfa->next(stateStack.back(), tokens[tag]);
       assert(nstate != NULL);
#ifdef DESAXE_DEBUG
       std::cerr << "to state " << nstate->ID << "\n";  
#endif
       if (nstate->ID == dfa->deflt()->ID) {
              nstate = dfa->next(stateStack.back(), ANY);
#ifdef DESAXE_DEBUG
              std::cerr << "empty, trying any:" << nstate->ID << "\n"; 
#endif
       }
       stateStack.push_back(nstate);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void desaxe::RuleState::reset ( ) [inline]

sets the pattern recognizing automaton to its start state

Definition at line 236 of file digester.cpp.

{
       stateStack.clear();
       if (!valid)
              compileDFA();
       stateStack.push_back(dfa->start());
}

Here is the call graph for this function:

Here is the caller graph for this function:

const std::vector< rule_t > & desaxe::RuleState::rulesForCurrentState ( ) [inline]

returns the rules which apply for the currently recognized pattern

Definition at line 303 of file digester.cpp.

{
       return stateStack.back()->rules;
}

Here is the caller graph for this function:


Member Data Documentation

std::vector<nfa_state_t> desaxe::RuleState::accepting [private]

lists the accepting (NFA) states for each rule (same sequence as rules)

Definition at line 75 of file digester.cpp.

the dfa corresponding to the rule patterns

Definition at line 77 of file digester.cpp.

std::vector<rule_t> desaxe::RuleState::rules [private]

user sets these rules

Definition at line 70 of file digester.cpp.

stack of dfa states

Definition at line 79 of file digester.cpp.

rule patterns get broken into tokens:

Definition at line 73 of file digester.cpp.

is true after compileDFA has run

Definition at line 91 of file digester.cpp.


The documentation for this class was generated from the following file: