3 ms·
> 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 languag
by 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.