On Saturday, 7 July 2012 at 15:39:52 UTC, Roman D. Boiko wrote:
On Saturday, 7 July 2012 at 14:17:54 UTC, Tobias Pankrath wrote:Also any PEG defines a language with linear-time parsing. Some non-context-free languages can be described with PEG.Proper CFG parsers all are liner-time anyway.To be picky here:The languages that can be parsed in linear time are a strict subset of CFGs.
Interesting, I thought that PEG ⊂ CFG holds.