LanguageDev / Yoakke

A collection of libraries for implementing compilers in .NET.
https://languagedev.github.io/Yoakke/
Apache License 2.0
141 stars 8 forks source link

Allow for unary operators in the precedence table #102

Open LPeter1997 opened 3 years ago

LPeter1997 commented 3 years ago

Is your feature request related to a problem? Please describe. Recently I've met quite a few grammars that had unary prefix or postfix operators between the usual binary operator precedence table. It's kind of annoying having to write an explicit rule to handle that and then continue writing the table. It sections the table into way too many places.

Describe the solution you'd like The precedence table feature should allow for prefix and postfix operators injected.

Describe alternatives you've considered Simply [Prefix(...)] and [Postfix(...)] attributes would suffice.

A [Prefix(op1, op2)] would translate into

level_n : (op1 | op2) level_n
        | level_(n-1)

A [Postfix(op1, op2)] would translate into

level_n : level_n (op1 | op2)
        | level_(n-1)

Additional context There is a slight problem: The transformation function would have to be different for unary prefix and postfix operators. Fortunately, the parser generator doesn't check that the actually annotated method is being called, it only cares about the name, so we could just allow overloads to be defined with the same name to handle prefix and postfix cases:

[Right("^")]
[Left("*", "/", "%")]
[Left("+", "-")]
[Postfix("!")]
[Prefix("+", "-")]
[Rule("expression")]
public static int Expr(int a, IToken op, int b) => ...; // Binary
public static int Expr(IToken op, int b) => ...; // Prefix
public static int Expr(int a, IToken op) => ...; // Postfix
LPeter1997 commented 3 years ago

An even better idea to just do it all "properly". Allow for arbitrary rules to have a precedence and associativity. This way not only binary, prefix and postfix elements can be handled, but any arbitrary expression, including things like conditional expresssions.

Example (the exact properties are not clear yet):

[Rule("expr : expr '^' expr", Associativity = Right, Precedence = 8)]
[Rule("expr: expr ('*' | '/' | '%') expr", Associativity = Left, Precedence = 7)]
[Rule("expr: expr '?' expr ':' expr", Associativity = Right, Precedence = 6)]
...

Left associativity would mean that take the rule, find the rightmost recursion, and change that to a lower level reference. Right-associativity would change the leftmost one.