3 ms·

> But it is a solution... the grammar is no longer ambiguous if you define choice as giving priority to one side or the other. Sure it's no longer ambiguous to

> But it is a solution... the grammar is no longer ambiguous if you define choice as giving priority to one side or the other. Sure it's no longer ambiguous to the computer. But the important question is: is it ambiguous to a human? Take the "dangling else" problem. What does this mean in C? if (a) if (b) f(); else g(); If you defined your grammar with a PEG, the answer is: whichever alternative you put first (if-with-else or if-without-else). But that answer doesn't help someone actually trying to use your language unless they go and read your PEG. What user wants to do that? Worse, it keeps language designers from being aware when they accidentally put gotchas like this into their languages. The PEG tools can't warn you, because to a PEG tool there is no problem. As a real-world example of this, it was not discovered that ALGOL 60 had a "dangling else" ambiguity until the language had already been published in a technical report. A CFG-based tool could have warned the designers about the ambiguity, but with PEG-based tools you are designing blind.

chrisseaton 9y ago
Your example seems to support my argument, not yours! Dangling else's are solved by formally expressing a fixed priority in the grammar. > unless they go and read your PEG Well yes they need to read the documentation for the language... how else were they managing to write a program in it? How is it any difference from having to read the documentation to understand the precedence of different operators?
- haberman 9y ago
  Dangling else is solved by changing the definition of the language. Newer languages don't have the dangling else problem, because we learned the hard way in the 60s how to avoid it. PEG-based tools invite more mistakes like this, because they can prevent the discovering of ambiguities until it is too late to fix them. Yes, operator precedence is another example of ambiguity: we live with it because infix math is useful enough that we live with the fact that you have to learn the precedence rules. But with PEG-based tools, you can accidentally introduce ambiguities that might be easy to avoid if you just knew about them at the design stage. I would never design a language with PEG-based tools, because I would have no idea where I might be introducing pointless ambiguity.
  - chrisseaton 9y ago
    > prevent the discovering of ambiguities But there are no ambiguities to discover if you use a PEG! A language grammar defined using PEG cannot be ambiguous!
    - haberman 9y ago
      It's very strange that you keep returning to this. "Dangling else" is a problem regardless of how you write down your grammar or implement your parser. It's like sweeping a mound of dirt under the rug and then saying "by definition, there is no dirt on the rug!"
      - chrisseaton 9y ago
        I guess I just can't understand where you are coming from then. Someone said that PEGs don't solve ambiguous grammars. I said that's wrong - they do - they are no longer ambiguous. Now people are arguing about having to understand the grammar and how languages should be designed and things like that? Seems irrelevant to me. I thought there was one precise technical question - do PEGs make solve the problem of ambiguous grammars. Yes they do - they are no longer ambiguous. If you define your language using a PEG you will never have any ambiguity in your grammar. Seems solved to me!
        haberman 9y ago
        > I thought there was one precise technical question - do PEGs make solve the problem of ambiguous grammars. Yes they do - they are no longer ambiguous. Everyone understands that. We all agree that this is formally true: PEG grammars have no ambiguity. No one is disputing that. The question is whether the convention of ordered choice is useful. Does it solve conceptual ambiguities? Take tomp's example: imagine that we changed Java to resolve overloaded functions differently. Right now Java will throw an error if two overloaded functions both match a call site. Imagine that Java was changed to successfully compile the file, and resolved the ambiguity by arbitrarily picking the first matching function. Now there is no ambiguity! Just like PEGs! But is this behavior useful? I would rather know about the ambiguity, and have the compile fail.
victorNicollet 9y ago
Ambiguity of a grammar is rather unrelated to how surprising it can be to a human. Something like TypeScript: var a = { label: f() }; () => { label : f() }; These constructs look similar, but one is an object literal and the other is a block with a useless label. All of this can be implemented as an unambiguous context-free grammar. Relying on grammar ambiguity detection to find constructs surprising to humans is not very effective, if only because of the difference between how a human understands the grammar (pattern-based) and how EBNF expresses it (prefix-based).
- haberman 9y ago
  This is a red herring. Context-free grammar tools don't solve the problem of keeping a language from ever being confusing. However they do solve the problem of allowing literal ambiguity into your language. Ambiguity is strictly worse than confusion. Ambiguity means you have to communicate more information to your users: when two parses are both syntactically valid, which one does the language actually choose?
