> 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.
Yes. This is not most important part in our paper since the notion of our cut operator and its effectiveness were described in our earlier work. However, our earlier paper has been written in Japanese. Then, the overview of cut was needed. That's all. And I think that it's not need to mention counters in our paper since it's **trivial** optimization and the all implementation detail cannot be written in our paper that has page limit. > It looks that main idea of paper is how to insert cut. It's not correct in a precise sense. the main idea of the paper is how to insert cut **automatically* without changing grammar meanings. > 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. What do you mean? Certainly, hand-written cut operators may increase bugs. Then, we explored the way to decrease space complexity without hand-written cut operators in our paper. Of course, our methods is too conservative to cover all practical grammars. But, we don't say such things and I've written as the followings: " We believe that this problem can be solved by some extensions to our methods (e.g. increasing the number of lookahead nonterminal expressions like LL(k)). We intend to address the problem in future work." (Sorry for not continuing this research since I work as a software engineer in a company). Although forms of writing paper maybe poor, it seems that you misunderstand about our paper and the proposed methods. 2013/03/31 18:19 "Ondřej Bílka" <nel...@seznam.cz<https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=nel...@seznam.cz> >: > 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<https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=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<https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=PEG@lists.csail.mit.edu> > > [7]https://lists.csail.mit.edu/mailman/listinfo/peg > > > > -- > > Kota Mizushima > > e-mail: > > [8]mizuk...@gmail.com<https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=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<https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=nel...@seznam.cz> > > 5. http://kam.mff.cuni.cz/~ondra/thesis.pdf > > 6. > > mailto:PEG@lists.csail.mit.edu<https://mail.google.com/mail/u/0/?view=cm&fs=1&tf=1&to=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> > > > 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
