Thanks for the explanation. Yes, makes sense from the perspective of analysis.
But as someone using context-free grammar parsers for practical problem, I need to be concerned at what the guy on the street sees, independent of how messy it might make things for the theorist or analyst. Recall that I am adapting conventional compiler technology for a slightly different use. By doing this I hope to capture a more rigor than I have seen in some (perhaps most) decompilers. One of the weird things in this Alice through the looking-glass world is that instead of *designing* a language and checking that input string are valid, we *start *from a set of strings that are known to be valid and then need to design a grammar that *covers* that. And it is okay if the designed language covers too much - it is okay to allow the grammar to recognize or accept strings that never be input. So In the upside-down world, context free ambiguous grammars simplify finding a covering set. But... we need to pay attention to exponential derivations in designing the grammar. To a large extend, I think various grammar-design rules go a long way to reducing the possibility of exponential run-time (and space). On Sun, Nov 12, 2017 at 8:45 PM, Jeffrey Kegler < [email protected]> wrote: > With respect to time complexity, the question is that the parse time is >> 2.4 or cubic with respect to exactly what? > > > The tradition is to measure time with respect to n, which n is the length > of the input in characters of some alphabet, and the time only includes > parsing time, not evaluation time. This is how Earley's algorithm can be > cubic, when the number of parses can be super-exponential, and so simply > listing every parse would be far worse than cubic. The idea here is that > you don't know how complex or simple an evaluation the applications wants, > so it would confuse things to include evaluation time. It's possible, for > example, that parsing is simply recognition -- all you want is a "yes" or > "no" as to whether the input matches the grammar. > > Again, best of luck, jeffrey > > -- > You received this message because you are subscribed to a topic in the > Google Groups "marpa parser" group. > To unsubscribe from this topic, visit https://groups.google.com/d/ > topic/marpa-parser/LSo32mQTQlw/unsubscribe. > To unsubscribe from this group and all its topics, send an email to > [email protected]. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "marpa parser" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
