Hacker News new | past | comments | ask | show | jobs | submit login

Most parser combinator DSLs use PEGs to parse, which don't actually prevent ambiguity, but instead hide it. I strongly recommend using something that compiles your declarative grammar into LL(k) or LALR(k)



Do they hide or do they just apply order to choices. Making it impossible to be ambiguous compared to the CFG definition?

It's only sweeping under the rug, if you look at PEG under CFG rules. PEG is not CFG.

I think practice of writing industrial software that is better.


I do sometimes wonder if a lot of these arguments themselves would be less ambiguous if PEGs (or some other name of them) were formally added to Chomsky's Hierarchy of Languages between Regular Languages and the languages expressed by CFGs. Though I think it would take someone with a much more rigorous math background than myself to make the case formal enough to get it accepted.

(If it helps, and it may be a red herring, the dualism between PEGs and Parser Combinators has me thinking it's a Category Theory related "step" in the hierarchy. "Deterministic Monadic Compositions" in a reflection of DFA/NFA duals to Regular Languages might imply "Monadic Languages" as a possible name? Again, my math background is definitely not formal enough here to make actual suggestions, but maybe it sparks an idea for someone else.)


PEGs absolutely do prevent ambiguity - they don't 'hide' it - I don't even know what that would mean?

There is exactly one way a PEG can parse - there is no ambiguity at all.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: