More Efficient Pattern-Matching Automata
for Overlapping Patterns
Nadia Nedjah*, Colin D. Walter and Stephen E. Eldridge
Computation Dept., UMIST, PO. Box 88, Manchester M60 1QD, UK.
{nn, cdw, see} @sna.co.umist.ac.uk

www.co.umist.ac.uk

Abstract
Pattern-matching is a fundamental feature in many applications such as functional programming,
logic programming, term rewriting and rule-based expert systems. Usually, patterns are preprocessed into a deterministic finite automaton. Using such an automaton allows one todetermine the matched pattern(s) by a single scan of the input term. The matching automaton istypically based on left-to-right traversal of patterns. With overlapping patterns a subject term
may be an instance of more than one pattern. To select the pattern to use, a priority rule isusually engaged.
The pre-processing of the patterns adds new patterns which are instances of the originalones. When the original patterns overlap, some of the instances supplied may be irrelevant forthe matching process. They may cause an unnecessary increase in the space requirements of theautomaton and may also reduce the time efficiency of the matching process. Here, we devise a
new pre-processing operation that recognises and avoids such irrelevant instances and hence
improves space and time requirements for the matching automaton.
Keywords: Pattern-matching, tree automaton, closure, compilation.

1. Introduction
Pattern-matching is an important operation in several applications such as functional, equational
and logic programming [5,11], theorem proving [4] and rule-based expert systems [3]. It can beachieved as in lexical analysis by using a finite automaton [2,6,7,10,12]. In order to avoid
backtracking over symbols already examined, new patterns are added. These correspond tooverlaps in the scanned prefixes of original patterns. When patterns overlap, some of the added
patterns may be irrelevant to the matching process.

Sekar et al. [12] use the notion ofrepresentative pattern sets to compute smaller automata for pattern-matching by deleting such
patterns. As each automaton node is constructed, their algorithm eliminates a pattern π from thecurrent matching set whenever a match for π implies a match for a pattern of higher priority.
This deletion is a computationally expensive operation and loses some potentially useful feedback to the programmer. In this paper, we focus on improving these aspects by leaving theremoval of irrelevant patterns till the end of the construction. This usually results in more
efficient compilation.
*

Author sponsored by the British Council and the Algerian Ministry for High Education.

Proc. Internat. Workshop on the Implementation of Functional Languages, St Andrews, Sept 1997, pp 341-350

First, we recall from [10] a method for generating a deterministic tree matching automaton fora given pattern set. Although the generated automaton is efficient since it avoids symbol reexamination, it may contain unnecessary branches. Part of this is due to duplication ofequivalent nodes. [10] provides an efficient method for recognising most of these and so obtains
an upper bound for the size of an equivalent, partially minimised automaton which improves on
the bounds in [6] and [12]. The other main reason for excessive automaton size is the presence,or introduction during the construction process, of overlapping patterns which are not eventuallymatched. Here, a smaller automaton may be obtained by pruning back from final nodes.

2. Notation
In this section, we recall the notation and concepts that will be used in the rest of the paper.
Symbols in a term are either function or variable symbols. The non-empty set of function
symbols F = {a, b, f, g, ...} is ranked i.e., every function symbol f in F has an arity which is thenumber of its arguments and is denoted #f. A term is either a constant, a variable, or has theform ft1t2...t#f where each ti, 1 ≤ i ≤ #f, is itself a term. We abbreviate terms by removing theusual parentheses and commas. This is unambiguous in our examples since the function arities
will be kept unchanged throughout, namely #f = 3, #g = 1, #a = #b = 0. A term containing novariables is said to be a ground term. Throughout, variable occurrences are replaced by ω since
the actual symbols are irrelevant here. (Often _ is used instead.) The justification for this is that
we assume all patterns are linear terms, i.e. each variable symbol can occur at most once in each.
Pattern sets will be denoted by L and patterns by π1, π2, ..., or simply by π. A term t is said to be
an instance of a (linear) pattern π if t can be obtained from π by replacing the variables of π bycorresponding subterms of t.
Definition 2.1: A matching item is a triple r:α•β where αβ is a term and r is a rule label
identifying a pattern in the original, prioritised pattern set. The label identifies the origin of theterm αβ and hence, in a term rewriting system, the rewrite rule which has to be applied when

