Rewriting the pattern matching engine — part 1

For the last two weeks, I’ve trying to write Piggy patterns to construct a symbol table from a Java AST. Patch after patch, I’d change the pattern matching code to “fix” something that wasn’t working. Unfortunately, I finally wrote a pattern that broke the camel’s back, “< classBodyDeclaration < modifier >* < memberDeclaration < methodDeclaration > > >”, which looks for methods within a class.

So, I decided to rewrite the engine the way it should have been done: using an NFA. It’s so far taken a week or so, but it turns that the pattern matcher is much cleaner, and likely faster. In addition, the output engine–which executes the code blocks in the pattern–is also much cleaner. I’ll try to see if I can combine the patterns together in one automaton.

I really should have known better than to approach the tree regular expression matching problem following what other people did, using a top-down recursive recognizer. Live and learn. Always follow a clean, clear theory instead of just hacking.