HOME       UP       PREV       NEXT (ABD - SERES Pattern Matching Example)  

Naive pattern to RTL Automaton

The ML fragment gen_pattern_matcher handles concatenation, fusion concatenation, alternation, arbitrary repetition and n-times repetition. However, this generates a one-hot automaton and there are far more efficient procedures used in practice and given in the literature.

A harder operator to compile is the length-matching conjunction (introduced shortly), since care is needed when each side contains arbitrary repetition and can declare success or failure at a number of possible times.

(C) 2008-10, DJ Greaves, University of Cambridge, Computer Laboratory.