4 ms·

Well, first you don't seem to understand what 'ambiguity' means in the context of parsing "Nobody writes a parser that has a random decision..." which is weird.

Well, first you don't seem to understand what 'ambiguity' means in the context of parsing "Nobody writes a parser that has a random decision..." which is weird. It's a very establish meaning here. Then you say "I guess I don't understand why we use languages for writing grammars that let you express ambiguity in the first place" without any suggestions, or even if this is possible, or if it is, whether the resulting language might be too constrained to be useful (interesting question though. Edit: even context-free grammars have ambiguity, eg. the regexp "aa" is legal but ambiguous for sentence "aaa"). Then "I think parser generators were a mistake" which is surreal. If you've ever had the tedious misfortune to write one manually, you know how much faster it is to have the computer do that work. So I am thrown a bit here.

chrisseaton 4y ago
If you choose to specify your language using a class of grammar which permits ambiguity, then you have to resolve that ambiguity. If instead you choose to specify your language using a class of grammar which does not permit ambiguity, then you don't have to resolve it because it never existed. That's the point. The suggestion is to either specify your language using a formal grammar which does not permit ambiguity, or to specify your language imperatively, using a reference parser. I've written many parsers, both using parser generators and manually. I'd choose to write one manually. In fact, I'm currently looking at a project at work right now to take a generated parser and to re-write it manually because it's easier to work with. That's a pretty mainstream opinion amongst professionals in the industry - not sure why you think it's surreal or why it's throwing you.
- zasdffaa 4y ago
  > If you choose to specify your language using a class of grammar which permits ambiguity, then you have to resolve that ambiguity. I added an edit after which you may not have seen: even context-free grammars have ambiguity, eg. the regexp "aa" is legal but ambiguous for sentence "aaa" So what grammar can you suggest that's even weaker than context-free (to make expressions of ambiguity impossible) and still useful? > I'd choose to write one manually Matter of taste I guess.
  - chrisseaton 4y ago
    > So what grammar can you suggest that's even weaker than context-free (to make expressions of ambiguity impossible) and still useful? It doesn’t need to be weak. For example use a Parsing Expression Grammar.
    - zasdffaa 4y ago
      PEGs are ambiguous, just that that's resolved by rule ordering. From the wiki page (https://en.wikipedia.org/wiki/Parsing_expression_grammar#Ambiguity_detection_and_influence_of_rule_order_on_language_that_is_matched https://en.wikipedia.org/wiki/Parsing_expression_grammar#Amb...) "A PEG parser generator will resolve unintended ambiguities earliest-match-first, which may be arbitrary and lead to surprising parses"
      - chrisseaton 4y ago
        > PEGs are ambiguous You're misunderstanding the rhetoric there - they're unambiguous by construction because they deterministically resolve earliest-match-first - a well-defined rule. It's impossible to write an ambiguous PEG. Any grammar you write in a PEG is never ambiguous. A grammar you write using a CFG can be ambiguous. As your own link says "Unlike CFGs, PEGs cannot be ambiguous". Or read Ford's original paper https://bford.info/pub/lang/peg.pdf https://bford.info/pub/lang/peg.pdf - they solve "the ambiguity problem by not introducing ambiguity in the first place". (I wrote a much-cited thesis on PEGs and issues such as ambiguity in precedence parsing - I'm not just talking off the top of my head here.)
        zasdffaa 4y ago
        You're the expert, thanks for the pointers!

chrisseaton 4y ago

If you choose to specify your language using a class of grammar which permits ambiguity, then you have to resolve that ambiguity. If instead you choose to specify your language using a class of grammar which does not permit ambiguity, then you don't have to resolve it because it never existed. That's the point. The suggestion is to either specify your language using a formal grammar which does not permit ambiguity, or to specify your language imperatively, using a reference parser. I've written many parsers, both using parser generators and manually. I'd choose to write one manually. In fact, I'm currently looking at a project at work right now to take a generated parser and to re-write it manually because it's easier to work with. That's a pretty mainstream opinion amongst professionals in the industry - not sure why you think it's surreal or why it's throwing you.

zasdffaa 4y ago
> If you choose to specify your language using a class of grammar which permits ambiguity, then you have to resolve that ambiguity. I added an edit after which you may not have seen: even context-free grammars have ambiguity, eg. the regexp "aa" is legal but ambiguous for sentence "aaa" So what grammar can you suggest that's even weaker than context-free (to make expressions of ambiguity impossible) and still useful? > I'd choose to write one manually Matter of taste I guess.
- chrisseaton 4y ago
  > So what grammar can you suggest that's even weaker than context-free (to make expressions of ambiguity impossible) and still useful? It doesn’t need to be weak. For example use a Parsing Expression Grammar.
  - zasdffaa 4y ago
    PEGs are ambiguous, just that that's resolved by rule ordering. From the wiki page (https://en.wikipedia.org/wiki/Parsing_expression_grammar#Ambiguity_detection_and_influence_of_rule_order_on_language_that_is_matched https://en.wikipedia.org/wiki/Parsing_expression_grammar#Amb...) "A PEG parser generator will resolve unintended ambiguities earliest-match-first, which may be arbitrary and lead to surprising parses"
    - chrisseaton 4y ago
      > PEGs are ambiguous You're misunderstanding the rhetoric there - they're unambiguous by construction because they deterministically resolve earliest-match-first - a well-defined rule. It's impossible to write an ambiguous PEG. Any grammar you write in a PEG is never ambiguous. A grammar you write using a CFG can be ambiguous. As your own link says "Unlike CFGs, PEGs cannot be ambiguous". Or read Ford's original paper https://bford.info/pub/lang/peg.pdf https://bford.info/pub/lang/peg.pdf - they solve "the ambiguity problem by not introducing ambiguity in the first place". (I wrote a much-cited thesis on PEGs and issues such as ambiguity in precedence parsing - I'm not just talking off the top of my head here.)
      - zasdffaa 4y ago
        You're the expert, thanks for the pointers!