Hacker News new | ask | show | jobs
by zasdffaa 1414 days 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.

1 comments

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

PEGs are ambiguous, just that that's resolved by rule ordering. From the wiki page (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"

> 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 - 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.)

You're the expert, thanks for the pointers!