Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Left-associativity #387

Closed
ghost opened this issue Mar 12, 2017 · 2 comments
Closed

Left-associativity #387

ghost opened this issue Mar 12, 2017 · 2 comments

Comments

@ghost
Copy link

ghost commented Mar 12, 2017

@bd82
Copy link
Member

bd82 commented Mar 12, 2017

Have a look at this calculator example grammar it handles operator precedence.
https://github.com/SAP/chevrotain/blob/master/examples/grammars/calculator/calculator.js

Its the same pattern as used in Antlr3 and most Top Down parsers which do not support Left recursion.
Antlr3 Java Grammar expressions Example

You can also consider to not embed precedence into the grammar.
The disadvantage of this pattern is that it creates some fairly deep parse trees.

Alternative

The Swift programing language takes an interesting approach to solve this complexity
by removing the operator precedence logic from the grammar altogether.
See:
https://developer.apple.com/library/prerelease/content/documentation/Swift/Conceptual/Swift_Programming_Language/Expressions.html#//apple_ref/doc/uid/TP40014097-CH32-ID383

Note
At parse time, an expression made up of binary operators is represented as a flat list. This list is transformed into a tree by applying operator precedence. For example, the expression 2 + 3 * 5 is initially understood as a flat list of five items, 2, +, 3, *, and 5. This process transforms it into the tree (2 + (3 * 5)).

@ghost ghost closed this as completed Mar 12, 2017
@bd82
Copy link
Member

bd82 commented Mar 12, 2017

Precedence and associativity are two fundamentally different concepts, though, aren't they?

Yes, I'm sometimes a bit too focused on syntax and syntax is sometimes used for Precedence handling.
Associativity is more about what you do with the syntax you parsed.

This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant