5 ms·
PEGs are more expressive than CFGs, iirc. So use the right tool for the job. I have come to quite like PEGs and they become quite natural, once one understands
by zelphirkalt 2y ago
PEGs are more expressive than CFGs, iirc. So use the right tool for the job. I have come to quite like PEGs and they become quite natural, once one understands things like no left recursion. I also often prefer them over complex regexes.
- sparkie 2y agoIt's difficult to conclude meaningfully that any one is more expressive than the other. They parse different languages, though there is a large subset of PEGs which are also CFGs, they're not a proper superset - there are things you can parse with a CFG which cannot be parsed with PEG, and vice-versa. OTOH, when comparing LL and LR, we can conclusively say that LR are more expressive than LL because they're a proper superset - any language that can be parsed by an LL(k) grammar can be parsed by an LR(k) grammar (for same k).
- orlp 2y ago> there are things you can parse with a CFG which cannot be parsed with PEG This is not known. It is conjectured to be true because if all context-free languages could be parsed with a PEG grammar it would imply you'd have a linear-time boolean matrix multiplication algorithm, but no one has ever constructed a concrete example of a language which is context-free but not parsable with a PEG.