Again thanks. I have a backlog of things to do, but I will look into Marpa ASFs. I still have a lot to learn.
On Sun, Nov 12, 2017 at 9:37 PM, Jeffrey Kegler < [email protected]> wrote: > 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 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.
