Grammar Designer recursion question

SyntaxEditor for Windows Forms Forum

Posted 13 years ago by Anton Filimonov
Version: 4.0.0233
Avatar
Hi, I'm creating my custom language add-on using Grammar Designer. My grammar requires these NonTerminals:

PrimaryExpression :
InvocationExpression

InvocationExpression :
PrimaryExpression ParenthesisOpen arguments ParenthesisClose

In xml grammar definition I write these rules like this:

    <NonTerminal Key="PrimaryExpression" Parameters="out PrimaryExpression pr">
      <Production>
        <![CDATA[
          <%pr = null;%>
          ("InvocationExpression<@out pr@>")
          <%pr.EndOffset = this.Token.EndOffset;%>
        ]]>
      </Production>
    </NonTerminal>

    <NonTerminal Key="InvocationExpression" Parameters="out InvocationExpression expr">
      <Production>
        <![CDATA[
        <%
          PrimaryExpression pr;
          ArrayList args;
          expr = null;
        %>
        "PrimaryExpression<@out pr@>"
        'ParenthesisOpen'
        "Arguments<@out args@>"
        'ParenthesisClose'
        <%
          expr = new InvocationExpression();
          expr.Primary = pr;
          expr.Arguments = args
        %>
        ]]>
      </Production>
    </NonTerminal>
The problem is that when trying to generate semantic parser I get this error message:
Quote:

A parser generator exception occured:
Production PrimaryStatement allows for infinite left recursion


Does this mean that parser for such type of grammar can't be automatically generated? Or is there a way I should rewrite production code to make it work with Grammar Designer?

Thank you,
Anton Filimonov

Comments (1)

Posted 13 years ago by Actipro Software Support - Cleveland, OH, USA
Avatar
Correct, left recursion is not allowed with any LL(k) type parser. If you look at the code that a LL(k) parser generates, doing recursion the way you have it will cause an infinite stack recursion since the MatchPrimaryExpression method will call the MatchInvocationExpression method, which will call MatchPrimaryExpression, and so on, thus leading to a stack overflow.

I did a quick google and found this page which explains left recursion pretty well for LL(k) languages and how to alter your language to handle it.
http://www.cs.luther.edu/~leekent/tutorials/ll1.html

Sometimes eliminating left recursion can be tricky. In our C# language (for the .NET Languages add-on) we spent a little while trying to eliminate it for expressions. Our Visual Basic language development has been difficult, maybe even moreso, for the same reason.


Actipro Software Support

The latest build of this product (v2020.1 build 0400) was released 1 days ago, which was after the last post in this thread.

Add Comment

Please log in to a validated account to post comments.