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

Louis Mullie wrote:
> First of all I must say I am only a high school student, and I've
been
> looking into creating parsers for a month or so only;
<snip>
> I have come up with a way (it's probably wrong) to use my
> LL parser and still parse left-recursive grammars seamlessly;
> I'd like you to have a look at it, and if it's wrong, please
> tell me why it wouldn't work. Here it is, in pseudo-code :
<snip>
> add := add '+' term
> term := num
<php code snipped>


Notice that left-recursive rules need at least one non left-recursive
alternative, which is missing from your example above. I guess you
intended to write:


> add := add '+' term
            | term //a non left-recursive alternative
> term := num


Anyway, it's a known fact that left-recursive rules such as


    A: A B
      | C


can be transformed into


    A: C B*


or, in your case:


    Add: term ('+' term)*


Since you have complete control over the generation of the resulting
tree (or so it seems) there's nothing preventing you from building the
tree already in order, without the need to fiddle with the placement of
the productions' elements:


<example language=pseudo-basic>
    Sub ParseAdd(Tree As TreeNode)
    Dim This As New TreeNode("Add: Term")
        ParseTerm(This)


        Do While Accept("+")
        Dim Temp As New TreeNode("Add: Add + Term")
            Temp.Add This
            This = Temp


            ParseTerm(This)
        Loop


        Tree.Add This
    End Sub
</example>


Notice that the code processes the non left-recursive rule(s) first,
but postpones adding the resulting nodes to the tree. On the contrary,
if the tail of the left recursive part is found (the while loop), the
current node (this) is added to a new node labeled after the
left-recursive rule. The tail is then processed, becoming a sibling of
the previous node.


This is a very simple approach, of course, and may or may not match
your needs. Personally, even being a great fan of Recursive Descent, I
find any RD approach to handle more than so many rules (your mileague
may vary) cumbersome. So, for larger grammars, I'd suggest you try to
build a Shift Reduce parser...


HTH,


Regards,


Branco Medeiros.

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