Efficient automata-driven pattern-matching for equational programs

✍ Scribed by Nadia Nedjah; Colin D. Walter; Stephen E. Eldridge

• Publisher: John Wiley and Sons
• Year: 1999
• Tongue: English
• Weight: 210 KB
• Volume: 29
• Category: Article
• ISSN: 0038-0644
• DOI: 10.1002/(sici)1097-024x(19990725)29:9<793::aid-spe254>3.0.co;2-m

✦ Synopsis

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.