I did look at some of the articles you mentioned. That idea -- starting with a space of possible parses and narrowing it down -- is what Marpa's ASF's do. Perhaps you'll find them useful.
Hope this helps, jeffrey On Sun, Nov 12, 2017 at 6:25 PM, Rocky Bernstein <[email protected]> wrote: > 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/to >> pic/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. > -- 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.
