[antlr-interest] question on greedy matching

[Andrei Alexandrescu]

Ric Klaren wrote:
> On 10/18/05, Andrei Alexandrescu <andrei at metalanguage.com> wrote:
>>try statement ( catch (ID ID) '{' statement '}' )+
>>
>>Clearly not an award-winning design, because it has the "dangling catch"
>>ambiguity:
>>
>>try
>>     try
>>         foo();
>>     catch (E1 e) { bar(); }
>>catch (E2 e) { baz(); }
> 
> 
> I assume the try statement is an alternative of the statement rule (or
> somewhere below it)?


That is correct. The try statement is an alt of statement.

> (Side note: This is awfully horrid language design.... adding curlies
> around the statement inside the try would make life a lot more
> pleasant.)

Definitely. But it's the most sensible example I could find for a 
situation where you want a non-greedy parsing. (Other examples?) In 
addition, it's an excellent exercise for understanding how to do some 
nontrivial parsing with antlr.

Besides, think o the even more horrid rule:

statement ::= ...
   | try statement ( catch (ID ID) statement )+

That is, eliminate curlies from the catch as well. Now you need an awful 
lot of disambiguation, because how are you going to interpret:

try
      try
          foo();
      catch (E1 e) try bar(); catch (E3 e) zip();
catch (E2 e) baz();

> I guess the following is not allowed?
> 
> try
>      try
>          foo();
>      catch (E1 e) { bar(); }
>      catch (E2 e) { baz(); }
>      bbb();
> catch (E3 e) { baa(); }

You can't do that, you'd have to add curlies:

try {
      try
          foo();
      catch (E1 e) { bar(); }
      catch (E2 e) { baz(); }
      bbb();
}
catch (E3 e) { baa(); }

In other words, it's a Java-like language, not a Python-like language 
(indentation is irrelevant).

> No predicates is probably not possible without switching to
> treebuilding and fixing things in a 2nd pass.

That's what I thought.

> Not 100% sure but the dirty trick department might work:
> 
> try_rule { ncatch = 0; }:
> try { this.ntry++; } statement
> (  { if( ntry > 1 && ncatch > 1 ) break; }:
>    catch { ncatch++; }  (ID ID) '{' statement '}'
> )+ { this.ntry--; }

Ok, I understand.

> Alternatively:
> 
> start out with a try rule with only one catch. Then define an extra
> alternative (probably in the statement rule to collect trailing catch
> statements) Some checks are probably necessary afterwards to see if
> everything made sense. The catch all might need a predicate to prevent
> it from being entered if the preceding statement was not a try.

I believe this is not possible with syntactic predicates. You have to 
have semantic predicates, I think. Actually that's my fundamental 
question. Another fundamental question is how would a PEG deal with that 
(see http://pdos.csail.mit.edu/~baford/packrat/).

> Hope this helps (and that it was not too late in the evening when I
> wrote this ;) ),

Thanks, Ric.


Andrei