Recursive descent algorithm able to parse Python?

Piet van Oostrum piet at cs.uu.nl
Fri Oct 6 17:46:56 CEST 2006


>>>>> "Diez B. Roggisch" <deets at nospam.web.de> (DBR) wrote:

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

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

This is the first time I see this called `backup'. I have always used and
seen the term `backtracking'.
-- 
Piet van Oostrum <piet at cs.uu.nl>
URL: http://www.cs.uu.nl/~piet [PGP 8DAE142BE17999C4]
Private email: piet at vanoostrum.org



More information about the Python-list mailing list