recursion in grammar?

[Michael Hudson]

peri12345 at poczta.onet.pl (Peri) writes:

> I'm trying to create Python parser/interpreter using ANTLR. 
> Reading grammar from language refference I found:
> or_expr::= xor_expr | or_expr "|" xor_expr
> 
> For me it looks like infinite recursion.

Isn't this just left recursion (a standard LL(1) trick)?

> And so it says ANTLR. Maybe I don't understand EBNF notation. For
> me it should look like this.  or_expr::= xor_expr | xor_expr "|"
> xor_expr

That wouldn't let you write "1 | 2 | 4", would it?

It's not really different from recursion in programming languages (or
mathematical induction) -- the Python grammar is a finite way of
describing sequences of tokens of arbitrary length.  You have to have
*some* trick like recursion in there for this to work.

I can't help you with ANTLR.

Cheers,
mwh


-- 
  I would hereby duly point you at the website for the current pedal
  powered submarine world underwater speed record, except I've lost
  the URL.                                         -- Callas, cam.misc