[pypy-dev] New Javascript parser in the works

Carl Friedrich Bolz cfbolz at gmx.de
Fri Apr 27 21:36:25 CEST 2007


Hi Leonardo!

Leonardo Santagada wrote:
 > Done man, now I will be writing tons of tests, I just need to get the
 > first ones to work. They are in test_parser.py

I just looked at the current state of affairs, and while the grammar
seems to be getting more complete, there is still only a couple of
tests, and those that are there are failing. Ok, it's your time but I
can't say I like this approach.

Just looking at the grammar made me note the following problem:

Something like the following is wrong:

additiveexpression : multiplicativeexpression "+" additiveexpression
                    | multiplicativeexpression "-" additiveexpression
                    | multiplicativeexpression
                    ;

The problem is that something like "5 - 3 - 3" with this grammar will
give you a parse tree that essentially looks like the following:

      additiveexpression
     /|\
    / | \
   5  -  additiveexpression
        /|\
       / | \
      3  -  3

And evaluating this tree gives 5, instead of the correct -1.

Unfortunately solving this is not trivial. In theory the grammar rule
should look like this:

additiveexpression : additiveexpression "+" multiplicativeexpression
                    | additiveexpression "-" multiplicativeexpression
                    | multiplicativeexpression
                    ;

which does not work, since then you have a left recursion, which is not
supported. In theory there could be a nice grammar transformer that
removes the left recursion for you (which is simple and always possible)
together with a nice tree transformer that makes the tree look
correctly (which is not so simple). Until then, you can use the
following workaround:

additiveexpression : multiplicativeexpression "+" >additiveexpression<
                    | multiplicativeexpression "- >additiveexpression<
                    | <multiplicativeexpression>
                    ;

which will lead to a wrong tree originally, but the tranformer will
tranform the tree into this:

   additiveexpression
     / |  |  | \
    /  |  |  |  \
   5   -  3  -   3

which is not as nice, since additiveexpression has more children than
only three but at least it's easy to find out what is correct. You have
to make sure then that when you transform the tree into the nodes you
use for interpretation that you do the right thing then.

Oh, another small thing: would you mind not using tabs in the grammar? I
know it is not a python file, but somehow the number of spaces per tab
is different between your and my editor, so it makes it a bit annoying
for me to look at. Do you have local changes? Otherwise I could do a
tab-removing checkin.

Cheers,

Carl Friedrich



More information about the Pypy-dev mailing list