6 ms·

Python is not context free (2012)

73 points by linux2647 7y ago

perfunctory 7y ago
> the parser component is a context-free parser > 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?
- nightcracker 7y ago
  The lexer isn't context-free, and you should re-read the paragraph. The part that you left out in the dots is crucial: > 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.
  - deleted 7y ago
    [deleted]
- marmada 7y ago
  Did you ignore the next sentence: 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.
jMyles 7y ago
It feels to me like this is the thesis: > 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.
- nightcracker 7y ago
  > Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? 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' | ''.
  - jMyles 7y ago
    Right - that was the point I was (perhaps awkwardly) making by posing the question that way.
- ptsneves 7y ago
  For me the interesting part was a cliff hanger:). How exactly a context free parser and lexer help in specification? Do such cases exist? If not why? Also why have I never heard of context free programing languages? I am trying to think of file formats and even a puny ini file has a context aware parser. 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.
  - ben509 7y ago
    I think it helps with tooling, linters, refactoring tools, code generation, etc., if you have a "standard" lexer and parser. The reason being these tools can rely on reasonably standard parsing libraries to take a spec in a common format and then translate input to an AST to take actions on. If you haven't heard the term context-free, you haven't done much parsing; it's ubiquitous there.
- coldtea 7y ago
  >Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? 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...
andolanra 7y ago
There are some papers (which postdate this blog post) that add simple extensions to context-free grammars that are capable of expressing the grammars of indentation-based languages in a principled way: Principled Parsing for Indentation-Sensitive Languages (Michael Adams, 2013)[1] and Indentation-Sensitve Parsing for Parsec (Michael Adams, 2014)[2], which add support for indentation-based parsing to bottom-up parsers (specifically GLR and LR(k)) and top-down parsers (parser combinator-like systems and PEGs) respectively. 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/ https://michaeldadams.org/papers/layout_parsing/ [2]: https://michaeldadams.org/papers/layout_parsing_2/ https://michaeldadams.org/papers/layout_parsing_2/
nickcw 7y ago
Interesting article... I wrote a lexer for python as part of gpython: https://github.com/go-python/gpython/blob/f100534592c96b7922c59660553ee77fbf217da1/parser/lexer.go#L375 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.
kissgyorgy 7y ago
If you found this article interesting, you might find interesting Guido's blog post series about PEG parsers: https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60 https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d...
canjobear 7y ago
> It’s pretty obvious that most programming languages are not context free if you consider them as languages over sequences of characters. Not obvious to me. Can someone explain this?
- insulanus 7y ago
  Let's say you are parsing a language that contains both negative numbers, and the "minus" symbol. Most languages use the same ASCII glyph for both of those, but they mean very different things, and are parsed as parts of different tokens. 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.
  - johnday 7y ago
    In many cases this won't be true as you can infer from the left hand side only (for example) what - means and mode switch appropriately.
  - Sharlin 7y ago
    Many mainstream languages don't actually have negative number literals. They lex `-42` as two tokens: the operator `-` and the integer literal `42`.
    - Doxin 7y ago
      The unary minus operator is still different from the binary minus operator depending on context in languages that tackle it that way.
      - Sharlin 7y ago
        Yes, but that's a parsing-time distinction. The lexer does not need to care. And even though the token's syntactic meaning "depends on the context", the grammar itself can be (and usually is) perfectly context-free!

73 points by linux2647 7y ago

> the parser component is a context-free parser > 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?

nightcracker 7y ago
The lexer isn't context-free, and you should re-read the paragraph. The part that you left out in the dots is crucial: > 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.
- deleted 7y ago
  [deleted]
marmada 7y ago
Did you ignore the next sentence: 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.

jMyles 7y ago

It feels to me like this is the thesis: > 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.

nightcracker 7y ago
> Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? 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' | ''.
- jMyles 7y ago
  Right - that was the point I was (perhaps awkwardly) making by posing the question that way.
ptsneves 7y ago
For me the interesting part was a cliff hanger:). How exactly a context free parser and lexer help in specification? Do such cases exist? If not why? Also why have I never heard of context free programing languages? I am trying to think of file formats and even a puny ini file has a context aware parser. 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.
- ben509 7y ago
  I think it helps with tooling, linters, refactoring tools, code generation, etc., if you have a "standard" lexer and parser. The reason being these tools can rely on reasonably standard parsing libraries to take a spec in a common format and then translate input to an AST to take actions on. If you haven't heard the term context-free, you haven't done much parsing; it's ubiquitous there.
coldtea 7y ago
>Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? 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...

andolanra 7y ago

There are some papers (which postdate this blog post) that add simple extensions to context-free grammars that are capable of expressing the grammars of indentation-based languages in a principled way: Principled Parsing for Indentation-Sensitive Languages (Michael Adams, 2013)[1] and Indentation-Sensitve Parsing for Parsec (Michael Adams, 2014)[2], which add support for indentation-based parsing to bottom-up parsers (specifically GLR and LR(k)) and top-down parsers (parser combinator-like systems and PEGs) respectively. 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/ https://michaeldadams.org/papers/layout_parsing/ [2]: https://michaeldadams.org/papers/layout_parsing_2/ https://michaeldadams.org/papers/layout_parsing_2/

nickcw 7y ago

Interesting article... I wrote a lexer for python as part of gpython: https://github.com/go-python/gpython/blob/f100534592c96b7922c59660553ee77fbf217da1/parser/lexer.go#L375 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.

kissgyorgy 7y ago

If you found this article interesting, you might find interesting Guido's blog post series about PEG parsers: https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d41b2ed60 https://medium.com/@gvanrossum_83706/peg-parsing-series-de5d...

canjobear 7y ago

> It’s pretty obvious that most programming languages are not context free if you consider them as languages over sequences of characters. Not obvious to me. Can someone explain this?

insulanus 7y ago
Let's say you are parsing a language that contains both negative numbers, and the "minus" symbol. Most languages use the same ASCII glyph for both of those, but they mean very different things, and are parsed as parts of different tokens. 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.
- johnday 7y ago
  In many cases this won't be true as you can infer from the left hand side only (for example) what - means and mode switch appropriately.
- Sharlin 7y ago
  Many mainstream languages don't actually have negative number literals. They lex `-42` as two tokens: the operator `-` and the integer literal `42`.
  - Doxin 7y ago
    The unary minus operator is still different from the binary minus operator depending on context in languages that tackle it that way.
    - Sharlin 7y ago
      Yes, but that's a parsing-time distinction. The lexer does not need to care. And even though the token's syntactic meaning "depends on the context", the grammar itself can be (and usually is) perfectly context-free!