Efficient automata‐driven pattern‐matching for equational programs
Nadia Nedjah, Colin D. Walter, Stephen E. Eldridge · Software Practice and Experience · 1999
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 matching table is constructed using a compilation method similar to the technique that YACC employs to generate parsing tables. The matching table obtained allows for the pattern-matching process to be performed without any backtracking. Then, the known information about right sides of the equations is inserted in the matching table in order to speed-up the pattern-matching process. Most of the discussion assumes that the processed pattern set is left-linear, the non-linear case being handled by an additional pass following the matching stage. Copyright © 1999 John Wiley & Sons, Ltd.