αβ is matched. The label is not written explicitly below except where necessary. The metasymbol • is called the matching dot, and α and β are called the prefix and suffix respectively. A
final matching item is one of the form α•.
Throughout this paper left-to-right traversal order is used. So the matching item •β represents
the initial state prior to matching the pattern β. In general, the matching item α•β denotes thatthe symbols in α have been matched and those in β have not yet been recognised. Finally, thematching item α• is reached on successfully matching the whole pattern α.
Definition 2.2: A set of matching items in which all the items have the same prefix is called amatching set. A matching set in which all the items have an empty prefix is called an initialmatching set whereas a matching set in which all the items have an empty suffix is called a final
matching set.

N. Nedjah, C.D. Walter & S.E. Eldridge

Definition 2.3: For a set L of pattern suffixes and any symbol s, let L\s denote the set of pattern
suffixes obtained by removing the initial symbol s from those members of L which commencewith s and excluding the other members of L. Then, for f ∈ F define Lω and Lf by:
L\ω

Lω =
Lf

=

 L \ f ∪ ω # f L \ ω if L \ f ≠ ∅∅otherwise

where ω#f denotes a string of #f symbols ω and ∅ is the empty set. The closure L of a pattern
set L is then defined recursively by Gräf [6] as follows:

L =

 L


 ∪ s Lss ∈F∪{ω}

if L = {ε} or L = ∅otherwise

Roughly speaking, with two item suffixes of the form fα and ωβ we always add the suffixfω β in order to postpone by one more symbol the decision between these two patterns.
#fOtherwise backtracking might be required to match ωβ if input f leads to failure to match fα.

3. Tree Matching Automata
In this section, we briefly recall from [10] a practical method to construct a deterministic tree
matching automaton for a prioritised overlapping pattern set. The pattern set L is extended to its
closure L while generating the matching automaton.
The automaton states are labelled by matching sets which consist of original patterns whose
prefixes match the current input prefix, together with extra instances of the patterns which are
added to avoid backtracking in reading the input. In particular, the matching set for the initialstate contains the initial matching items formed from the original patterns and labelled by therules associated with them. The state transition function is denoted by δ. For each symbol s ∈F∪{ω} and state S with matching set M, the new state δ(S,s) has matching set δ(M,s) derived byapplying the composition of the functions accept and close defined in Figure 3.1.

Proc. Internat. Workshop on the Implementation of Functional Languages, St Andrews, Sept 1997, pp 341-350

