Remove assigned actions

[pluralia]

Motivation to have assigned actions

Shape the semantic model after:

• left-factoring (that handles left-recursion) / operator precedence
• handling long common prefixes: XAnnotation here is a prefix for XtendClass, XtendInterface ...

Motivation to remove

• Hard to learn and use — contradiction with the idea of Langium to be simple
• Changes in Chevrotain (LL(*) and left-recursion elimination) handle problems above

Problems related to removal

• Experience users used to assigned actions and successfully use it (-> Xtext)
• We tight to Chevrotain too much

Proposal

Don't remove assigned actions, but work on user experience improvement.

Add more use cases of assigned actions in documentation

• It simplifies understanding of the concept
• Nice idea to add many trees corresponding to actions and infers keyword usages

Add a special syntax for infix operators

• The most common use case of assigned actions for newbies — operators precedence. If we add special syntax for that, learning assigned actions concept can be postponed.
• We were asked for libraries for common grammar patterns; infix operators precedence is one of such patterns.
• How infix operators syntax can look like:

Expression:
    PrimaryExpression | BinaryExpression;

infix_op
BinaryExpression:
    left=PrimaryExpression op=[['*', '/'], ['+', '-']] right=PrimaryExpression;
 
PrimaryExpression:
    '(' Expression ')' | {infer NumberLiteral} value=NUMBER;

Compare it with the current version:

Expression:
    Addition;

Addition infers Expression:
    Multiplication ({infer BinaryExpression.left=current} operator=('+' | '-') right=Multiplication)*;

Multiplication infers Expression:
    PrimaryExpression ({infer BinaryExpression.left=current} operator=('*' | '/') right=PrimaryExpression)*;

PrimaryExpression infers Expression:
    '(' Expression ')' | {infer NumberLiteral} value=NUMBER;

[luan-xiaokun]

The most common use case of assigned actions for newbies — operators precedence. If we add special syntax for that, learning assigned actions concept can be postponed.

This is true for me. For people like me who don't know much about parser, it will take some time to understand the tree-rewriting actions.

Bringing new syntax for defining infix operators sounds interesting to me, it can lower the barrier for the users and make the grammar definition more concise. I have a question on this idea, though: there are also prefix and postfix operators, such as the logical negation operator !, unary plus / minus + / -, etc, and in most cases, how can we define their precedence with respect to these infix operators?

For example, the precedence of infix arithmetic operators is usually higher than logical negation, which has higher precedence than logical AND and logical OR, and how can we define such precedence (*, / > ! > && > ||)?

[Lotes]

The shortest notation I know is for LR parsers like Yacc or Bison:

%left + -
%left * /
%right ^

e ::= e [+-/*^] e | NUM

There is also an algorithm for that, but you can also transform the rules internally to shape how it is normally accomplished.

[pluralia]

@luan-xiaokun, @Lotes, my initial idea of precedence syntax implementation is inspired by the Haskell library megaparsec (look at operatorTable). To shape the idea better, I'd propose such syntax for the Langium DSL:

op_root
Expression:
    [ [ prefix "-" Unary, prefix "+" Unary ]
    , [ infix "*" Binary, infix "/" Binary ]
    , [ prefix "!" Unary ]
    , [ infix "&&" Binary ]
    , [ infix "||" Binary ]
    ]

op_leaf
Primary:
     '(' Expression ')' | {infer NumberLiteral} value=NUMBER;

Here a hierarchy top is marked with a keyword op_root and a primary -- with a keyword op_leaf. A primary looks like a usual parser rule, but top is a list of lists. Each item of each list consists of an operator type (prefix, infix, postfix), the operator and a type that is responsible for the operator -- each such type will inherit op_root automatically (Expression in our case). Besides, each item is grouped by precedence so, than earlier a list appears in the operator list, than higher precedence is.
Internally such syntax will be "unfolded" in current Langium DSL syntax -- the example above will generate:

Expression:
    Or;

Or infers Expression:
    And ({infer Binary.left=current} operator='||' right=And)*;

And infers Expression:
    Not ({infer Binary.left=current} operator='&&' right=Not)*;

Not infers Expression:
      {infer Unary} operator='!' value=Addition
    | Addition;

Addition infers Expression:
    Multiplication ({infer Binary.left=current} operator=('+' | '-') right=Multiplication)*;

Multiplication infers Expression:
    NegPos ({infer Binary.left=current} operator=('*' | '/') right=NegPos)*;

NegPos infers Expression:
      {infer Unary} operator=('-' | '+') value=Primary
    | Primary;

Primary infers Expression:
    '(' Expression ')' | {infer NumberLiteral} value=NUMBER

[pluralia]

I like the prefix/postfix information, infix misses an associatvity, like left or right.

Wow, you're right! To fix it, I propose to add keywords infixr, infixl and infix when no associativity. Example above demonstrates left associativity everywhere.

The syntax looks unusual, but I have seen different syntaxes than you.

We should think more about syntax. But I hope the core idea is already there.

The unfolding idea reminded me of macros like in C or Elixir…

I also took this from Haskell: it actively uses the term "syntax sugar" when you have a lot of cool, non verbose syntax that internally is unfolded in a Haskell subset that represents only core functionality.

[msujew]

I have a feeling like this shouldn't be a core grammar language feature. It adds a ton of complexity for very little gain. You could implement it in a separate project/language though, which then generates a normal Langium grammar.

Note that one of our main goals of Langium is to stay simple. While features such as these might help the user in the short term, they massively increase maintenance burden on our side in the long term.

[luan-xiaokun]

I like the prefix/postfix information, infix misses an associatvity, like left or right.

This comment reminds me that I incorrectly defined some right-associative operators to be left-associative, such as logical implication '->'. It is true that we may forget to consider the associativity of operators when concentrating on the precedence, I think providing more examples in the document may be helpful.

For example, we can extend the arithmetic example with more operators to cover more cases, such as unary plus minus (prefix), suffix increment and decrement (postfix), ternary conditional (ternary operator & right-associative).

[Lotes]

@msujew That is true, it is like syntactic sugar, no real value, only a shortcut. But we should have some guides about operators, precedence and associativity. Maybe some task for me.

@luan-xiaokun normally left-associativity is done by left-recursive rules (me = me op next | next) and right-associativity by right-recursion (me = next op me | next). In Xtext and Langium the patterns are slightly different, but accomplish the same in the end.

• me is the current rule
• op are the operator tokens
• next is the next stronger operator rule

[spoenemann]

Note that one of our main goals of Langium is to stay simple. While features such as these might help the user in the short term, they massively increase maintenance burden on our side in the long term.

@msujew I generally agree, but we should still experiment with conceptual extensions of the grammar language to see whether we find a notation that looks good. The result should be simpler (more readable and understandable) from the user's perspective, so a tradeoff on the implementation side is possible.