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
Automaton *	make_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().

{
  int n = A->n_rules();
  vector<Subst> subst(n, Subst());
  /* perform matching, record variable substitutions */
#ifdef DEBUG
  cerr << "automaton " << A << ", state " << s << ", start match on arg: " << *X << endl;
#endif
  s = apply_pattern_matcher_internal(A, s, X, subst);
  C = nil;
  if (s < 0)
    /* failed match */
    return s;
  /* process variable substitutions */
  list<Rule>::const_iterator r;
  for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) {
    // all rules still active in state s
    if (!isBoxError(E[r->r])) { // and still viable
      Subst::const_iterator assoc;
      for (assoc = subst[r->r].begin(); assoc != subst[r->r].end(); assoc++) {
    Tree Z, Z1 = subtree(X, 0, assoc->p);
    if (searchIdDef(assoc->id, Z, E[r->r])) {
      if (Z != Z1) {
        /* failed nonlinearity, add to the set of nonviable rules */
#ifdef DEBUG
      cerr << "state " << s << ", rule #" << r->r << ": " <<
        *assoc->id << " := " << *Z1 << " *** failed *** old value: " <<
        *Z << endl;
#endif
        E[r->r] = boxError();
      }
    } else {
      /* bind a variable for the current rule */
#ifdef DEBUG
      cerr << "state " << s << ", rule #" << r->r << ": " <<
        *assoc->id << " := " << *Z1 << endl;
#endif
      E[r->r] = pushValueDef(assoc->id, Z1, E[r->r]);
    }
      }
    }
  }
  if (A->final(s)) {
    /* if in a final state then return the right-hand side together with the
       corresponding variable environment */
    for (r = A->rules(s).begin(); r != A->rules(s).end(); r++) // all rules matched in state s
      if (!isBoxError(E[r->r])) { // and still viable
    /* return the rhs of the matched rule */
    C = closure(A->rhs[r->r], nil, nil, E[r->r]);
#ifdef DEBUG
    cerr << "state " << s << ", complete match yields rhs #" << r->r <<
      ": " << *A->rhs[r->r] << endl;
#endif
    return s;
      }
    /* if none of the rules were matched then declare a failed match */
#ifdef DEBUG
    cerr << "state " << s << ", *** match failed ***" << endl;
#endif
    return -1;
  }
#ifdef DEBUG
  cerr << "state " << s << ", successful incomplete match" << endl;
#endif
  return s;
}

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, State::rules, and Automaton::rules().

Referenced by evalCase().

{
  Automaton *A = new Automaton;
  int n = len(R), r = n;
  State *start = new State;
  Tree rule, rest;
  vector<Tree> rules(n, (Tree)NULL);
  vector< vector<Tree> > testpats(n);
  while (isCons(R, rule, rest)) {
    rules[--r] = rule;
    R = rest;
  }
  for (r = 0; r < n; r++) {
    Tree lhs, rhs;
    if (isCons(rules[r], lhs, rhs)) {
      Tree pat, rest;
      int m = len(lhs), i = m;
      vector<Tree> pats(len(lhs), (Tree)NULL);
      State *state0 = new State, *state = state0;
      A->rhs.push_back(rhs);
      while (isCons(lhs, pat, rest)) {
    pats[--i] = pat;
    lhs = rest;
      }
      testpats[r] = pats;
      for (i = 0; i < m; i++) {
    Path p;
    state = make_state(state, r, pats[i], p);
      }
      Rule rule(r, NULL);
      state->rules.push_back(rule);
      merge_state(start, state0);
      delete state0;
    }
  }
  A->build(start);
  /* Check for shadowed rules. Note that because of potential nonlinearities
     it is *not* enough to just check the rule lists of final states and
     determine whether they have multiple matched rules. */
  for (r = 0; r < n; r++) {
    int s = 0, m = (int)testpats[r].size();
    Tree C;
    vector<Tree> E(n, nil);
    /* try to match the lhs of rule #r */
    for (int i = 0; i < m; i++) {
      s = apply_pattern_matcher(A, s, testpats[r][i], C, E);
      if (s < 0) break;
    }
    if (A->final(s)) {
      list<Rule>::const_iterator ru;
      for (ru = A->rules(s).begin(); ru != A->rules(s).end(); ru++)
    if (!isBoxError(E[ru->r]))
      if (ru->r < r) {
        /* Lhs of rule #r matched a higher-priority rule, so rule #r may
           be shadowed. */
        Tree lhs1, rhs1, lhs2, rhs2;
        if (isCons(rules[ru->r], lhs1, rhs1) &&  isCons(rules[r], lhs2, rhs2)) {
            cerr    << "WARNING : shadowed pattern-matching rule: "
                << boxpp(reverse(lhs2)) << " => " << boxpp(rhs2) << ";"
                << " previous rule was: " 
                << boxpp(reverse(lhs1)) << " => " << boxpp(rhs1) << ";"
                << endl;
        } else {
            cerr << "INTERNAL ERROR : " << __FILE__ << ":" << __LINE__ << endl;
            exit(1);
        }
      } else if (ru->r >= r)
        break;
    }
  }
#ifdef DEBUG
  cerr << "automaton " << A << endl << *A << "end automaton" << endl;
#endif
  return A;
}

Here is the call graph for this function:

Here is the caller graph for this function: