Recursive descent algorithm able to parse Python?

Lawrence D'Oliveiro ldo at geek-central.gen.new_zealand
Fri Sep 29 01:50:23 CEST 2006


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
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.



More information about the Python-list mailing list