|
|
|
|
|
by BruceIV
4194 days ago
|
|
I've been working on a derivative parser for PEGs; it's not quite working yet, but the inherent lack of ambiguity in PEGs is helpful to the time bounds there (I think I can make it worst case cubic, and linear in a lot of common cases). I've got some ideas how to modify the algorithm to a better derivative parser for CFGs; I should be able to recognize arbitrary CFGs in linear time, and I think parse them in cubic (carrying around the set of current parse tree options is expensive, but I think if you store them as a DAG of parsing paths rather than a parse tree you can make it tolerable). |
|