Lawrence D'Oliveiro wrote: > In message <[EMAIL PROTECTED]>, Diez B. Roggisch wrote: > >> [EMAIL PROTECTED] 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 -- http://mail.python.org/mailman/listinfo/python-list
