Re:Yacc is not dead
by kragen on Saturday March 12, 2011 @09:48PM
(#2318149)
I agree that PEGs are more interesting.
Formally speaking, you can parse PEGs in worst-case linear time with a packrat parser. Practically speaking, the constant factor on that worst case is still much worse than the usual case (the number of nonterminals in your grammar is a factor of the constant factor.)
Formally speaking, you can parse PEGs in worst-case linear time with a packrat parser. Practically speaking, the constant factor on that worst case is still much worse than the usual case (the number of nonterminals in your grammar is a factor of the constant factor.)
I've written a one-page PEG compiler-compiler (interspersed with many pages of text explaining it) at https://github.com/kragen/peg-bootstrap/blob/master/peg.md.