accept(M,s) = {r:αs•β  r:α•sβ ∈ M }close(M)= M ∪ {r:α•fω#fµ  r:α•ωµ ∈ M and∃ q:α•fλ∈M for some suffix λ and f∈F }δ(M,s)= close( accept(M,s) )Figure 3.1: Automata Transition Function from [10].
The items obtained by recognising the symbols in those patterns of M where s is the next
symbol form the set accept(M,s). However, the set δ(M,s) may contain more items. The
presence of two items α•ωµ and α•fλ in M creates a non-deterministic situation since thevariable ω could be matched by a term having f as head symbol. The item r:α•fω#fµ is added toremove this non-determinism and avoid backtracking. Its label simply keeps account of theoriginating pattern from which it was derived. Now the f-transition can be taken when f is thenext input symbol regardless of which of the two patterns, if any, is matched. The transition
function δ thus implements simply the main step in the closure operation described by Gräf [6]and set out in the previous section. Hence the full pattern set resulting from all additions during
the automaton construction coincides with the closure operation of Definition 2.3.
Non-determinism is worst where the input can end up matching the whole of two different
patterns. Then we need a priority rule to determine which pattern to select.

Definition 3.2: A pattern set L is overlapping if there is a ground term that is an instance of atleast two distinct patterns in L. Otherwise, L is non-overlapping.

Definition 3.3: A priority rule is a partial ordering on patterns such that if π1 and π2 are distinct
overlapping patterns then either π1 has higher priority than π2 or π2 has higher priority than π1.
In the latter case, we write π1 < π2.
Since the rule labels of items identify patterns from a prioritised pattern set, we can write r1 <r2 for labels r1 and r2. When a final state is reached, if several patterns have been successfully
matched, then the priority rule is engaged to select the one of highest priority. An example is the
textual priority rule which is used in the majority of functional languages [1,8,9,13]. Among thematched patterns, the rule chooses the pattern that appears first in the text. Whatever priority
rule is used, we will apply the word match only to the pattern of highest priority which ismatched:Definition 3.4: For a prioritised pattern set L and pattern π ∈ L, the term t is said to match π in
L if, and only if, t is an instance of π but not an instance of any other pattern in L of higher
priority than π.

N. Nedjah, C.D. Walter & S.E. Eldridge

Example 3.5: Let L = {1:faωω, 2:fωaa, 3:fωba, 4:fgωgωb} be the pattern set where #f = 3, #g =1 and #a = #b = 0, as throughout this paper. Assuming a textual priority rule, the matching
automaton for L is given in Figure 3.6. Transitions corresponding to failures are omitted. Eachstate is labelled with its matching set. In the construction process, each new item is associatedwith the rule from which it is directly derived and whose pattern it is known to match. So, an
added item α•fω#fβ is associated with the same rule as is its parent α•ωβ. Items added by close
are underneath a horizontal line in the state. At the final nodes, several items may be matched.
Then the highest priority matching rule must be chosen, but the others appear in parentheses.
When this happens, it indicates the occurrence of what we call irrelevancy in the next section.
During pattern matching, an ω-transition is only taken when there is no other available transition
which accepts the current symbol; these transitions might more aptly be labelled “else” when
there are other alternatives starting at the parent node. With care, the automaton can usually be
used to drive the pattern-matching process irrespective of the chosen term rewriting strategy.
0

1: • fa ωω
2: • fωaa
3: • fωba
4: • fg ωgωb
f

1

a

2

a

ω

a

8

b
7

13

1: faa ω• 14
1: faba•(3:faba•)bω

9

2: fωa • a 3: fωb • aaa
16

1: faω • ω
2: faa • a
3: fab • aω
1: faa • ω 11
1: fab • ωω 1: faωω •ωaa

1: faaa•(2:faaa•)4

4: fg • ωgωb
2: fg • ωaa
3: fg • ωba

2: fω • aa
3: fω • ba

6

12

g

3

1: fa • ωω
2: fa • aa
3: fa • ba
1: fa • a ω
1: fa • b ω
5

1: f • a ωω
2: f • ωaa
3: f • ωba
4: f • g ωgωb
2: f • aaa
3: f • aba
2: f • g ωaa
3: f • g ωbaω

4: fg ω • gωb
2: fgω • aa
3: fgω • ba

17

2: fωaa•

3: fωba•
18

15

1: fab ω•

21

10

a

19

g

b

13

2: fg ωa •a 4: fg ωg • ωb 3: fg ωb • a
ω
a
a 23
22
2: fg ωaa• 4: fg ωgω • bb
24

3: fg ωba•

4: fg ωgωb•

Figure 3.6: Matching Automaton for {1:faωω, 2:fωaa, 3:fωba, 4:fgωgωb}.

Proc. Internat. Workshop on the Implementation of Functional Languages, St Andrews, Sept 1997, pp 341-350

4. Reduced Matching Automaton for Overlapping Patterns
We now treat the observation that the close function of Figure 3.1 may add more items than itneeds when the patterns are overlapping. For example, in Figure 3.6 consider the items 2:f•aaa
and 3:f•aba which close adds to state 1 but which are finally ignored in states 12 and 14. Everyterm matching these items is eventually associated with derivatives of the higher priority item
1:f•aωω, also of state 1, and so the two items could have safely been omitted. We return to thisexample again after several definitions.
A position in a term is a path specification which identifies a node in the parse tree of theterm. For a term t and a position p in this term, we denote by t[p] the symbol at position p in t.

Definition 4.1: A term t is said to be more general than (a term) t′ at (the position) p if, andonly if, the symbol t[p] is ω, t′[p] is a function symbol and the prefixes of t and t′ ending
immediately before p are the same. We will also say t is initially more general than t′ if t ismore general than t′ at the first position for which the symbols of t and t′ differ.
It is the existence of a pair of terms with one being more general than the other at thematching position that is the condition for the function close to add in a new item. The priority
rule of the original rule set must be extended to these new items. The following definition
enables us to associate a unique item of highest priority from amongst all those which patternmatch a given term: if there is a unique pattern-matched item whose rule has highest priority
then that is chosen; otherwise, when there are several pattern-matched items associated withrules of maximal priority, it turns out that those items must all derive from the same original
pattern and we can select the initially most general. (Any other uniquely defined choice would
also be acceptable, but this is the most convenient in what follows.)

Definition 4.2: Item r:α•β has higher priority than item r′:α′•β′ if r has higher priority than r′
or r = r′ and αβ is initially more general than α′β′. For a matching set M and item r:α•β ∈ M,
the term t is said to match r:α•β in M if, and only if, t is an instance of αβ but not an instance of
any other item in M of higher priority.
In fact, for a ground term there will always be a unique choice for the (highest priority)
matching item because each matching set in the automaton will contain a matching instance of
the unique original pattern which the priority rule identifies as the match to choose for the input
term. Note that although the pattern αβ of the item r:α•β will always be an instance of thepattern of rule r, instances of it may actually match a pattern of higher priority. Such a higher
priority rule could not have been used in generalising the priority rule to all terms and items
because it is not uniquely defined; different instances of a non-ground term may match different
patterns. The above definition suffices because for any given input term, each matching set willcontain a matching item associated with the correct rule of maximal priority. It is now possible

N. Nedjah, C.D. Walter & S.E. Eldridge

to determine which patterns are useful for matching sets to include. Indeed, we can start byconsidering the usefulness of each pattern in the initial pattern set:

Definition 4.3: Suppose L∪{π} is a prioritised pattern set. Then π is said to be relevant for L if
there is a term that matches π in L∪{π} in the sense of Definition 3.4. Otherwise, π is irrelevant
for L. Similarly, an item π is relevant for (the matching set) M if there is a term that matches π
in M∪{π} in the sense of Definition 4.2.
Clearly, any term that matches an element of a pattern set, respectively item of a matchingset, will still have that property even when an irrelevant pattern, respectively item, is removed.
We can therefore immediately prune irrelevant patterns one by one from the initial pattern set
until every remaining pattern is relevant to the remaining pattern set, and do the same for eachmatching subset generated by accept. Sekar et al. [12] call the resulting sets representative sets.
As observed above, the function close of Figure 3.1 may certainly supply items that are
irrelevant for subsequent matching.

Indeed, all additional items which close supplies areirrelevant for the current state although they may be relevant to later matching sets; neverthelesswe need them for the child states to avoid backtracking. The uselessness of some items for
subsequent matching may happen when the original pattern set contains overlapping patterns
with more general ones having lower priorities. For instance, in Example 3.5, the original
patterns 1:faωω and 2:fωaa are overlapping, 2:fωaa is more general than 1:faωω at position 1 yet
1:faωω has higher priority. The close function supplies the items 2:f•aaa, 3:f•aba and two others
to state 1. Then accepting symbol a would yield a superset of {1:fa•ωω, 2:fa•aa, 3:fa•ba}. At
this stage, based only on the item 1:fa•ωω a match for faωω can be announced and hence items
2:fa•aa and 3:fa•ba are redundant, and indeed irrelevant under the definition above.
In order to avoid irrelevant items, we can follow Sekar [12] and define a new function rel
which, given a matching set M, removes all the irrelevant items. A definition of this function is
given in Figure 4.4. For a matching set M and a symbol s ∈ F∪{ω}, the automaton transition
function is now defined by δ(M,s) = close(rel(accept(M,s))).

This removes the items

corresponding to rules 2 and 3 from state 2 in Figure 3.6 and yields the reduced automaton of
Figure 4.6.
rel(M) = any maximal subset S of M such that
if π ∈ M\S then π is irrelevant for S.

Figure 4.4: Rel function which deletes irrelevant items.
Checking for relevance is mostly straightforward. Consider items in descending order ofpriority. Suppose r:α•β is being considered for relevance in M = accept(M0, s). Any itemr′:α′•β′ ∈ M may be ignored as far as r:α•β is concerned if the priority rules do not relate r andr′. This is because α•β and α′•β′ are special cases of the patterns r and r′ respectively, whichcannot overlap. So, such r′:α′•β′ do not affect the relevance of r:α•β. At the opposite extreme,Proc. Internat. Workshop on the Implementation of Functional Languages, St Andrews, Sept 1997, pp 341-350

suppose there is an item r′:α′•β′ ∈ M for which r = r′. Then both items are instances of thepattern of rule r with prefix α = α′. Both β and β′ must be the complementary suffix of thepattern of rule r preceded by the same number of ωs (see [10]). So, the items are identical andr:α•β is irrelevant. Indeed, this argument shows that rel will produce a set in which every item
is associated with a different rule. This leaves the situation where all items r′:α′•β′ ∈ Maffecting the relevance of r:α•β satisfy r < r′. All items have the same prefix α followed bysome inserted occurrences of ω, followed by a suffix of the named rule. Hence, the most generalunifier of r:α•β and any r′:α′•β′ can be found easily from that of r and r′, which can becalculated initially once for all. Standard techniques (see [12]) enable the relevance or not ofr:α•β to be concluded. However, we feel it worth noting that in a real application, especially ina typed system, it is often the case that the number of function symbols which can be used at agiven position in a term is finite. This means that it may be possible to cover an item r:α•βwhich contains ω at some position with items of higher priority containing a function symbol atthat position. Then, contrary to some algorithms, the ω cannot be instantiated as some unseen
function symbol to show the item is relevant.

Example 4.5: Using the improved transition function, the automaton corresponding to
L = {1:faωω, 2:fωaa, 3:fωba, 4:fgωgωb} is given in Figure 4.6. As usual, transitions
corresponding to failure are omitted. Notice that for the same pattern set the automaton of
Figure 3.6 has six more states, namely states 6, 7, 12, 13, 14 and 15. Pattern-matching for theterms faaa and faba using the automaton of Figure 3.6 necessitates four symbol examinations
whereas by using the automaton of Figure 4.6 only two symbols need to be examined as ωsmatch any term. Thus, using the new transition function in this example, not only does theautomaton have fewer states but it also allows pattern-matching to be performed more quickly
for some inputs.

N. Nedjah, C.D. Walter & S.E. Eldridge

1: • fa ωω
2: • fωaa
3: • fωba
4: • fg ωgωbf
1: f • a ωω
2: f • ωaa
3: f • ωba
4: f • g ωgωb
2: f • aaa
3: f • aba
2: f • g ωaa
3: f • g ωba

a

g

ω

1: fa • ωω

4: fg • ωgωb
2: fg • ωaa
3: fg • ωba

2: fω • aa
3: fω • ba

ω
1: faω • ω

a

b

ω

2: fωa • a

3: fωb • aa

1: faωω •a
2: fωaa•ω

3: fωba•

4: fg ω • gωb
2: fgω • aa
3: fgω • baagb

2: fg ωa • a 4: fg ωg • ωb 3: fg ωb • aaaω
2: fg ωaa•

4: fg ωgω • b 3: fg ωba•b
4: fg ωgωb•

Figure 4.6: Matching automaton using the function rel.
In practice it may be expensive to check relevance as every state is constructed. It may becheaper to build the full automaton first and cut back the branches to remove irrelevancy
afterwards. The algorithm for this is the following. Items are first removed from final nodes, sothat each final node contains a single item, naming the matching rule to be applied. Then,moving up the matching tree, whenever an item has had all its images under accept removed
from child nodes, it can be removed itself from the current node and close re-applied to modify
the children if necessary. Thus, in Figure 3.6 the final states 12 and 14 both contain an irrelevant
pattern for deletion: only the rule numbers differ between the items and we must select that ofhighest priority and discard the other. After this the items corresponding to rules 2 and 3 may bedeleted from states 6 and 7 and hence from state 2 because they are not used in any of their childstates. Re-computing the closure of state 2 causes the branches rooted at states 6 and 7 todisappear. The automaton of Figure 4.6 is thus obtained.
To justify the correctness of this algorithm, note first that an irrelevant item, say r:α•β, cannot
be matched. At the final node reached by inputting the irrelevant item αβ, by construction thereProc. Internat. Workshop on the Implementation of Functional Languages, St Andrews, Sept 1997, pp 341-350

must be the instance αβ of every original pattern r′ which matches αβ, annotated with r′. These
are all irrelevant except for the item associated with the unique rule of highest priority, Thus theautomaton contains irrelevant items if, and only if, there is a final node whose matching set
contains more than one item. Now suppose that all occurrences of an item r:α•β ∈ M have been
removed from the children of the node labelled by M. We need to establish the correctness ofremoving it from M also. First of all, by induction, the item must be irrelevant for M: if it isirrelevant for, or unused by, all the children, then no input reaching M will match the item (elsethe item would appear in a final node descendent, which it doesn't), so it is irrelevant. The otherquestion is whether removal affects the pattern-matching. However, we need not pattern match
an irrelevant item, since all inputs to the node are matched with other items. Lastly, is the item
necessary to avoid backtracking? Here we note that if the item is to be removed from the kernelof the matching set, that is, the set obtained by applying accept to the parent set, then close is reapplied to the new set so that backtracking is automatically avoided. However, if r:α•β is itself
added by close, then it can be safely deleted without re-applying close because, as the item will
not be matched, there is no need to back-track to it. Thus the pruning algorithm is correct.
This process can be applied equally well to the partially minimised acyclic automata
described by the authors in [10], and enables a similar reduction in automaton size there also.
Finally, we observe the usefulness of this approach to the programmer. The appearance of
irrelevant items in final states corresponds to overlapping patterns; the automaton construction
process identifies overlaps automatically so that, without extra effort, the programmer can beadvised if appropriate.

8. Conclusion
In this paper, we began by recalling a practical method that compiles prioritised overlapping
patterns to a deterministic matching automaton.

However, the automaton may include

unnecessary branches when the patterns are overlapping. In the main body of the paper, we
identified those branches by considering relevant patterns and, by deleting irrelevant patterns, we
modified the method so that only necessary branches are included in the matching automaton.
An example showed how the matching automaton obtained can improve both the space and timerequirements.

N. Nedjah, C.D. Walter & S.E. Eldridge

References[1]

A. Augustsson, A Compiler for Lazy ML, Proc. ACM Conference on Lisp and Functional
Programming, ACM, pp. 218-227, 1984.

[2]

J. Christian, Flatterms, Discrimination Nets and Fast Term Rewriting, Journal of AutomatedReasoning, vol. 10, pp. 95-113, 1993.

[3]

D. Cooper and N. Wogrin, Rule-Based Programming with OPS5, Morgan Kaufmann, San
Francisco, 1988.

[4]

N. Dershowitz and J.P. Jouannaud, Rewrite Systems, Handbook of Theoretical Computer Science,
vol. 2, chap. 6, Elsevier Science Publishers, 1990.

[5]

A.J. Field and P.G. Harrison, Functional Programming, International Computer Science Series,
Addison-Wesley, 1988.

[6]

A. Gräf, Left-to-Right Tree Pattern-Matching, Proc. Conference on Rewriting Techniques andApplications, Lecture Notes in Computer Science vol. 488, pp. 323-334, Springer-Verlag 1991.

[7]

C.M. Hoffman and M.J. O’Donnell, Pattern-Matching in Trees, Journal of ACM, vol. 29,
nº 1, pp. 68-95, 1982.

[8]

P. Hudak, S.L. Peyton-Jones, P. Wadler, et al., Report on the Programming Language Haskell: a

Non-Strict, Purely Functional Language, Version 1.2, SIGPLAN Notices, Section S, May 1992,
pp. 1-164.
[9]A. Laville, Comparison of Priority Rules in Pattern Matching and Term Rewriting, Journal of
Symbolic Computation, nº 11, pp. 321-347, 1991.

[10] N. Nedjah, C.D. Walter and S.E. Eldridge, Optimal Left-to-Right Pattern-Matching Automata,Proc. ALP’97, Southampton, Lecture Notes in Computer Science vol. 1298, Springer-Verlag,
1997.
[11] M.J. O'Donnell, Equational Logic as Programming Language, MIT Press, 1985.
[12] R.C. Sekar, R. Ramesh and I.V. Ramakrishnan, Adaptive Pattern-Matching, SIAM Journal on
Computing,, vol. 24, nº 5, pp. 1207-1234, 1995.
[13] D.A. Turner, Miranda: a Non Strict Functional Language with Polymorphic Types, Proc.
Conference on Lisp and Functional Languages, ACM, pp. 1-16, 1985.