6
$\begingroup$

From Wikipedia: Off-side_rule#Implementation, there is a statement:

...This requires that the lexer hold state, namely the current indentation level, and thus can detect changes in indentation when this changes, and thus the lexical grammar is not context-free – INDENT/DEDENT depend on the contextual information of previous indentation level.

I'm a bit confused. Some lexical grammars of Python is not context-free but INDENT/DEDENT themselves can be expressed in CFG. So lastly, Python is a context-free language or not?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ It's most certainly not, depending on how you would define the language. (Since there's no compiler, what constitutes a valid program?) See this question on cstheory.SE. $\endgroup$ – Raphael♦ Jul 16 '17 at 10:22
  • 1
    $\begingroup$ @raphael: the text of the language definition, which includes a grammar? The operation of the builtin ast module, which converts a string to an AST or reports failure? Why do you need a compiler per se? $\endgroup$ – rici Mar 24 '18 at 14:36
10
$\begingroup$

Context-free grammars cannot express the rules of INDENT/DEDENT and so Python (which we use today in practice with INDENTs/DEDENTs)is not pure CF. Parsers (or lexical analyzers or lexers) for these languages use additional techniques to handle those structures. For example keep track of indentation levels, or tokenizer (scanners) may count number whitespaces and store that info in a table for later use. This is similar to something like trying to write a parser for the language $a^nb^{2n}c^n$, where you must keep track of value of $n$.

A simple example of adding additional power to a lexer is removing redundant whitespace symbols (space/tabs/newlines) or removing comments which has no meaning for the parser (parsing a CFL).

As another example, roughly it can be described as following. Assume a grammar $a^nb^mc^k$ which is clearly CFG. You use BISON/YACC like tools to generate a parser for this grammar. Then you can introduce an additional rule like number of $a$s must be equal to the number of $c$ which makes the language non CF. So you just add extra logic (manually coding) to your parser to handle that rule by means of, say, annotated trees. Your original language is still context free but extra piece of code you added manually allows it to accept non CF subset of the original language.

I don't think that such parsers are generated automatically by compiler tools (at least I don't know) and so that ("non context free") part must be coded manually.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But basically, INDENT/DEDENT are defined as terminal symbols right? Which is one of the members of grammar G here: en.wikipedia.org/wiki/Context-free_grammar#Formal_definitions . So, how does INDENT/DEDENT violate the definition of CFG. $\endgroup$ – fronthem Jul 16 '17 at 11:12
  • $\begingroup$ "Context-free grammars cannot express the rules of INDENT/DEDENT": It does in Python (ref: docs.python.org/2/reference/grammar.html). You would like to say that regex cannot express INDENT/DEDENT right? $\endgroup$ – fronthem Jul 16 '17 at 11:19
  • $\begingroup$ In fact, it is not INDENT/DEDENT that violates the definition of CFG, but their count. You have to keep track of counts of INDENT if you for example allow nested indents. How can you incorporate that information (#of indents) into a CFG? $\endgroup$ – fade2black Jul 16 '17 at 11:19
  • 2
    $\begingroup$ I am not expert in Python compiler implementation, but I guess the lexer emits INDENT tokens as input to the parser every time the lexer sees whitespace symbols together with their count, and parser decides whether the Python code has grammar errors or not. $\endgroup$ – fade2black Jul 16 '17 at 11:33
  • $\begingroup$ I updated the post. Please have a look. $\endgroup$ – fade2black Jul 16 '17 at 11:42
-2
$\begingroup$

Python is not a context free language. We can check any language context free or not using Odgens's lemma (In the theory of Formal languages).

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ And what would that look like? Our reference question lists many methods of showing that a language is not context-free; what's the lesson here? $\endgroup$ – Raphael♦ Mar 24 '18 at 8:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.