If you can inline rules and eliminate direct left recursion you can eliminate iLR as well.(if you dont mind that grammar size can grow exponentialy) say we need use iLR rule X we transofm it to LR rule by taking rule Y in LR cycle, remwrite to eliminate direct LR and inline in all remaining rules in cycle. Repeat until recursion is direct.
On Sat, Dec 04, 2010 at 09:15:05AM -0700, C. Mundi wrote: > On Sat, Dec 4, 2010 at 8:07 AM, C. Mundi <[1]cmu...@gmail.com> wrote: > > On a related subject, can someone point me to any literature on > automatic grammar rewriting > to eliminate (multiply-indirect) LR?� The pattern is > > I mean besides > > [2]http://en.wikipedia.org/wiki/Left_recursion#Removing_indirect_left_recursion > . > In other words, is it possible to eliminate iLR while preserving > association?� The classic example of > switching from left to right association messing up subtraction can be > handled -- albeit clumsily -- by > rewriting as addition with the right-hand operand replaced by its additive > inverse.� But this pattern does > not generalize, for example in the case of division where the > multiplicative inverse is not guaranteed to exist. > Granted, such cases might be handled by semantic predicates, but that > seems inelegant and is contrary to > by design goal of not requiring the designer to edit the rewritten > grammar.� > > So what I should have asked was, "Is there literature on automatic > elimination if iLR which preserves association > without the need for explicit hints in the Design Grammar or predicates > added manually to the Rewritten Grammar?"� > It's ok for the rewrite algorithm to deduce its own hints, of course. > > Alternatively, if there is a formal proof that this is impossible, I'd > like to know (although I don't need to understand the proof). > > Thanks! > Carlos > > References > > Visible links > 1. mailto:cmu...@gmail.com > 2. > http://en.wikipedia.org/wiki/Left_recursion#Removing_indirect_left_recursion > _______________________________________________ > OMeta mailing list > om...@vpri.org > http://vpri.org/mailman/listinfo/ometa -- operation failed because: there is no message for this error (#1014) _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
