User loginNavigation 
Pathological Problems in ParsingHello LtU! I have composed an algorithm for a garbagecollected LLderived parser for extracting parse forests in a dynamicsyntax language. I'm not really sure how to go about calculating the time complexity though, I have no formal training. So far all my tests seem to indicate that the algorithm is O(n^2) in the length of the input in the worstcase and linear in the best case. Since it has been stated that GLR can take O(n^3) in the worst case i find my result surprising. I have been unable to locate any examples that trigger the O(n^3) behaviour in the GLR though. So my question is, does do readers of LtU have any examples of really pathological grammars? By disnesquick at 20111205 09:17  LtU Forum  previous forum topic  next forum topic  other blogs  5755 reads

Browse archivesActive forum topics 
Recent comments
1 hour 57 min ago
6 hours 57 min ago
7 hours 8 min ago
9 hours 13 min ago
16 hours 3 min ago
17 hours 36 min ago
20 hours 40 min ago
20 hours 54 min ago
21 hours 11 min ago
21 hours 56 min ago