[antlr-interest] single-pass pattern matching "for free"?

Terence Parr parrt at cs.usfca.edu
Sun Jan 15 11:39:37 PST 2006


On Jan 14, 2006, at 8:09 PM, Sohail Somani wrote:

> On Sat, 2006-01-14 at 15:59 -0800, Terence Parr wrote:
>> Perhaps we can have the ease of specification of Andy's solution
>> without having to handbuild a specific pattern engine...well, if
>> we're going to only do a single linear check for a match, apply rule,
>> and repeat.  Imagine a pattern engine like this:
>>
>> <expr>+0 -> <expr>
>> <expr>*0 -> 0
>>
>> Can't we auto convert this to:
>>
>> rules returns [String result]
>>        :       => expr '+' INT {$INT.text.equals("0")}? {$result =
>> $expr.text;}
>>        |       => expr '*' INT {$INT.text.equals("0")}? {$result =
>> $INT.text;}
>>        ;
>
> After some more thought, doesn't it seem like just a more concise  
> way to
> specify tree parsing? What would the differences be?

And that is the most important question of all!  The answer is:

1. just listing a bunch of patterns is easier until you get a huge  
number of them, when it becomes hard to find bugs in rule applications.
2. patterns have no guarantee of coverage whereas a tree grammar does.
3. patterns are floating in space w/o context; a grammar knows that  
expressions cannot occur outside of a method or var  
initialization...patterns could specify context, however, but it is  
not as clear as a grammar.  want an action to execute when you see  
the '}' of a function, just stick an action after the '}' in the  
appropriate spot in the grammar.

The translation of a pattern -> replacement system would be trivial  
for a simple system; just translate to ANTLR.  Further, to separate  
the view from the controller, one could use templates on the right:

"<a:expr>+<b:expr>" -> add(left=a,right=b)

or some such just like an antlr grammar.  The idea would be really  
groovy.  You give me a grammar and then a list of patterns and I  
generate a combined new grammar that does exactly what you want,  
yanking in all the required tokens/rules.  Now where is a grad  
student when I need some cheap smart labor! ;)  Actually, that would  
make a damn fine paper and system.

Ter


More information about the antlr-interest mailing list