Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

Writing Interpreters, Compilers and Translators in Perl

by Moron (Curate)
on May 24, 2007 at 09:10 UTC ( [id://617189]=perlquestion: print w/replies, xml ) Need Help??

Moron has asked for the wisdom of the Perl Monks concerning the following question:

Dear monks,

I am currently in the planning stage of writing a 60 min. tutorial for YAPC Europe with the above title. The contents list I have planned so far is:

- Introduction: Mapping the technical territory

- Industrial and Commercial application of interpreters, translators and compilers written in Perl.

- The Starting Point: Grammar.

- Relevant Perl code design strategy

- Lexical analyser and Thrower - generic opportunities in Perl and comparison with C-implementation.

- Interpreters, design impact for some high volume throughput applications.

- Compiler and translator parser; parser tree construction and traversal in Perl.

- Code generation for translators implemented in Perl.

- Compiler code generation with Perl

- Porting with virtual and real machines.

- Pre-testing considerations

- CPAN resources, limitations for commercial and industrial application.

- other resources and limitations

I'd be grateful of any feedback, things you'd like to hear about under this topic, suggestions about the topic or subtopics, length, anecdotes from experience, offers to review the draft etc., or perhaps Perl 6 considerations I might want to address early etc. or any other comments that might help me assure the quality and usefulness of this tutorial.

Thanks in advance, sincerely, the M. __________________________________________________________________________________

^M Free your mind!

Replies are listed 'Best First'.
Re: Writing Interpreters, Compilers and Translators in Perl
by rinceWind (Monsignor) on May 24, 2007 at 10:40 UTC

    I look forward to your talk in Vienna.

    I presume you are going to cover Damian's Parse::RecDescent - I would hope that you do so in some detail. Although it doesn't cover every situation, it is a tool that can enable parsing applications to be developed rapidly. When it comes to P::RD's autotrees, I wrote a module Parse::RecDescent::Topiary that assists in getting the trees in the shape you want them (properly constructed objects), rather than how Parse::RecDescent generates them.

    It may be worth covering the history, and including YACC and LEX in the scope. Knowledge of bottom up parsers and how they differ from top down, is useful.

    --
    wetware hacker
    (Qualified NLP Practitioner and Hypnotherapist)

      Thanks very much for your reply

      Yes, Parse::RecDescent is obviously within the scope, but as you also suggest, it's not a panacea for all cases and has a number of non-generic impositions.

      Your own module resolves some of those and so will also get some coverage in my tutorial.

      In the tutorial I will try to represent an unbiased choice of a) programming the relevant software by integration of CPAN modules versus b) from scratch or at least from an unassuming code design basis, although from-scratch takes more time to explain. I'll kick that off during the section "relevant code design", showing the two ways to go, again avoiding bias. I also feel that OO Perl should be a conscious choice during code design rather than a given and I feel I should also give people a free choice between OO and procedural Perl, without me imposing one or other on them. (oops I forgot to define audience-level in the OP -- updating ... )

      I will now add a short section on grammar definition - I was going to downgrade the grammar definition part to below subtopic visibility on the grounds that it's general rather than Perl-specific, but because Parse::RecDescent needs it, I have a good enough excuse after all! (updating contents list ... whirr, click).

      I'll also take your point about covering top-down versus bottom-up - thanks a lot! I was anyway going to go even further back in history than you suggest and very briefly explain the original unix lex and yacc approach (update: actually maybe even further back, because there are kinds of interpreters that can't use yacc) and then work forward from there so that Perl beginners with general programming knowledge gained elsewhere don't feel they just landed on the planet Zartog!

      __________________________________________________________________________________

      ^M Free your mind!

Re: Writing Interpreters, Compilers and Translators in Perl
by lin0 (Curate) on May 24, 2007 at 13:00 UTC

    Hi Moron,

    It looks great! It made me want to go there :-)

    Two things that I would add are:

    1. A sort of introduction as to why study compiler construction and why it is a good idea to do Compilers in Perl. Maybe you want to cover that in the Mapping of the technical territory?
    2. A brief description of some of the Properties of a Good Compiler. For example, it has to generate correct code ;-), it has to conform completely to the language specifications, and it should be able to handle programs of arbitrary size.

    Overall, very good outline. Good Job!

    Cheers,

    lin0
Re: Writing Interpreters, Compilers and Translators in Perl
by samizdat (Vicar) on May 24, 2007 at 14:10 UTC
    Blessed and revered Moron,

    I applaud your dedication and gastronomical fortitude. :)

    I think you need to make your talk much more focused. Marshall Kirk McKusick may be able to cover the history of BSD in two hours while swilling a pitcher of beer, but the rest of us mortals need to distill our talks down to one or two major points, made really well.

    I'd suggest that you build (at most) two examples during your hour, sprinkling a few tidbits of history and theory on top. If you make the examples good, they can make your two hundred line "Links" addendum make sense.

    Don Wilde
    "There's more than one level to any answer."
      I see what you're getting at. Yes, I do have some ideas for keeping it focused. And yes I can always cut detail to "a bit of history and a bit of theory" to achieve that and yes I can refer to such things by linkage or reference - but I believe it is precisely by keeping an eye on the bigger picture of the basic design of such software in preparing the talk that I feel I can best make the pieces in the puzzle make sense for the selected audience level.
      __________________________________________________________________________________

      ^M Free your mind!

