Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical

Re: Clunky parsing problem, looking for simple solution

by jepri (Parson)
on Jun 17, 2002 at 05:38 UTC ( #175028=note: print w/replies, xml ) Need Help??

in reply to Clunky parsing problem, looking for simple solution

I have to agree with our AnoniMonk here, although a little more politely. It really depends how you are parsing it. Since this would indeed be a non-problem in parse-recdescent, I can assume you are not using it.

Your problem may be that you are not following the informal rules closely enough. You need some kind of 'scope', so that when you hit a THEN or an ELSE statement, your program goes 'new scope, start evaluating expressions again'. That way your program is compartmentalised and the routines don't have to know if they are in a nested structure or not.

e.g. if you hit an ELSE IF, your program should think to itself "got and ELSE, mark a label here, start evaluating normally, here's an if, call the if routine'. There's no need for it to know that it is inside an if routine already.

If you stick with the rules then issues like this become trivial (just remember to ascend from your recursive routines when you get to the end of the line).

And like our AnoniMonk says, Parse::RecDescent is fantastic for this kind of problem, but I find it makes register allocation much harder than it should be (in fact it beat me totally). With IMCC it should all be easy, though.

I didn't believe in evil until I dated it.

  • Comment on Re: Clunky parsing problem, looking for simple solution

Replies are listed 'Best First'.
Re: Re: Clunky parsing problem, looking for simple solution
by clintp (Curate) on Jun 17, 2002 at 16:38 UTC
    (background aside for other's listening, AM's deserve no replies)

    First let me clarify a few things. Firstly, within the BASIC interpreter itself, there's no formal "grammar" at all. Lines are dissected to find the statement being executed (the first token following the line number) and each statement's execution block has hard-wired into it a series of possible templates for that statement.

    As one rude monk asked, "The art of language design hasn't been around for 25+ years without having come up with solutions to this kind of thing (...) did you do any research into language design before embarking on this project?" As a matter of fact I did. 25 years ago when I first saw this language, and shortly thereafer obtained assembler source code for implementations of the language, I learned how it was done. When I thought to recreate it for the Parrot CPU this is how it happened. The total number of assembly instructions is about 2k (for interactive mode, runtime, parser, everything).

    When I get around to porting a pig like QuickBasic, I'll think about using a more open design with a formal grammar.

    So discounting comments directed towards the interpreter itself, I'm left with the GW-BASIC to Parrot BASIC Perl script. This is (so far, and can remain) a simple filter. I don't want to teach it BASIC. The only statement's that's "special" is IF..THEN..ELSE. If the parser gets confused, it gets confused. This is what GW-BASIC was like.

    (specifically to jepri)

    Looking at talexb's solution and your description, I think I'm going to write a small state machine to process tokens on an IF..THEN line and arrange them accordingly. kvale's notes triggered a few light-bulbs as well. I'll post something shortly...

      I think the academic computer world now calls small state machines Discrete Finite Automations or something. I read about how to do it in a lecture series I pulled of the net. Available upon request, or google for it. The upshot was that it was an interesting way of approaching the problem. To me it sounds like you are flogging yourself unnecessarily, but each to his own :)

      I didn't believe in evil until I dated it.

        the academic computer world now calls small state machines Discrete Finite Automations or something

        I think a lot of terms are used, this being one of them. Determinisitic Finite State Automata, Turing Machines, Finite State Machines, Finite Sate Automata, State Transition Machine are all terms ive seen.

        Yves / DeMerphq
        Writing a good benchmark isnt as easy as it might look.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://175028]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (7)
As of 2016-09-30 02:14 GMT
Find Nodes?
    Voting Booth?
    Extraterrestrials haven't visited the Earth yet because:

    Results (562 votes). Check out past polls.