Re^3: Writing Interpreters, Compilers and Translators in Perl

Good luck, this is one of my favourite topics ;)

There is a recent new animal called Parse::Eyapp which deserves having a look. Also Manning has released recently a book on the subject of parsing with Perl.

Would be nice to have a review of table-driven top-down parsing and possible speed advantage of (almost)infinite backtracking: look at packrat parsing in Wikipedia and google for SLK, and then you could tell us how to do a fast version of Parse::RecDescent, and if you start the project maybe i'll even help you ;).

PPI has some interesting comments in its doc about parsing in general. It would be really nice to have a survey of the various techniques used in the various sucessful parsers written in Perl (even the ones with C parts) so that it could be extrapolated a useful set of rules for a generic useful (fast, easy to use) parser generator .

Another interesting line of thought is "chunk parsing" and give the illusion of "stream" regexes. Obviously what is needed is a smart tokenizer. One simple approach is to have various chunk levels, you drive a simple m//gc regex-based lexer with a small chunk (string); if match you add chunk to have always minimum length and if no-match you add it another chunk and some kind of heuristics which enable switching to something faster if parsing comment-like or quotish-like (pretokenizing on big chunks)...some ideas can be taken from IO::Tokenizer, IO::Mark and the such

Cheers --stephan

Comment on Re^3: Writing Interpreters, Compilers and Translators in Perl

Replies are listed 'Best First'.
Re^4: Writing Interpreters, Compilers and Translators in Perl by casiano (Pilgrim) on Jul 14, 2007 at 11:08 UTC
Congratulations for the topic and the interesting outline. I look forward for the talk. Thank you Stephan for mentioning Parse::Eyapp. I thought none paid previously attention to it :-( Parse::Eyapp is fully compatible with Parse::Yapp. It fixes a few bugs that were in Parse::Yapp and -sure - it introduces new ones :-) Furthermore, Parse::Eyapp extends Parse::Yapp with concepts similar to those found in Parse::RecDescent: autoactions, automatic generation of trees, etc. There are, however, a few new functionalities: Translation Schemes and a Tree Transformation language to mention two. If you need any assistance with the module I will be more than glad to help. Have a look at the examples directory inside the distribution. Also, there is a brief tutorial at http://nereida.deioc.ull.es/~pl/eyapsimple/ The source code for this tutorial can be found at http://nereida.deioc.ull.es/~pl/eyapsimple/source.tgz Best Casiano	[reply]
Re^4: Writing Interpreters, Compilers and Translators in Perl by Moron (Curate) on May 30, 2007 at 14:47 UTC
Thanks for your suggestions. I'll definitely be taking some of them on board. In regard to your comment about smart tokenising, I have a sort of negatively-matching lexer for that I call the antilexer which I might include but only if it survives as a sensible alternative after CPAN modules have been thorughly investigated. For large continuous streams and such-like where I can't use the usual module, I use instance variables that have rules, recursion depths at which to start building trees, callback functions definable as "parser exits" (that's something I picked up from old prePerl technoliogy) to be invoked at certain points so that the tree never needs to be completed but can be acted on or code generated on the fly and I am sure there are other special needs situations I haven;t yet thought of! It's a horrible minefield but I love it too ;);) after all - if the subject were reducible to bolting modules together and that working for every case, it wouldn't be so interesting, would it? __________________________________________________________________________________ ^M Free your mind!	[reply]
Re^5: Writing Interpreters, Compilers and Translators in Perl by sgt (Deacon) on May 30, 2007 at 16:15 UTC
...More thoughts... There is a new edition of the book by Grune et al Parsing Techniques. It should be out or close. Often people think about LR or LL parsing but the first edition of "Parsing Techniques" talks about starting anywhere! which is interesting at least in the sense of having maybe two-staged tokenizing <chess>?!</chess> then there is HOP::Lexer. I haven't played much but it is quite slower than anything based on Parse::Yapp. Still a mixed approach could be nice... finally using 5.9.x or more one can plug a different regexp engine, say a small one that permits "streaming" Update: [SDF] seems also interesting. cheers --stephan	[reply]