patternmatcher.hh File Reference

#include <vector>
#include "tlib.hh"
Include dependency graph for patternmatcher.hh:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

Automatonmake_pattern_matcher (Tree R)
int apply_pattern_matcher (Automaton *A, int s, Tree X, Tree &C, vector< Tree > &E)

Function Documentation

int apply_pattern_matcher ( Automaton A,
int  s,
Tree  X,
Tree C,
vector< Tree > &  E 
)

Definition at line 660 of file patternmatcher.cpp.

References apply_pattern_matcher_internal(), boxError(), closure(), Automaton::final(), isBoxError(), Automaton::n_rules(), nil, pushValueDef(), Automaton::rhs, Automaton::rules(), searchIdDef(), subst(), and subtree().

Referenced by applyList(), and make_pattern_matcher().

00665 {
00666   int n = A->n_rules();
00667   vector<Subst> subst(n, Subst());
00668   /* perform matching, record variable substitutions */
00669 #ifdef DEBUG
00670   cout << "automaton " << A << ", state " << s << ", start match on arg: " << *X << endl;
00671 #endif
00672   s = apply_pattern_matcher_internal(A, s, X, subst);
00673   C = nil;
00674   if (s < 0)
00675     /* failed match */
00676     return s;
00677   /* process variable substitutions */
00678   list<Rule>::const_iterator r;
00679   for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) {
00680     // all rules still active in state s
00681     if (!isBoxError(E[r->r])) { // and still viable
00682       Subst::const_iterator assoc;
00683       for (assoc = subst[r->r].begin(); assoc != subst[r->r].end(); assoc++) {
00684     Tree Z, Z1 = subtree(X, 0, assoc->p);
00685     if (searchIdDef(assoc->id, Z, E[r->r])) {
00686       if (Z != Z1) {
00687         /* failed nonlinearity, add to the set of nonviable rules */
00688 #ifdef DEBUG
00689       cout << "state " << s << ", rule #" << r->r << ": " <<
00690         *assoc->id << " := " << *Z1 << " *** failed *** old value: " <<
00691         *Z << endl;
00692 #endif
00693         E[r->r] = boxError();
00694       }
00695     } else {
00696       /* bind a variable for the current rule */
00697 #ifdef DEBUG
00698       cout << "state " << s << ", rule #" << r->r << ": " <<
00699         *assoc->id << " := " << *Z1 << endl;
00700 #endif
00701       E[r->r] = pushValueDef(assoc->id, Z1, E[r->r]);
00702     }
00703       }
00704     }
00705   }
00706   if (A->final(s)) {
00707     /* if in a final state then return the right-hand side together with the
00708        corresponding variable environment */
00709     for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) // all rules matched in state s
00710       if (!isBoxError(E[r->r])) { // and still viable
00711     /* return the rhs of the matched rule */
00712     C = closure(A->rhs[r->r], nil, nil, E[r->r]);
00713 #ifdef DEBUG
00714     cout << "state " << s << ", complete match yields rhs #" << r->r <<
00715       ": " << *A->rhs[r->r] << endl;
00716 #endif
00717     return s;
00718       }
00719     /* if none of the rules were matched then declare a failed match */
00720 #ifdef DEBUG
00721     cout << "state " << s << ", *** match failed ***" << endl;
00722 #endif
00723     return -1;
00724   }
00725 #ifdef DEBUG
00726   cout << "state " << s << ", successful incomplete match" << endl;
00727 #endif
00728   return s;
00729 }

Here is the call graph for this function:

Here is the caller graph for this function:

Automaton* make_pattern_matcher ( Tree  R  ) 

Definition at line 479 of file patternmatcher.cpp.

References apply_pattern_matcher(), Automaton::build(), Automaton::final(), isBoxError(), isCons(), len(), make_state(), merge_state(), nil, reverse(), Automaton::rhs, Automaton::rules(), and State::rules.

Referenced by evalCase().

00482           :
00483 
00484    Rules    ::= cons Rule (cons Rule ... nil)
00485    Rule     ::= cons Lhs Rhs
00486    Lhs      ::= cons Pattern (cons Pattern ... nil)
00487    Pattern  ::= Tree (parameter pattern)
00488    Rhs      ::= Tree
00489 
00490    NOTE: The lists of rules and patterns are actually delivered in reverse
00491    order by the parser, so we have to reverse them on the fly. */
00492 {
00493   Automaton *A = new Automaton;
00494   int n = len(R), r = n;
00495   State *start = new State;
00496   Tree rule, rest;
00497   vector<Tree> rules(n, (Tree)NULL);
00498   vector< vector<Tree> > testpats(n);
00499   while (isCons(R, rule, rest)) {
00500     rules[--r] = rule;
00501     R = rest;
00502   }
00503   for (r = 0; r < n; r++) {
00504     Tree lhs, rhs;
00505     if (isCons(rules[r], lhs, rhs)) {
00506       Tree pat, rest;
00507       int m = len(lhs), i = m;
00508       vector<Tree> pats(len(lhs), (Tree)NULL);
00509       State *state0 = new State, *state = state0;
00510       A->rhs.push_back(rhs);
00511       while (isCons(lhs, pat, rest)) {
00512     pats[--i] = pat;
00513     lhs = rest;
00514       }
00515       testpats[r] = pats;
00516       for (i = 0; i < m; i++) {
00517     Path p;
00518     state = make_state(state, r, pats[i], p);
00519       }
00520       Rule rule(r, NULL);
00521       state->rules.push_back(rule);
00522       merge_state(start, state0);
00523       delete state0;
00524     }
00525   }
00526   A->build(start);
00527   /* Check for shadowed rules. Note that because of potential nonlinearities
00528      it is *not* enough to just check the rule lists of final states and
00529      determine whether they have multiple matched rules. */
00530   for (r = 0; r < n; r++) {
00531     int s = 0, m = testpats[r].size();
00532     Tree C;
00533     vector<Tree> E(n, nil);
00534     /* try to match the lhs of rule #r */
00535     for (int i = 0; i < m; i++) {
00536       s = apply_pattern_matcher(A, s, testpats[r][i], C, E);
00537       if (s < 0) break;
00538     }
00539     if (A->final(s)) {
00540       list<Rule>::const_iterator ru;
00541       for (ru = A->rules(s).begin(); ru != A->rules(s).end(); ru++)
00542     if (!isBoxError(E[ru->r]))
00543       if (ru->r < r) {
00544         /* Lhs of rule #r matched a higher-priority rule, so rule #r may
00545            be shadowed. */
00546         Tree lhs1, rhs1, lhs2, rhs2;
00547         if (isCons(rules[ru->r], lhs1, rhs1) &&  isCons(rules[r], lhs2, rhs2)) {
00548             cerr    << "WARNING : shadowed pattern-matching rule: "
00549                 << boxpp(reverse(lhs2)) << " => " << boxpp(rhs2) << ";"
00550                 << " previous rule was: " 
00551                 << boxpp(reverse(lhs1)) << " => " << boxpp(rhs1) << ";"
00552                 << endl;
00553         } else {
00554             cerr << "INTERNAL ERROR : " << __FILE__ << ":" << __LINE__ << endl;
00555             exit(1);
00556         }
00557       } else if (ru->r >= r)
00558         break;
00559     }
00560   }
00561 #ifdef DEBUG
00562   cout << "automaton " << A << endl << *A << "end automaton" << endl;
00563 #endif
00564   return A;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Generated on Wed Apr 28 23:45:54 2010 for FAUST compiler by  doxygen 1.6.3