Pettersson, M. (1992). A Term Pattern-Match Compiler Inspired by Finite Automata Theory. Technical Report LiTH-IDA-R-92-09, Department of Computer and Information Science, Linköping University, Sweden. Also in the proceedings of The 4th International Conference on Compiler Construction (CC'92), Paderborn, Germany, October 5-7, 1992, LNCS-641, Springer Verlag. (bibtex),
Abstract: This paper presents a new algorithm for compiling term pattern-matching for functional languages. Earlier algorithms may produce duplicated code, and redundant or sub-optimal discrimination tests for certain combinations of patterns, in particular when a pattern column contains a mixture of constructors and variables. This algorithm, which was inspired by finite automata theory, addresses these problems and solves them to some extent. It does so by viewing patterns as regular expressions, and optimising the finite automaton that is built to recognise them. It also makes checking patterns for exhaustiveness and irredundancy cheap operations.
CS Dept TR Overview