Hacker News Reader

Comment by scribu | Hacker News Reader

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/nJzOyRnA...

View on HN

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?

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.

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.

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

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.

You imply that indentation isn't a part of Python's grammar...

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/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.

Reply on news.ycombinator.com