BTW, our parser generator, Yapp, sources can be seen from my github repository.
https://github.com/kmizu/yapp Note that Java/XML/JSON sources used in the experimentation in our paper has been cut to reduce repository size when the source is published to github. 2013/3/31 Kota Mizushima <mizuk...@gmail.com> > Hi, Ondřej. > > > I found that paper poorly writen, main idea is: > > Create counter c. In c maintain number of pending ordered choice > branches in > > current derivation. > > When c==0 then you can obviously discard entries before current > > position. > > This idea is hidden in paper and mentioned only implicitly. > > The idea you said is the same thing that we said in our paper. In our > paper[1] Section 3.3, > We explained our idea using "backtracking stack" and how cut operators > reduce size of "backtracking stack". > Counter-based approach you said is just a trivial optimization in real > parser generator implementation. > > Actually, in our parser generator (Yapp) implementation, since preparing > "real" backtracking stack explicitly sacrifices execution speed because of > too much allocation and GC, > We implemented our idea using one counter (32-bit integer) as you said. > > [1] *Packrat Parsers Can Handle Practical Grammars in Mostly Constant > Space > (PDF)<http://ialab.cs.tsukuba.ac.jp/~mizusima/publications/paste513-mizushima.pdf> > *. Kota Mizushima, Atusi Maeda, and Yoshinori Yamaguchi. > PASTE<http://cseweb.ucsd.edu/paste2010/program.html>, > June 2010. > http://ialab.cs.tsukuba.ac.jp/~mizusima/publications/paste513-mizushima.pdf > > > > > > 2013/3/29 Ondřej Bílka <nel...@seznam.cz> > >> On Thu, Mar 28, 2013 at 03:55:28PM -0430, Juancarlo Añez wrote: >> > Hello Kota, >> > I'm reading your paper more carefully now (Packrat Parsers can Handle >> > Practical Grammars in Mostly Constant Space). >> > If I understand correctly, if a cut is seen at position P in the >> input, >> > then all memoization for positions prior to P can be discarded? >> > Thanks in advance! >> > Cheers, >> > -- >> >> Not exactly, >> I found that paper poorly writen, main idea is: >> Create counter c. In c maintain number of pending ordered choice branches >> in >> current derivation. >> When c==0 then you can obviously discard entries before current >> position. >> This idea is hidden in paper and mentioned only implicitly. >> >> This is interwined with transformation that allow us say that some >> branches are not possible. >> >> How they write paper it forces you to use certain representation to >> carry transformations. This is problem as your representation is almost >> certainly incompatible. >> >> It is better to use generic optimizations (predication gives most) and get >> better space utilization for free >> >> See my thesis for other improvements, chapter 2.6 most of ideas apply >> http://kam.mff.cuni.cz/~ondra/thesis.pdf >> >> >> >> Ondra >> >> > Juancarlo Añez >> >> >> >> _______________________________________________ >> PEG mailing list >> PEG@lists.csail.mit.edu >> https://lists.csail.mit.edu/mailman/listinfo/peg >> > > > > -- > Kota Mizushima > e-mail: > mizuk...@gmail.com<https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=mizuk...@gmail.com> > -- Kota Mizushima e-mail: mizuk...@gmail.com<https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=mizuk...@gmail.com>
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
