4 ms·

> I just have to write these {} things all over the place because every other language is a gramatically bloated mess. In what way are context-free languages "

> I just have to write these {} things all over the place because every other language is a gramatically bloated mess. In what way are context-free languages "a grammatically bloated mess?" Whitespace delimited languages like Python have context-sensitive grammars. Now that is a mess.

WorldMaker 9y ago
Most bracket languages aren't strictly context-free either (the Dangling else problem [1] alone somewhat guarantees that most programming languages are not strict, unambiguous CFGs in a mathematic sense). There's no right/wrong/superiority in context-free versus context-sensitive, they are tools in the toolbox and not really "levels in a superiority hierarchy". [1] https://en.wikipedia.org/wiki/Dangling_else https://en.wikipedia.org/wiki/Dangling_else
- sedachv 9y ago
  > There's no right/wrong/superiority in context-free versus context-sensitive Dismissing the whole field of formal language theory with that statement is so bogus, it "is not even wrong." There are tools and techniques for parsing context-free languages that are impossible with context-sensitive languages. Parser generators, structured editing, metacompilers, composable grammars; those are all impossible with context-sensitive languages. Context-free languages are faster to parse, easier to write compilers/interpreters for, and much easier to write tooling for (editors, linters, etc). Ambiguous context-free grammars are a very different thing from context-sensitive grammars. You can't point to the former and say "so whitespace sensitivity is ok."
  - WorldMaker 9y ago
    I'm not dismissing anything. I'm pointing out the boundaries are fuzzier than hard cut-offs and it's weird to assign moral superiority to one side of the grass or the other. Most parser generators/composable grammar tools, etc, have tools for dealing with context sensitive sections of a language, just as they use regular expressions for tokenizing and allow regular language sub-languages. I can point to ambiguous context-free grammars and say whitespace sensitivity is ok, because the tools to fix the one are often the same to fix the other. (Ambiguous context-free grammars do turn out to make context sensitive languages, because it's a blurry line in the grass between them.) Whitespace sensitivity is one of the easier context sensitivity challenges to embed as a sub-language in an otherwise (mostly) context-free language, because you can represent it entirely as pseudo tokens from a simply modified lexing phase in a traditional CFG parser. Python is an easy and clear proof, as that is exactly what it did (Python is also not purely a CFG after whitespace tokenization because of also how it handles the dangling else, but we've already mentioned those weeds). Even if you don't find the boundaries between the classes of languages fuzzy (and Parser Combinators and PEG grammars have a lot to say here), context-sensitive languages are a tool in a growing toolbelt, not a "complex" evil to be demonized.
    - sedachv 9y ago
      > it's weird to assign moral superiority to one side of the grass or the other Algorithmic complexity is not "moral superiority." The whole point of formal language theory is to show how the different languages differ in terms of how difficult they are to work with. > just as they use regular expressions for tokenizing and allow regular language sub-languages That is because regular languages are a subset of context-free languages. There is nothing special to "allow" there. > I can point to ambiguous context-free grammars and say whitespace sensitivity is ok, because the tools to fix the one are often the same to fix the other. No they are not. Precedence rules and extra lookahead will help with ambiguous context-free grammars but not with context-sensitive ones. There is also a whole class of algorithms, such as GLR, specialized to handle ambiguous CFGs efficiently. > Whitespace sensitivity is one of the easier context sensitivity challenges to embed as a sub-language in an otherwise (mostly) context-free language, because you can represent it entirely as pseudo tokens from a simply modified lexing phase in a traditional CFG parser. That statement is nonsense. There is no way to "embed" a context-sensitive language in a CFG. What you are saying is that it is "easy" to make a whole context-sensitive parser just to produce a context-free language so you can pass that to another CFG parser. That is not "easy," that is bolting crap onto other crap.
      - WorldMaker 9y ago
        > Algorithmic complexity is not "moral superiority." The whole point of formal language theory is to show how the different languages differ in terms of how difficult they are to work with. Chomsky's hierarchy was designed for production from categories of languages. That it doubles as a useful rule of thumb for algorithmic complexity in parsing is a fascinating dualism in mathematics. That those same rules of thumb reflect basic automaton abstractions is even more fascinating. This is also where it seems the clearest analogy lies to why I find your arguments to "complexity" so useless. It sounds to me like a strange steampunk form of the "640k is all anyone will ever need" fallacy: "why use Turing machines when Pushdown automatons will do just fine?" Yes, there are a lot of great tools for working with CFGs, just as we've pushed Regular Expressions far past the boundaries of formal Regular Languages, we push these same tools past the boundaries of formal CFGs. We aren't actually constrained by the limits of only using Deterministic Finite Automata or Pushdown Automata in our programming, we have vast Church-Turing–level state machines at our power completely and easily capable of tracking contexts/states. The "context" in a whitespace-sensitive language is "how many spaces have you seen recently?". This is not a hard question, this is not some mystical "context sensitivity" that needs an entire "context-sensitive language parser". It's a handful of counters. That is the very definition of easy, that's the built-in basics of your average Church-Turing machine, keep a number on the tape and update it as necessary. Python's specification for the language defines the language in a CFG BNF just as the majority of brackets languages. The one concession to its whitespace sensitivity is that it expects from its lexer INDENT and DEDENT tokens. Those tokens are added simply by counting whitespace between lines, seeing if there is a < or > relationship. After those tokens are in the stream (along with the rest of the tokens defined in their associated (Mostly) Regular Languages) it is parsed by whatever CFG automaton/algorithm the Python team wants (LR, GLR, LALR, PEG, etc). That's not "bolting crap onto other crap" by most stretches of the imagination, that's using a pretty simple stack of tools that any programmer should be able to (re-)build, and not one at all more complicated than (and in fact built entirely inside) the classic tokenizer/lexer feeding a parser stack.

WorldMaker 9y ago

Most bracket languages aren't strictly context-free either (the Dangling else problem [1] alone somewhat guarantees that most programming languages are not strict, unambiguous CFGs in a mathematic sense). There's no right/wrong/superiority in context-free versus context-sensitive, they are tools in the toolbox and not really "levels in a superiority hierarchy". [1] https://en.wikipedia.org/wiki/Dangling_else https://en.wikipedia.org/wiki/Dangling_else

sedachv 9y ago
> There's no right/wrong/superiority in context-free versus context-sensitive Dismissing the whole field of formal language theory with that statement is so bogus, it "is not even wrong." There are tools and techniques for parsing context-free languages that are impossible with context-sensitive languages. Parser generators, structured editing, metacompilers, composable grammars; those are all impossible with context-sensitive languages. Context-free languages are faster to parse, easier to write compilers/interpreters for, and much easier to write tooling for (editors, linters, etc). Ambiguous context-free grammars are a very different thing from context-sensitive grammars. You can't point to the former and say "so whitespace sensitivity is ok."
- WorldMaker 9y ago
  I'm not dismissing anything. I'm pointing out the boundaries are fuzzier than hard cut-offs and it's weird to assign moral superiority to one side of the grass or the other. Most parser generators/composable grammar tools, etc, have tools for dealing with context sensitive sections of a language, just as they use regular expressions for tokenizing and allow regular language sub-languages. I can point to ambiguous context-free grammars and say whitespace sensitivity is ok, because the tools to fix the one are often the same to fix the other. (Ambiguous context-free grammars do turn out to make context sensitive languages, because it's a blurry line in the grass between them.) Whitespace sensitivity is one of the easier context sensitivity challenges to embed as a sub-language in an otherwise (mostly) context-free language, because you can represent it entirely as pseudo tokens from a simply modified lexing phase in a traditional CFG parser. Python is an easy and clear proof, as that is exactly what it did (Python is also not purely a CFG after whitespace tokenization because of also how it handles the dangling else, but we've already mentioned those weeds). Even if you don't find the boundaries between the classes of languages fuzzy (and Parser Combinators and PEG grammars have a lot to say here), context-sensitive languages are a tool in a growing toolbelt, not a "complex" evil to be demonized.
  - sedachv 9y ago
    > it's weird to assign moral superiority to one side of the grass or the other Algorithmic complexity is not "moral superiority." The whole point of formal language theory is to show how the different languages differ in terms of how difficult they are to work with. > just as they use regular expressions for tokenizing and allow regular language sub-languages That is because regular languages are a subset of context-free languages. There is nothing special to "allow" there. > I can point to ambiguous context-free grammars and say whitespace sensitivity is ok, because the tools to fix the one are often the same to fix the other. No they are not. Precedence rules and extra lookahead will help with ambiguous context-free grammars but not with context-sensitive ones. There is also a whole class of algorithms, such as GLR, specialized to handle ambiguous CFGs efficiently. > Whitespace sensitivity is one of the easier context sensitivity challenges to embed as a sub-language in an otherwise (mostly) context-free language, because you can represent it entirely as pseudo tokens from a simply modified lexing phase in a traditional CFG parser. That statement is nonsense. There is no way to "embed" a context-sensitive language in a CFG. What you are saying is that it is "easy" to make a whole context-sensitive parser just to produce a context-free language so you can pass that to another CFG parser. That is not "easy," that is bolting crap onto other crap.
    - WorldMaker 9y ago
      > Algorithmic complexity is not "moral superiority." The whole point of formal language theory is to show how the different languages differ in terms of how difficult they are to work with. Chomsky's hierarchy was designed for production from categories of languages. That it doubles as a useful rule of thumb for algorithmic complexity in parsing is a fascinating dualism in mathematics. That those same rules of thumb reflect basic automaton abstractions is even more fascinating. This is also where it seems the clearest analogy lies to why I find your arguments to "complexity" so useless. It sounds to me like a strange steampunk form of the "640k is all anyone will ever need" fallacy: "why use Turing machines when Pushdown automatons will do just fine?" Yes, there are a lot of great tools for working with CFGs, just as we've pushed Regular Expressions far past the boundaries of formal Regular Languages, we push these same tools past the boundaries of formal CFGs. We aren't actually constrained by the limits of only using Deterministic Finite Automata or Pushdown Automata in our programming, we have vast Church-Turing–level state machines at our power completely and easily capable of tracking contexts/states. The "context" in a whitespace-sensitive language is "how many spaces have you seen recently?". This is not a hard question, this is not some mystical "context sensitivity" that needs an entire "context-sensitive language parser". It's a handful of counters. That is the very definition of easy, that's the built-in basics of your average Church-Turing machine, keep a number on the tape and update it as necessary. Python's specification for the language defines the language in a CFG BNF just as the majority of brackets languages. The one concession to its whitespace sensitivity is that it expects from its lexer INDENT and DEDENT tokens. Those tokens are added simply by counting whitespace between lines, seeing if there is a < or > relationship. After those tokens are in the stream (along with the rest of the tokens defined in their associated (Mostly) Regular Languages) it is parsed by whatever CFG automaton/algorithm the Python team wants (LR, GLR, LALR, PEG, etc). That's not "bolting crap onto other crap" by most stretches of the imagination, that's using a pretty simple stack of tools that any programmer should be able to (re-)build, and not one at all more complicated than (and in fact built entirely inside) the classic tokenizer/lexer feeding a parser stack.