Hi! I have prepared a draft explaining the semantics and put it available on: http://www.lua.inf.puc-rio.br/~sergio/leftpeglist.pdf
I present an operational semantics for PEGs and after I extend it in order to support left recursion. Some statements are not proved in this draft. I have a toy implementation of this semantics in Lua, using the LPEG library. An actual implementation should optimize the case of right-recursive rules, by not trying to expand the result of their matching. The semantics works for the grammar provided by Peter Goodman :-) Sérgio ----- Mensagem original ---- De: Peter Goodman <peter.good...@gmail.com> Para: peg@lists.csail.mit.edu Enviadas: Terça-feira, 17 de Novembro de 2009 21:30:12 Assunto: Re: [PEG] Res: Problem w/ nullable left recursion and trailing rules in "Packrat Parsers Can Support Left Recursion" Sérgio, I am quite interested in these semantics. I developed a PEG parser in C earlier this year as a part of a personal project and I attempted to come up with my own left recursive handling loosely based off of Warth et al. but I always had problems with cases such as: A <- A 'a' <- B B <- B 'b' <- A <- C C <- C 'c' <- B <- 'd'. That is a fairly contrived example, however, the main problems I had that I eventually could not overcome was with the intertwining/braiding of A and B. If your semantics are able to properly handle such awful grammars then I think that would be excellent and I would be really interested in reading more in-depth into them. Best Regards, Peter Goodman, http://ioreader.com 70 Winston Circle, Montreal, Quebec H9S 4X6 2009/11/17 Sérgio Medeiros <tamp...@yahoo.com>: >> Is there any more recent work that I should be aware of that corrects this? > > > I am studying left-recursion on PEGs and I am working on a new operational > semantics for PEGs that gives meaning for left-recursive rules in a grammar, > so it is another approach. > > It has some in common with the approach of Warth et al., but I think it is > simpler. > > The basic idea is based on the expansion of a nonterminal. Given the > definition: > A <- A 'a' / 'b' > > The expansion of A is as follows: > A^0 = fail > A^1 = A^0 'a' / 'b' > A^2 = A^1 'a' / 'b' > A^3 = A^2 'a' / 'b' > ... > > A nonterminal (left-recursive or not) should keep expanding while the > result of the matching increases, where expansion A^n uses the > previous result of the matching of expansion A^(n-1) > > Given the input "bac" > match A^0 = fail > match A^1 = "b" > match A^2 = "ba" > match A^3 = "b" (stops here) > > The result of the matching of A against input "bac" is "ba". > > I have a draft of this semantics and I also can give a lengthier > explanation if somebody is interested on it. > > Sérgio > > > > ____________________________________________________________________________________ > Veja quais são os assuntos do momento no Yahoo! +Buscados > http://br.maisbuscados.yahoo.com > > _______________________________________________ > PEG mailing list > PEG@lists.csail.mit.edu > https://lists.csail.mit.edu/mailman/listinfo/peg > _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg ____________________________________________________________________________________ Veja quais são os assuntos do momento no Yahoo! +Buscados http://br.maisbuscados.yahoo.com _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
