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>
_______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
