4 ms·

It feels to me like this is the thesis: > Furthermore, a typical lexer will strip all whitespace from the token stream, so the parser never sees it. ...but is

by jMyles 7y ago

It feels to me like this is the thesis: > Furthermore, a typical lexer will strip all whitespace from the token stream, so the parser never sees it. ...but is that important in answering the underlying question? Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? The fact that python performs minor gymnastics around whitespace in order to achieve its control structure pattern is not per se pre-existing context in terms of its parser. If that's the conclusion that I'm being asked to reach, then I disagree with the argument.

nightcracker 7y ago
> Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? Absolutely. Any CFG can be made to ignore whitespace by dumping the nonterminal W between each symbol in each rule, and letting W -> W ' ' | W '\n' | ''.
- jMyles 7y ago
  Right - that was the point I was (perhaps awkwardly) making by posing the question that way.
ptsneves 7y ago
For me the interesting part was a cliff hanger:). How exactly a context free parser and lexer help in specification? Do such cases exist? If not why? Also why have I never heard of context free programing languages? I am trying to think of file formats and even a puny ini file has a context aware parser. Do not get me wrong with all these questions. I never heard of this topic before so I am very curious and grateful for the HN post.
- ben509 7y ago
  I think it helps with tooling, linters, refactoring tools, code generation, etc., if you have a "standard" lexer and parser. The reason being these tools can rely on reasonably standard parsing libraries to take a spec in a common format and then translate input to an AST to take actions on. If you haven't heard the term context-free, you haven't done much parsing; it's ubiquitous there.
coldtea 7y ago
>Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? Sure. What does ignoring "an entire class of legal characters" has to do with being context-free (which just means that each production rule doesn't need further context to work)? You can trivially ignore "an entire class of legal characters with (regular language compatible) regular expressions - and if so, you can express that processing as a context-free grammar...
- 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)

by jMyles 7y ago

nightcracker 7y ago

> Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? Absolutely. Any CFG can be made to ignore whitespace by dumping the nonterminal W between each symbol in each rule, and letting W -> W ' ' | W '\n' | ''.

jMyles 7y ago
Right - that was the point I was (perhaps awkwardly) making by posing the question that way.

ptsneves 7y ago

For me the interesting part was a cliff hanger:). How exactly a context free parser and lexer help in specification? Do such cases exist? If not why? Also why have I never heard of context free programing languages? I am trying to think of file formats and even a puny ini file has a context aware parser. Do not get me wrong with all these questions. I never heard of this topic before so I am very curious and grateful for the HN post.

ben509 7y ago
I think it helps with tooling, linters, refactoring tools, code generation, etc., if you have a "standard" lexer and parser. The reason being these tools can rely on reasonably standard parsing libraries to take a spec in a common format and then translate input to an AST to take actions on. If you haven't heard the term context-free, you haven't done much parsing; it's ubiquitous there.

coldtea 7y ago

>Or, to ask it differently: can a lexer which ignores an entire class of legal characters (whitespace) ever be context free? Sure. What does ignoring "an entire class of legal characters" has to do with being context-free (which just means that each production rule doesn't need further context to work)? You can trivially ignore "an entire class of legal characters with (regular language compatible) regular expressions - and if so, you can express that processing as a context-free grammar...

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)