3 ms·
They have an exponential complexity in general case, I guess that's the reason. There is a way to make them be of polynomial complexity in the worst case, but i
by Joker_vD 5y ago
They have an exponential complexity in general case, I guess that's the reason. There is a way to make them be of polynomial complexity in the worst case, but it requires quite an ingenious memoization technique, coupled with lazy evaluation.
- ahelwer 5y agoDo you have any reading about this or terms I could search to learn more?
- spekcular 5y agoThis paper gives the best algorithm I know of, and a sketch of its complexity: http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%20Daniel%20(2010)%20-%20Generalized%20Parser%20Combinators.pdf http://dinhe.net/~aredridel/.notmine/PDFs/Parsing/SPIEWAK,%2....
- deleted 5y ago[deleted]