Recursive descent algorithm able to parse Python?

Piet van Oostrum piet at
Fri Oct 6 17:46:56 CEST 2006

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


>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>
URL: [PGP 8DAE142BE17999C4]
Private email: piet at

More information about the Python-list mailing list