#include <vector>
#include "tlib.hh"
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) |
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 }
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; }