Re: Seamlessly parsing left-recursive grammars with LL parsers ?

Hello,
Thanks a lot for your replies.
Mr. O'Connor :
There's, as noted by Mr. Medeiros, an error in my above grammar : "add :=
add '+' term" should be "add := add '+' term | term", and I unwillingly
tried to fix it in my code: reverseOrder(symbol.rule) + '|' + symbol;
should simply be reverseOrder(symbol.rule);


Don't forget that the input is also reversed, so add "'+' '*' term" would
become "term '*' '+' add", but "4 +* 5" would also be flipped to "5 *+ 4",
which stays correct.


Mr. Medeiros :
When I wrote "seamlessly", I meant without the parse tree being changed:
this would have to occur behind the scenes, the end user not 'knowing' the
tool transformed the grammar. The tool is a recursive descent parser that
dynamically accepts any grammar. I have (unsuccessfully) tried to
implement a non-table-driven LALR parser; I am looking into recursive
ascent-descent and recursive ascent parsing as an alternative, but it
still involves computing states.


Since I wrote this, I've read up a lot on left-recursion, and I've
questionned myself if, on a parse tree T generated by a grammar G`
(created from G in which left-recursion was removed with the standard
(Ullman's) method), it was possible to apply a set of transformations such
that T` would've been the same tree as the one generated by G (G` => T and
G => T`). Mathematically, it looked perfectly possible, and I've come up
with another (simple) algorithm, which also restores the left
associativity of the operators :


For each child of node N {
        if child is a newly created non-terminal (i.e., of the form A`) :
                    for each sub-child of child {
                              if child is a newly created non-terminal (i.e., of the form
A`) : store in variable 'rest' and break the loop
                              apply algorithm on sub-child;
                              add sub-child to N;
                    }


                    create new node N` with the same type as N;
                    add N to N`;
                    if rest is &#949; then continue;<>
                    apply algorithm to rest;
                    add each child of rest to N;


}


1. Original tree
                                                        Expr ---
                                                      / \
                                                  Term Expr' --
                                                      | / | \
                                              Factor + Term Expr' ------
                                                      | | | \ \
                                                    Int Factor + Term Expr'
                                                                                                  | |
                                                                                              Factor &#949;
                                                                                                  |
                                                                                                Int
==========================================================
2. Added sub-child to N
                                                        Expr ---
                                                      / \
                                                  Term Term
                                                      | | (Rest)
                                              Factor Factor Expr' ------
                                                      | | | \ \
                                                    Int Factor + Term Expr'
                                                                                                  | |
                                                                                              Factor &#949;
                                                                                                  |
                                                                                                Int
3. Added rest
                                                                  Expr -----------------
                                                                / | |
                                                              / | |
                                                        Expr --- + Term
                                                      / \ |
                                                  Term Term Factor
                                                      | | |
                                              Factor Factor Int
                                                      | |
                                                    Int Factor


4. The above tree is the same tree as the one produced by an LR parser :




                                                      Expr
                                                  / \
                                              Expr + Term
                                          / | \ \
                                      Expr + Term Factor
                                        | | |
                                    Term Factor Int
                                        | |
                                    Factor Int
                                        |
                                      Int


Any thoughts on this approach to the problem ?


Regards,


--
Louis Mullie <louis@mulliemedia.com>

Return to the comp.compilers page.
Search the comp.compilers archives again.