Re: Writing Interpreters, Compilers and Translators in Perl
by blazar (Canon) on May 24, 2007 at 13:03 UTC
    or perhaps Perl 6 considerations I might want to address early

    That's certainly a topic I would like to hear about. We recommend people to try to avoid naive regex based parsing and lexing all the time for anything that is moderately complex, and to use a proper dedicated tool instead, like P::RD. But the whole idea of regexen being promoted to "rules" possibly gathered in grammars sheds a new light on the issue and indeed in a very exciting manner.

      Thanks, a good pointer - I'll have to investigate the Perl 6 rules facilities more thoroughly now and see how much I can bring on board. Do you know of any reference links to help me there?
      __________________________________________________________________________________

      ^M Free your mind!

        I'll have to investigate the Perl 6 rules facilities more thoroughly now and see how much I can bring on board. Do you know of any reference links to help me there?

        Well, there's Synopsis 5. Also see the comment about the standard grammar in a recent article by TimToady.

Re: Writing Interpreters, Compilers and Translators in Perl
by diotalevi (Canon) on May 24, 2007 at 15:07 UTC

    I have a few very small points. AI::Prolog, another language written directly in perl now also allows embedding of perl code. We have eval. Further, I found out last week that it works to dynamically generate Inline::C code and use its Inline->bind( C => $SRC ) to generate fast functions.

    ⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

Re: Writing Interpreters, Compilers and Translators in Perl
by Youdaman (Acolyte) on May 25, 2007 at 02:32 UTC
      thanks, a nice link!
      __________________________________________________________________________________

      ^M Free your mind!

Re: Writing Interpreters, Compilers and Translators in Perl
by educated_foo (Vicar) on May 24, 2007 at 13:39 UTC
    Sounds interesting. I would skip the section on testing, since that's a real can of worms, and is covered exhaustively elsewhere. Also, what target language(s) are you using? IMHO you should describe translation to either C or Perl, since the former can give bare-metal performance, and the latter interoperates easily with an existing Perl program.
      I shortend it from "testing considerations" - there are one or two things worth saying that are well-defined and bounded, but to avoid the "can", I'll change that back to a well-defined non-wormish specification :). I'm trying to be generic about what to translate into in regard to translators, but Perl has to be the implementation language - that's a given I think for this conference!
      __________________________________________________________________________________

      ^M Free your mind!

        It seems like you'll have to include some examples, or maybe a single running example throughout. For (meta-)example:
        1. An interpreter for a basic arithmetic language.
        2. One for a fancier version.
        3. Turning that into a compiler.
        4. Doing something fancy with the compiler.
        Doing this in a generic way would be terribly hard. It would be much easier to choose an example source and target language, and the semantic mismatches between source and target would substantially shape your talk.

        One really cool example here would be to "compile" a subset of Ruby into Perl, to show just how little semantic difference there is. Another would be compiling X to C, since you would have to describe implementing X's runtime. Another would be translating to Perl (see e.g. my Language::FP, which has both an interpreter and a compiler), since it wouldn't require introducing a third language (even though Perl elaborate semantics make the translation tricky).

Re: Writing Interpreters, Compilers and Translators in Perl
by Limbic~Region (Chancellor) on May 29, 2007 at 12:30 UTC
    Moron,
    I bookmarked this thread when I first saw it because I didn't have time to read it through then. I would appreciate it if you could provide a link to the presentation once it is finished. Oh, and if you do go the arithmetic route - I highly recommend Parse::Yapp over Parse::RecDescent. It handles precedence and associativity much easier.

    Cheers - L~R

      I completely agree. I also strongly recommend Parse::Eyapp. It fixes some Parse::Yapp bugs and provides extensions ala Parse::RecDescent.

      Casiano

      Yes, I have provisionally planned to cover Parse::Lex and Parse::Yapp if these are what you mean - thanks for the reminder. But I am not yet sure how much detail any given module will get in the available airtime.

      I'll have the slides ready in a few weeks in a mail-sendable format, but I am not sure if it is right to put them online - people should have to go to the conference to consume the material, shouldn't they? If significant conference material were available online people might stay at home!

      __________________________________________________________________________________

      ^M Free your mind!

        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
        I'll have the slides ready in a few weeks in a mail-sendable format, but I am not sure if it is right to put them online - people should have to go to the conference to consume the material, shouldn't they? If significant conference material were available online people might stay at home!

        You wrote this twice, but he wrote: "I would appreciate it if you could provide a link to the presentation once it is finished." I'm pretty sure he meant after the conference. In any case reading a presentation and attending to it are quite different experiences: in many cases I find slides to be instructive, but without the accompanying speech much is lost. So those who really want to be there will do in any case and there are also quite a lot of people that won't come anyway, maybe because they live abroad.

        Moron,
        Significant conference material is available online. Typically it is not posted until after the conference is over and it is usually the discretion of the author. If you do not want to publish it, that is fine. My reason for not attending conferences has nothing to do with the availability of the content online but rather family obligations.

        Cheers - L~R

Re: Writing Interpreters, Compilers and Translators in Perl
by ambrus (Abbot) on May 31, 2007 at 09:07 UTC

    Compiler in perl... I don't know if you've seen this one.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://617189]
Front-paged by naikonta
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others scrutinizing the Monastery: (4)
As of 2024-03-28 20:23 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found