Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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



the other one is known, though, isn't it? there's an example of a peg parsing a non-context-free language aⁿbⁿcⁿ in ford's dissertation?


Yes.




Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

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

Search: