Recursive descent algorithm able to parse Python?

[Diez B. Roggisch]

Lawrence D'Oliveiro wrote:

> In message <4o2ugcFcm4npU1 at uni-berlin.de>, Diez B. Roggisch wrote:
> 
>> seberino at spawar.navy.mil schrieb:
>>> I'm a compiler newbie and curious if Python grammar is able to
>>> be parsed by a recursive descent parser or if it requires
>>> a more powerful algorithm.
>> 
>> I might be mistaken, but isn't recursive descent one of the more
>> powerful parsing techniques - for the price of non-linearity and even
>> potentially non-termination?
> 
> No, you're thinking of LR(k) bottom-up parsers. Recursive descent is a

No, I'm not.

> top-down parser--might be the same thing as LL(1), I'm not sure. It's easy
> to implement and easy to understand, to the point where there is strong
> pressure on programming-language designers to make sure their languages
> can be parsed with recursive descent.

http://en.wikipedia.org/wiki/Recursive_descent_parser

"""
Recursive descent with backup is a technique that determines which
production to use by trying each production in turn. Recursive descent with
backup is not limited to LL(k) grammars, but is not guaranteed to terminate
unless the grammar is LL(k). Even when they terminate, parsers that use
recursive descent with backup may require exponential time.
"""

I have to admit that I have difficulties to compare LR(k) to recursive
descent, but the fact that the latter contains backtracking makes it at
least more powerful than LL(k)

Diez