How to obtain an AST with expected operator precedence?

Hi William,

I believe it's working out that way since we can't have left recursion in an LL parser.

If additiveExpression was rewritten as: Then there would be left recursion on the first non-terminal and the grammar wouldn't compile. There isn't a built-in way to change this around.

You can write custom tree construction classes to do anything to the AST. That's one very nice feature of the grammar, since it is fully extensible. You could write one with logic that say for the additive expression would look at the right expression and if it is additive, rotate the tree so that the first and second terms are put together as an additive expression and then chain on the third, thus making your tree.

I apologize for not including more detail in my question. I do understand an LL parser does not handle left recursion and I understand that the example grammar production in your reply does not work. That was something we had already tried and discovered did not work.

From what I can see from experimenting with the parser generated by the grammar specifications, the resulting AST is truly a left-most derived tree (which is as it should be for an LL parser). This also explains the ordering of the nodes in the AST for the example grammar in GettingStarted04a through GettingStarted04c, which I assume was intentionally on the simple side as it is intended as an introduction to the grammar specifications for your product. None the less, this example does not generate an AST that would result in the order of execution that would be expected of a C-like language, nor even the order of evaluation of arithmetic expressions as taught in elementary school.

We are in the midst of converting our DSL (domain specific language) for writing equity trading systems to .net and WPF. Our current product uses a “hand written” editor in VB6 and the corresponding lexer and parser were written by hand in C++. We are very excited to see how easy it was to build an editing environment in your Syntax Editor for our language. We are now trying to finish up the code generation for our language and would be equally excited to discover that using the Syntax Editor grammar specification features would result in a parser that can generate an AST for our language without a lot of further coding.

My question still stands: Do you have an example of a grammar where the operator precedence and associative order of execution for arithmetic expressions is as expected in a C like language? Presumably this problem has been solved by Actipro for the .net language add on product for the Syntax Editor, as both C# and VB have arithmetic operator precedence and are left associative for order of execution similar to that in our language. I am not asking for C# or VB grammars, just an example of a grammar specification in using the Syntax Editor grammar classes which illustrates how to do operator precedence and a left associative order of execution.

Modifying the syntax tree as it is constructed is an option I do not know how to evaluate, as modifying the tree as it is generated may adversely impact the intellisense prompts we use. This would take some analysis to see what the fallout would be - unless you have an example of how to do modify the AST for operator precedence and left associative order of execution. I am still learning how the tree construction class works, and with my current level of understanding, could not see how your suggestion above to modify the AST would be implemented. Beyond the documentation and the sample code supplied with the Syntax Editor product, do know of any other materials that would help me learn how to use the grammar specification and tree construction features in your product?

Hi William,

Unfortunately it's a limitation of LL parsers in general and we don't currently have anything to work around it. At some point we may be able to make some special tree construction node that specifically handles this but we don't have one right now. Our C# and VB languages in the add-on also work the same as the Simple grammar right now and have the same right associativity.

That being said, let me clarify the scenario more since I don't believe it's too much of an issue.

Operator precedence is always properly handled now, and the right associativity only occurs in operators within the same precedence level (really, same non-terminal production).

So "a - b + c" will read in the AST as "a - (b + c)" but that doesn't make a difference since +/- operators are at the same precedence order.

Say we make it more complex. "a * b + c" will read in the AST as "(a * b) + c", which as you can see properly applied operator precedence order.

Further, in the first case with just addition and subtraction, you can tell if the original input was "a - b + c" or "a - (b + c)" by whether a ParenthesizedExpression surrounds the "b + c" expression or not.