Thanks all. I'll read these couple of papers with great interest. Dominic
2009/11/19 Sérgio Medeiros <tamp...@yahoo.com> > 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 >
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
