Efficient automata-driven pattern-matching for equational programs

We propose a practical technique to compile left-to-right pattern-matching of prioritised overlapping function definitions in equational languages to a matching automaton from which efficient code can be derived. First, a mat ching table is constructed using a compilation method similar to the techni que that YACC employs to generate parsing tables. The matching table obtain ed allows for the pattern-matching process to be performed without any back tracking. Then, the known information about right sides of the equations is inserted in the matching table in order to speed-up the pattern-matching p rocess. Most of the discussion assumes that the processed pattern set is le ft-linear, the non-linear case being handled by an additional pass followin g the matching stage. Copyright (C) 1999 John Wiley & Sons, Ltd.