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  5228 reads

Browse archivesActive forum topics 
Recent comments
11 hours 24 min ago
11 hours 28 min ago
11 hours 39 min ago
13 hours 18 min ago
1 day 8 hours ago
1 day 9 hours ago
1 day 11 hours ago
1 day 14 hours ago
1 day 21 hours ago
1 day 23 hours ago