Synthèse
Volume 4, Numéro 1, Pages 32-38
1999-06-30

Pattern-matching Without Backtracking

Authors : Nedjah * . N. . Sellami" M. . Eldridge S. . Walter C .

Abstract

We propose a pratical technique to compile pattern-matching function definitions in equational-like languages, to a matching table from which ejJicient code can be derived. It is assumed that the evaluation is performed using normal order strategy. Forst, the original pattern set is converted to a closed pattern set allowing for the pattern-matching process to be performed without backtracking operations. Next, a matching table is constructed using a compilation method inspired front that YACC employes. Most of the discussion assufllfs that the processed pattern set is left-linear (the non-linear case can be handled by an additional pass following the matching stage

Keywords

pattern-matching, rewriting, equational programming, compilation