- tomp 9y ago
  > Relying on grammar ambiguity detection to find constructs surprising to humans is not very effective Well yeah, obviously, that's like relying on unittests and type system to keep your program bug free... I mean, neither can guarantee your program is going to work, but either failing means that it almost certainly won't work (well).

chrisseaton 9y ago

Your example seems to support my argument, not yours! Dangling else's are solved by formally expressing a fixed priority in the grammar. > unless they go and read your PEG Well yes they need to read the documentation for the language... how else were they managing to write a program in it? How is it any difference from having to read the documentation to understand the precedence of different operators?

haberman 9y ago
Dangling else is solved by changing the definition of the language. Newer languages don't have the dangling else problem, because we learned the hard way in the 60s how to avoid it. PEG-based tools invite more mistakes like this, because they can prevent the discovering of ambiguities until it is too late to fix them. Yes, operator precedence is another example of ambiguity: we live with it because infix math is useful enough that we live with the fact that you have to learn the precedence rules. But with PEG-based tools, you can accidentally introduce ambiguities that might be easy to avoid if you just knew about them at the design stage. I would never design a language with PEG-based tools, because I would have no idea where I might be introducing pointless ambiguity.
- chrisseaton 9y ago
  > prevent the discovering of ambiguities But there are no ambiguities to discover if you use a PEG! A language grammar defined using PEG cannot be ambiguous!
  - haberman 9y ago
    It's very strange that you keep returning to this. "Dangling else" is a problem regardless of how you write down your grammar or implement your parser. It's like sweeping a mound of dirt under the rug and then saying "by definition, there is no dirt on the rug!"
    - chrisseaton 9y ago
      I guess I just can't understand where you are coming from then. Someone said that PEGs don't solve ambiguous grammars. I said that's wrong - they do - they are no longer ambiguous. Now people are arguing about having to understand the grammar and how languages should be designed and things like that? Seems irrelevant to me. I thought there was one precise technical question - do PEGs make solve the problem of ambiguous grammars. Yes they do - they are no longer ambiguous. If you define your language using a PEG you will never have any ambiguity in your grammar. Seems solved to me!
      - haberman 9y ago
        > I thought there was one precise technical question - do PEGs make solve the problem of ambiguous grammars. Yes they do - they are no longer ambiguous. Everyone understands that. We all agree that this is formally true: PEG grammars have no ambiguity. No one is disputing that. The question is whether the convention of ordered choice is useful. Does it solve conceptual ambiguities? Take tomp's example: imagine that we changed Java to resolve overloaded functions differently. Right now Java will throw an error if two overloaded functions both match a call site. Imagine that Java was changed to successfully compile the file, and resolved the ambiguity by arbitrarily picking the first matching function. Now there is no ambiguity! Just like PEGs! But is this behavior useful? I would rather know about the ambiguity, and have the compile fail.

victorNicollet 9y ago

Ambiguity of a grammar is rather unrelated to how surprising it can be to a human. Something like TypeScript: var a = { label: f() }; () => { label : f() }; These constructs look similar, but one is an object literal and the other is a block with a useless label. All of this can be implemented as an unambiguous context-free grammar. Relying on grammar ambiguity detection to find constructs surprising to humans is not very effective, if only because of the difference between how a human understands the grammar (pattern-based) and how EBNF expresses it (prefix-based).

haberman 9y ago
This is a red herring. Context-free grammar tools don't solve the problem of keeping a language from ever being confusing. However they do solve the problem of allowing literal ambiguity into your language. Ambiguity is strictly worse than confusion. Ambiguity means you have to communicate more information to your users: when two parses are both syntactically valid, which one does the language actually choose?
tomp 9y ago
> Relying on grammar ambiguity detection to find constructs surprising to humans is not very effective Well yeah, obviously, that's like relying on unittests and type system to keep your program bug free... I mean, neither can guarantee your program is going to work, but either failing means that it almost certainly won't work (well).