3 ms·

I watched the introduction video and the author made a surprising claim: that deciding if a string of characters is valid Python code is fundamentally simpler t

by scribu 10y ago

I watched the introduction video and the author made a surprising claim: that deciding if a string of characters is valid Python code is fundamentally simpler than deciding if it's valid code in some other language. In more precise terms, the assertion is that Python's grammar belongs to the context-free class of languages in Chomsky's hierarchy. Here's an interesting discussion about that and the more philosophical question "what is valid code?" on comp.theory: https://groups.google.com/forum/m/#!msg/comp.theory/nJzOyRnAP3k/AInZxo48FNIJ https://groups.google.com/forum/m/#!msg/comp.theory/nJzOyRnA...

mikekchar 10y ago
I don't really have time to watch a video at the moment, but I'm not really sure what the significance is. If you allow look-ahead, I would think that most popular languages can be parsed with an LALR(2) parser (e.g. yacc/bison). I've even implemented the SIP protocol with an LALR(K) (antlr) parser and SIP is insane :-). I often wonder about Ruby, especially with the leading period that's allowed. But there are a lot languages with really simple grammars out there. I can't imagine that python is anywhere near the top of the list. In practical terms, simple grammars make it easy to write tools. I suppose you can also save stack space if you have simple grammars, which may be significant in some situations. Other than that, I'm not sure why it matters. Can you elaborate a bit more?
- scribu 10y ago
  I don't think there's any great significance behind it. I guess I jumped at the idea because it seemed to provide a simple theoretical explanation as to why Python is easier to grok than other languages which don't have context-free grammars.
  - gary_bernhardt 10y ago
    Yep, that was my motivation: to hint at deeper connections to programming at large, rather than focusing on technical concerns that are confined to parser implementation and therefore esoteric to an outsider.
paxcoder 10y ago
Python's grammar is context-sensitive until the lexer processes indentation. There are other programming languages whose grammar is context-free.
- gary_bernhardt 10y ago
  I went back and forth on that statement for exactly this reason, but kept it because the whitespace is handled in the lexer, as you mentioned. The Python grammar itself is context-free, and the grammar is the only part that I expect the series to examine.
  - paxcoder 10y ago
    You imply that indentation isn't a part of Python's grammar...
    - gary_bernhardt 10y ago
      It's not part of the Python grammar as specified in the file called Grammar in the canonical implementation of the language (https://github.com/python/cpython/blob/master/Grammar/Grammar https://github.com/python/cpython/blob/master/Grammar/Gramma...). Of course it's part of the grammar in the larger sense. I don't think that that distinction is important when trying to convince someone with no theoretical background to learn these topics, which is what the video in question is trying to do.

by scribu 10y ago

mikekchar 10y ago

I don't really have time to watch a video at the moment, but I'm not really sure what the significance is. If you allow look-ahead, I would think that most popular languages can be parsed with an LALR(2) parser (e.g. yacc/bison). I've even implemented the SIP protocol with an LALR(K) (antlr) parser and SIP is insane :-). I often wonder about Ruby, especially with the leading period that's allowed. But there are a lot languages with really simple grammars out there. I can't imagine that python is anywhere near the top of the list. In practical terms, simple grammars make it easy to write tools. I suppose you can also save stack space if you have simple grammars, which may be significant in some situations. Other than that, I'm not sure why it matters. Can you elaborate a bit more?

scribu 10y ago
I don't think there's any great significance behind it. I guess I jumped at the idea because it seemed to provide a simple theoretical explanation as to why Python is easier to grok than other languages which don't have context-free grammars.
- gary_bernhardt 10y ago
  Yep, that was my motivation: to hint at deeper connections to programming at large, rather than focusing on technical concerns that are confined to parser implementation and therefore esoteric to an outsider.

paxcoder 10y ago

Python's grammar is context-sensitive until the lexer processes indentation. There are other programming languages whose grammar is context-free.

gary_bernhardt 10y ago
I went back and forth on that statement for exactly this reason, but kept it because the whitespace is handled in the lexer, as you mentioned. The Python grammar itself is context-free, and the grammar is the only part that I expect the series to examine.
- paxcoder 10y ago
  You imply that indentation isn't a part of Python's grammar...
  - gary_bernhardt 10y ago
    It's not part of the Python grammar as specified in the file called Grammar in the canonical implementation of the language (https://github.com/python/cpython/blob/master/Grammar/Grammar https://github.com/python/cpython/blob/master/Grammar/Gramma...). Of course it's part of the grammar in the larger sense. I don't think that that distinction is important when trying to convince someone with no theoretical background to learn these topics, which is what the video in question is trying to do.