Python is not context free (2012)
trevorjim.com
trevorjim.com
These techniques do not "make Python context-free", so the blog's content stands. However, they do help address the final point of this blog post: they provide principled and limited tools which can express this kind of non-context-free grammar in a declarative way. Tools like these allow us to use simple lexers (i.e. without state hacks like Python's) while expressing indentation-based grammars using easy-to-understand-and-analyze BNF-like formalisms.
[1]: https://michaeldadams.org/papers/layout_parsing/ [2]: https://michaeldadams.org/papers/layout_parsing_2/
I wrote a lexer for python as part of gpython: https://github.com/go-python/gpython/blob/f100534592c96b7922...
It is remarkably complex and has a huge amount of state including separate indent levels for parentheses, brackets and braces!
The lexer is extremely well defined in the python docs; I wrote my version entirely by looking at the docs and not at the CPython source code (unlike let's say the compiler!).
Shoving the complexity into the lexer does make the python grammar itself quite straight forward though.
> Furthermore, a typical lexer will strip all whitespace from the token stream, so the parser never sees it.
...but is that important in answering the underlying question?
Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free?
The fact that python performs minor gymnastics around whitespace in order to achieve its control structure pattern is not per se pre-existing context in terms of its parser. If that's the conclusion that I'm being asked to reach, then I disagree with the argument.
Absolutely. Any CFG can be made to ignore whitespace by dumping the nonterminal W between each symbol in each rule, and letting W -> W ' ' | W '\n' | ''.
Do not get me wrong with all these questions. I never heard of this topic before so I am very curious and grateful for the HN post.
If you haven't heard the term context-free, you haven't done much parsing; it's ubiquitous there.
Sure.
What does ignoring "an entire class of legal characters" has to do with being context-free (which just means that each production rule doesn't need further context to work)?
You can trivially ignore "an entire class of legal characters with (regular language compatible) regular expressions - and if so, you can express that processing as a context-free grammar...
The article seems to extrapolate that because Python's syntax requires that it not ignore whitespace characters, that this distinction represents context.
In practice it is very uniform and can be easily converted to a context-free language as indentation and parenthesis are equivalent.
The typical example is that a context-free language cannot remember numbers so a context-free parser cannot group together indentation levels. In general this tries to match something like (w^n a)* for a fixed n, which is not context free
Don't these both represent the exact same amount of context (which reasonable people might disagree over which is "zero" or "non-zero")?
every correct indentation can be easily converted to parenthesis and viceversa (simply increase in indentation are opening brackets and decreasing are closing brackets), but it cannot be done by a context-free parser.
>Don't these both represent the exact same amount of context (which reasonable people might disagree over which is "zero" or "non-zero")?
the difference is in what kind of state the lexer can access. with parenthesis you remember in with a stack, you know what in what kind of block you are but know nothing of where you were. with indentation you need to remember the whitespaces on the previous line.
(Haskell for example has both a indentation based syntax and a {,} context-free equivalent syntax. In this sense focusing on being context-free is slightly meaningless.
(there is another category of languages which is very close to context free with the restriction that every token cannot be both "opening" and "closing" at the same time, as it is almost always the case. This category of languages can be operated on like regular languages, which is very nice)
Not obvious to me. Can someone explain this?
So, I believe the author's point is that in cases like these, you have to remember surrounding context in order to correctly classify which type of (and which) token a character belongs to.
> The Python lexer ... is the canonical non-regular, context-free language!
So we have a context-free lexer and a context-free parser. How come the total is not context free?
> The Python lexer keeps, in addition, a stack of counters for the indentation levels. Moreover, it keeps track of the nesting of parentheses; and the language of balanced parentheses is the canonical non-regular, context-free language! So in this design, there is no clear separation of the context-free part and the context-sensitive part, and the context-sensitive part goes well beyond what a typical lexer can do.