grammar question

[Martin v. Loewis]

Greg Ewing <greg at cosc.canterbury.ac.nz> writes:

> Python's parser is an interesting beast. I haven't looked at
> the internals of the parser generator, so I can't be sure,
> but it seems that, although it may be using a recursive
> descent algorithm at the production level, *within* a
> production it must use some sort of regular expression 
> matching engine.

It doesn't use recursive-descent; it is a table-driven LL(1)
parser. Notice that regular expressions also define LL(1) languages,
so the entire pgen parser is a "regular expression matching engine"
:-)

> For these reasons, saying just "Python's grammar is
> LL(1)" is oversimplifying things considerably.

If you count the semantic analysis as part of the grammar, I believe
there would be few programming languages that have a context-free
grammar. For example, in Python, it is an error if both a yield
statement and a return statement occur in the same function. Try
explaining that to your friendly LR(k) parser...

Regards,
Martin