3 ms·

Righto - that's the exact point I was trying to make. The article seems to extrapolate that because Python's syntax requires that it not ignore whitespace char

by jMyles 7y ago

Righto - that's the exact point I was trying to make. The article seems to extrapolate that because Python's syntax requires that it not ignore whitespace characters, that this distinction represents context.

afiori 7y ago
The point is that it requires the lexer to count whitespaces. In practice it is very uniform and can be easily converted to a context-free language as indentation and parenthesis are equivalent. The typical example is that a context-free language cannot remember numbers so a context-free parser cannot group together indentation levels. In general this tries to match something like (w^n a)* for a fixed n, which is not context free
- jMyles 7y ago
  ...but how is this any different than a '{}' language "remembering" whether a control structure is opening, and requiring a '}' to close it? Don't these both represent the exact same amount of context (which reasonable people might disagree over which is "zero" or "non-zero")?
  - afiori 7y ago
    yes, the difference is that indentation is accepting ||1||2||3||4 and |||1|||2|||3|||4 but not ||1|||2|||3||4. Here the context is remembering how many bars had the last "line". every correct indentation can be easily converted to parenthesis and viceversa (simply increase in indentation are opening brackets and decreasing are closing brackets), but it cannot be done by a context-free parser. >Don't these both represent the exact same amount of context (which reasonable people might disagree over which is "zero" or "non-zero")? the difference is in what kind of state the lexer can access. with parenthesis you remember in with a stack, you know what in what kind of block you are but know nothing of where you were. with indentation you need to remember the whitespaces on the previous line. (Haskell for example has both a indentation based syntax and a {,} context-free equivalent syntax. In this sense focusing on being context-free is slightly meaningless. (there is another category of languages which is very close to context free with the restriction that every token cannot be both "opening" and "closing" at the same time, as it is almost always the case. This category of languages can be operated on like regular languages, which is very nice)
coldtea 7y ago
A, ok. Misread your wording as doubting that, but it seems to just take the inverse position to refute it.

by jMyles 7y ago

afiori 7y ago

The point is that it requires the lexer to count whitespaces. In practice it is very uniform and can be easily converted to a context-free language as indentation and parenthesis are equivalent. The typical example is that a context-free language cannot remember numbers so a context-free parser cannot group together indentation levels. In general this tries to match something like (w^n a)* for a fixed n, which is not context free

jMyles 7y ago
...but how is this any different than a '{}' language "remembering" whether a control structure is opening, and requiring a '}' to close it? Don't these both represent the exact same amount of context (which reasonable people might disagree over which is "zero" or "non-zero")?
- afiori 7y ago
  yes, the difference is that indentation is accepting ||1||2||3||4 and |||1|||2|||3|||4 but not ||1|||2|||3||4. Here the context is remembering how many bars had the last "line". every correct indentation can be easily converted to parenthesis and viceversa (simply increase in indentation are opening brackets and decreasing are closing brackets), but it cannot be done by a context-free parser. >Don't these both represent the exact same amount of context (which reasonable people might disagree over which is "zero" or "non-zero")? the difference is in what kind of state the lexer can access. with parenthesis you remember in with a stack, you know what in what kind of block you are but know nothing of where you were. with indentation you need to remember the whitespaces on the previous line. (Haskell for example has both a indentation based syntax and a {,} context-free equivalent syntax. In this sense focusing on being context-free is slightly meaningless. (there is another category of languages which is very close to context free with the restriction that every token cannot be both "opening" and "closing" at the same time, as it is almost always the case. This category of languages can be operated on like regular languages, which is very nice)

coldtea 7y ago

A, ok. Misread your wording as doubting that, but it seems to just take the inverse position to refute it.