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 <rocky.bernst...@gmail.com> 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 < > jeffreykeg...@jeffreykegler.com> 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 >> marpa-parser+unsubscr...@googlegroups.com. >> 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 marpa-parser+unsubscr...@googlegroups.com. > 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 marpa-parser+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
