3 ms·

> 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

> 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

> 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!