0
$\begingroup$

I have a high level understanding of formal languages and grammars, and I'm familiar with the four major types of grammars in Chomsky hierarchy. I was interested in knowing the classification of Python's grammar. A quick search yielded some quick, but incomplete answers.

http://trevorjim.com/python-is-not-context-free/

https://www.reddit.com/r/compsci/comments/1f2e0w/ive_heard_of_contextfree_grammars_cfgs_but_are/

Is Python a context-free language?

The immediate takeaway from most resources it that Python's grammar is not a context free grammar (CFG). But that doesn't answer the question of what it is. Looking deeper I found that its a complete context sensitive grammar (CSG) either. But still no classification.

At this point the conclusion was that there must exist classes of grammars between CFGs and CSGs, but I had never heard anything about these.

What I do understand is Python's lexer (which transforms character sequences into tokens) does something that a CFG cannot do: it tracks the level of indentation and yields special INDENT DEDENT tokens. After this transformation resulting tokens are context-free and can be parsed into an abstract syntax tree. Thus the grammar on tokens is a CFG, but the grammar on characters uses slightly power power than a CFG can provide alone. I want to know if there is a classification for this type of grammar. What is between a CFG and a CSG?

After a bit more searching I stumbled on this table at the bottom of a Wikpedia article: https://en.wikipedia.org/wiki/Linear_bounded_automaton#External_links

Here is an image of that table:

enter image description here

Cool, I found that there are known grammars between CFG and CSGs. But I'm not an expert on formal languages, so I don't know how I would go about determining which if any of these categories Python's grammar belonged to.

Is it a "Positive range concatenation", "Indexed", "Thread automation's Grammar", "Linear context-free rewriting system", "Tree-adjoining"? Is it none of these; if so does what it is have a classification?

Note: The full grammar specification of Python 3 can be found here: https://docs.python.org/3/reference/grammar.html

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.