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

Browse archivesActive forum topics 
Recent comments
5 hours 42 min ago
13 hours 39 min ago
13 hours 56 min ago
18 hours 16 min ago
18 hours 53 min ago
19 hours 38 min ago
19 hours 57 min ago
20 hours 21 min ago
20 hours 32 min ago
21 hours 4 min ago