Home Original page

recursion in grammar?

Terry Reedy tjreedy at udel.edu
Sat Dec 27 13:04:15 EST 2003 
"Peri" <peri12345 at poczta.onet.pl> wrote in message
news:34ea966a.0312270509.5ecc2095 at posting.google.com...
> 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.

Better to call it unbounded recursion.  This is what makes general CF
languages/grammars more extensive/powerful that regular languages.

In particular, the recursion is written as left recursion.
The equivalent right recursion would be
or_expr::= xor_expr | xor_expr "|" or_expr
The recursive 'call' is to the right of the connector literal instead of
the left.

There are two types of linear CF parsers: bottom-up LR and top-down LL.
Each handles recursion written one way and chokes on recursion written the
other way.  The two types have opposite requirements.  (I forget which is
which.)  Since Antler choked on left recursion, I presume that it is the
'other' type than Python's and that it requires right rather than left
recursion.  So try reversing all the recursive definitions.  (Or try first
the one that gives first error message and see if you get farther.)

Terry J. Reedy
More information about the Python-list mailing list