On Sun, Mar 31, 2013 at 03:06:30PM +0900, Kota Mizushima wrote: > 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.
And that was precisely my point. You did not mention that this is most important part (Name of section is "3.3 properties"). Also you did not mentioned counter in paper. It looks that main idea of paper is how to insert cut. Actually that section is completely useless. When one incorporated first, follow optimization and does not increase counter when it is predicated then for any cut that you may insert counter is already zero. You only increased possibility of bugs without any real benefit. As for real parsers do you know implementation other at yapp that implements [1]? Also experiments in [1] are java and xml. Java grammar was designed to minimize stack usage, and xml is simple. How does your results change when you parse c for example? > [1] [1]Packrat Parsers Can Handle Practical Grammars in Mostly Constant > Space (PDF). Kota Mizushima, Atusi Maeda, and Yoshinori > Yamaguchi. [2]PASTE, June > > 2010.[3]http://ialab.cs.tsukuba.ac.jp/~mizusima/publications/paste513-mizushima.pdf > > 2013/3/29 Ondřej Bílka <[4]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 > [5]http://kam.mff.cuni.cz/~ondra/thesis.pdf > > Ondra > > > Juancarlo Añez > > _______________________________________________ > PEG mailing list > [6]PEG@lists.csail.mit.edu > [7]https://lists.csail.mit.edu/mailman/listinfo/peg > > -- > Kota Mizushima > e-mail: [8]mizuk...@gmail.com > > References > > Visible links > 1. > http://ialab.cs.tsukuba.ac.jp/~mizusima/publications/paste513-mizushima.pdf > 2. http://cseweb.ucsd.edu/paste2010/program.html > 3. > http://ialab.cs.tsukuba.ac.jp/~mizusima/publications/paste513-mizushima.pdf > 4. mailto:nel...@seznam.cz > 5. http://kam.mff.cuni.cz/~ondra/thesis.pdf > 6. mailto:PEG@lists.csail.mit.edu > 7. https://lists.csail.mit.edu/mailman/listinfo/peg > 8. [GMCP] Compose a new mail to mizuk...@gmail.com > > https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=mizuk...@gmail.com -- Interference from lunar radiation _______________________________________________ PEG mailing list PEG@lists.csail.mit.edu https://lists.csail.mit.edu/mailman/listinfo/peg
