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

Browse archivesActive forum topics 
Recent comments
58 min 19 sec ago
2 hours 39 min ago
12 hours 22 min ago
12 hours 36 min ago
13 hours 25 min ago
14 hours 11 sec ago
15 hours 10 min ago
16 hours 19 min ago
20 hours 51 min ago
23 hours 2 min ago