4 ms·
It'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 w
by sparkie 2y ago
It'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.