Member-Access Left Recursion

SyntaxEditor for WPF Forum

Posted 9 years ago by Gary Ranson
Avatar
Can somebody please help ...

I'm trying to implement a grammer to support the "member-access" syntax but I am failing miserably. I've remove the left recursion out from everywhere but this remains Non-Terminal.

This is a snippet from my grammar ....
            primaryExpression.Production = literal[Vx.Exp] > AstFrom(Vx.Exp)
                | simpleName[Vx.Exp] > AstFrom(Vx.Exp)
                | functionAccessMethod[Vx.Exp] > AstFrom(Vx.Exp)
                | parenthesizedExpression[Vx.Exp] > AstChildFrom(Vx.Exp)
                | memberAccess[Vx.Exp] > AstFrom(Vx.Exp)
                /*  | invocationExpression*/
                 ;
            /*
             * simple-name: identifier 
             * */

            simpleName.Production = identifier.ToTerm().ToProduction().SetLabel(Vx.Name)
            > Ast("SimpleName", AstFrom(Vx.Name));

            functionAccessMethod.Production = @identifier[Vx.Name] + @openParenthesis + argumentList[Vx.Args].Optional() + @closeParenthesis
            > Ast("FunctionAccessExpression", AstFrom(Vx.Name), AstFrom(Vx.Args));

            /*
             * parenthesized-expression: (   expression   ) 
             */
            parenthesizedExpression.Production = @openParenthesis + expression[Vx.Exp] + @closeParenthesis
            > Ast("ParenthesizedExpression", AstFrom(Vx.Exp));

            /*            
            member-access: primary-expression   .   identifier
            */

            memberAccess.Production = primaryExpression[Vx.Prefix] + @dotOperator + @identifier[Vx.Name]
            > Ast("MemberAccess",AstFrom(Vx.Prefix), AstFrom(Vx.Name));
And you will see that the memberAccess production refers to primaryExpression - and therefore Left Recursion.

Is there someone who can please help me?

Regards,

Gary Ranson.

[Modified at 04/29/2011 07:02 AM]

[Modified at 04/29/2011 07:21 AM]

Comments (2)

Posted 9 years ago by Actipro Software Support - Cleveland, OH, USA
Avatar
Hi Gary,

Yes that can get tricky, and we ran into it when building the C# grammar in the .NET Languages Add-on.

What we did is move out all the simpler pieces (like literal, simpleName, etc.) to a new primaryExpressionCore non-terminal. Then we ended up making primaryExpression something like this:
primaryExpression.Production = primaryExpressionCore["exp"] + (
        @dot + simpleName["name"]
            > Ast<MemberAccess>().SetProperty(e => e.Name, AstFrom("name"))
        | @openParenthesis + argumentList["args"].Optional() + @closeParenthesis.OnErrorContinue()
            > Ast<InvocationExpression>().AddToCollectionProperty(e => e.Arguments, AstChildrenFrom("args"))
        ...
    ).OnErrorContinue().ZeroOrMore().SetLabel("postfix")
    > new PrimaryExpressionTreeConstructionNode();
This design allows us to have a number of "postfix" items (like member access) after the root primary expression.

You'll note we created a special custom tree construction node to handle proper tree construction for this scenario. It's code is similar to this:
private class PrimaryExpressionTreeConstructionNode : TreeConstructionNodeBase {

    public override IAstNode CreateNode(IAstNodeMatchCollection matches) {
        if ((matches != null) && (matches.Count == 2)) {
            var exprNode = matches[0].Node as Expression;

            // If there are postfix operators, wrap the contained expression with them...
            if (matches[1].Node.HasChildren) {
                foreach (var wrapperNode in matches[1].Node.Children) {
                    MemberAccess memberAccessNode = wrapperNode as MemberAccess;
                    if (memberAccessNode != null) {
                        memberAccessNode.TargetExpression = exprNode;
                        exprNode = memberAccessNode;
                    }
                    else {
                        InvocationExpression invocationExprNode = wrapperNode as InvocationExpression;
                        if (invocationExprNode != null) {
                            invocationExprNode.TargetExpression = exprNode;
                            exprNode = invocationExprNode;
                        }
                    }
                }
            }

            return exprNode;
        }
        return null;
    }
            
}
Hope that helps!


Actipro Software Support

Posted 9 years ago by Gary Ranson
Avatar
Thank you.

That was the inspiration I needed.
The latest build of this product (v2019.1 build 0683) was released 1 month ago, which was after the last post in this thread.

Add Comment

Please log in to a validated account to post comments.