"Another not done marker added after this one. Must be done before this."

I'm working on intellij-elixir and I've had success implementing left associative operators using the `left` rule annotation in Elixir.bnf based on the patten in intellij-haxe's https://github.com/JetBrains/intellij-haxe/blob/master/grammar/haxe.bnf, but I've come to the first right-associative operators, `++, --, .., <>` and I'm not sure how do implement them.  I tried the following,

{   parserClass="org.elixir_lang.parser.ElixirParser"   extends="com.intellij.extapi.psi.ASTWrapperPsiElement"   extends("atom|(binary|unary)Operation|value")=expression   extends("(addition|hat|multiplication)Operation")=binaryOperation   name("unaryOperation")="`not`, `~~~`, `!`, `+`, `-`, `^`, Atom, Char Token, Number, Heredoc, or Sigil"   psiClassPrefix="Elixir"   psiImplClassSuffix="Impl"   psiPackage="org.elixir_lang.psi"   psiImplPackage="org.elixir_lang.psi.impl"   elementTypeHolderClass="org.elixir_lang.psi.ElixirTypes"   elementTypeClass="org.elixir_lang.psi.ElixirElementType"   tokenTypeClass="org.elixir_lang.psi.ElixirTokenType"   tokens = [     COMMENT = "regexp:#[^\r\n]*(\n|\r|\r\n)?"   ] } // expressionList is optional to handle code-less file that contains only EOL between blank lines and order comment // lines elixirFile ::= EOL* (expressionList EOL*)? // In alphabetical order /* Unlike other binary operation, additionOperations cannot begin with EOLs: if there are EOLs, then the +/-    is interpreted as unaryOperation */ left additionOperation ::= DUAL_OPERATOR EOL* multiplicationOperationList /* The list as a whole is left inner as left inner emulates right associativity for the rule to the left, which is     */ private left inner additionOperationList ::= multiplicationOperationList additionOperation* atom ::= COLON (ATOM_FRAGMENT | quote) fake binaryOperation ::= expression + {   methods = [     left = "/expr[0]"  // will be @NotNull as far as we have "+" in the expression     right = "/expr[1]" // "expr" is the name of the auto-calculated child property (singular or list)   ] } charList ::= CHAR_LIST_PROMOTER              interpolatedCharListBody              CHAR_LIST_TERMINATOR charListHeredoc ::= CHAR_LIST_HEREDOC_PROMOTER EOL                     interpolatedCharListBody                     CHAR_LIST_HEREDOC_TERMINATOR expression ::= twoOperationList private expressionList ::= expression (EOL+ expression)* left hatOperation ::= EOL* HAT_OPERATOR EOL* unaryOperationList private hatOperationList ::= unaryOperationList hatOperation* private interpolatedCharListSigil ::= TILDE INTERPOLATING_CHAR_LIST_SIGIL_NAME CHAR_LIST_SIGIL_PROMOTER interpolatedCharListBody CHAR_LIST_SIGIL_TERMINATOR private interpolatedCharListBody ::= (interpolation | CHAR_LIST_FRAGMENT | VALID_ESCAPE_SEQUENCE)* private interpolatedHeredocCharListSigil ::= TILDE INTERPOLATING_CHAR_LIST_SIGIL_NAME CHAR_LIST_SIGIL_HEREDOC_PROMOTER EOL                                              interpolatedCharListBody                                              CHAR_LIST_SIGIL_HEREDOC_TERMINATOR private interpolatedHeredocRegex ::= TILDE INTERPOLATING_REGEX_SIGIL_NAME REGEX_HEREDOC_PROMOTER EOL                                      interpolatedRegexBody                                      REGEX_HEREDOC_TERMINATOR SIGIL_MODIFIER* private interpolatedHeredocSigil ::= TILDE INTERPOLATING_SIGIL_NAME SIGIL_HEREDOC_PROMOTER EOL                                      interpolatedSigilBody                                      SIGIL_HEREDOC_PROMOTER SIGIL_MODIFIER* private interpolatedHeredocStringSigil ::= TILDE INTERPOLATING_STRING_SIGIL_NAME STRING_SIGIL_HEREDOC_PROMOTER EOL                                            interpolatedStringBody                                            STRING_SIGIL_HEREDOC_TERMINATOR private interpolatedHeredocWords ::= TILDE INTERPOLATING_WORDS_SIGIL_NAME WORDS_HEREDOC_PROMOTER EOL                                      interpolatedWordsBody                                      WORDS_HEREDOC_TERMINATOR SIGIL_MODIFIER* private interpolatedRegex ::= TILDE INTERPOLATING_REGEX_SIGIL_NAME REGEX_PROMOTER interpolatedRegexBody REGEX_TERMINATOR SIGIL_MODIFIER* private interpolatedRegexBody ::= (interpolation | REGEX_FRAGMENT | VALID_ESCAPE_SEQUENCE)* private interpolatedSigil ::= TILDE INTERPOLATING_SIGIL_NAME SIGIL_PROMOTER interpolatedSigilBody SIGIL_TERMINATOR SIGIL_MODIFIER* private interpolatedSigilBody ::= (interpolation | SIGIL_FRAGMENT | VALID_ESCAPE_SEQUENCE)* private interpolatedStringSigil ::= TILDE INTERPOLATING_STRING_SIGIL_NAME STRING_SIGIL_PROMOTER interpolatedStringBody STRING_SIGIL_TERMINATOR private interpolatedStringBody ::=  (interpolation | STRING_FRAGMENT | VALID_ESCAPE_SEQUENCE)* private interpolatedWordsBody ::= (interpolation | WORDS_FRAGMENT | VALID_ESCAPE_SEQUENCE)* interpolation ::= INTERPOLATION_START expressionList? INTERPOLATION_END private literalCharListBody ::= CHAR_LIST_FRAGMENT* private literalCharListSigil ::= TILDE LITERAL_CHAR_LIST_SIGIL_NAME CHAR_LIST_SIGIL_PROMOTER literalCharListBody CHAR_LIST_SIGIL_TERMINATOR private literalHeredocRegex ::= TILDE LITERAL_REGEX_SIGIL_NAME REGEX_HEREDOC_PROMOTER EOL                                 literalRegexBody                                 REGEX_HEREDOC_TERMINATOR SIGIL_MODIFIER* private literalHeredocSigil ::= TILDE LITERAL_SIGIL_NAME SIGIL_HEREDOC_PROMOTER EOL                                 literalSigilBody                                 SIGIL_HEREDOC_TERMINATOR SIGIL_MODIFIER* private literalHeredocStringSigil ::= TILDE LITERAL_STRING_SIGIL_NAME STRING_SIGIL_HEREDOC_PROMOTER EOL                                       literalStringBody                                       STRING_SIGIL_HEREDOC_TERMINATOR private literalHeredocWords ::= TILDE LITERAL_WORDS_SIGIL_NAME WORDS_HEREDOC_PROMOTER EOL                                 literalWordsBody                                 WORDS_HEREDOC_TERMINATOR SIGIL_MODIFIER* private literalRegex ::= TILDE LITERAL_SIGIL_NAME REGEX_PROMOTER literalRegexBody REGEX_TERMINATOR SIGIL_MODIFIER* private literalRegexBody ::= REGEX_FRAGMENT* private literalSigil ::= TILDE LITERAL_SIGIL_NAME SIGIL_PROMOTER literalSigilBody SIGIL_TERMINATOR SIGIL_MODIFIER* private literalSigilBody ::= SIGIL_FRAGMENT* private literalStringBody ::= STRING_FRAGMENT* private literalStringSigil ::= TILDE LITERAL_STRING_SIGIL_NAME STRING_SIGIL_PROMOTER literalStringBody STRING_SIGIL_TERMINATOR private literalWords ::=  TILDE LITERAL_SIGIL_NAME WORDS_PROMOTER literal WORDS_TERMINATOR SIGIL_MODIFIER* private literalWordsBody ::= WORDS_FRAGMENT* left multiplicationOperation ::= EOL* MULTIPLICATION_OPERATOR EOL* hatOperationList private multiplicationOperationList ::= hatOperationList multiplicationOperation* private quote ::= (charList | string) sigil ::= interpolatedCharListSigil |           interpolatedHeredocCharListSigil |           interpolatedHeredocRegex |           interpolatedHeredocSigil |           interpolatedHeredocStringSigil |           interpolatedHeredocWords |           interpolatedRegex |           interpolatedSigil |           interpolatedStringSigil |           literalCharListSigil |           literalHeredocRegex |           literalHeredocSigil |           literalHeredocStringSigil |           literalHeredocWords |           literalRegex |           literalSigil |           literalStringSigil |           literalWords string ::= STRING_PROMOTER            interpolatedStringBody            STRING_TERMINATOR stringHeredoc ::= STRING_HEREDOC_PROMOTER EOL                   interpolatedStringBody                   STRING_HEREDOC_TERMINATOR // right associative twoOperation ::= additionOperationList EOL* TWO_OPERATOR EOL* twoOperation | additionOperationList // list is just operation because operation is right associative and recursive.  List is only available to keep naming consistent private twoOperationList ::= twoOperation unaryOperation ::= (DUAL_OPERATOR | UNARY_OPERATOR) EOL* unaryOperation | value // list is just operation because operation is not associative private unaryOperationList ::= unaryOperation value ::= atom | CHAR_TOKEN | NUMBER | charListHeredoc | quote | sigil | stringHeredoc



When I try to parse

'a' ++ 'b'



I get `ERROR: Another not done marker added after this one. Must be done before this.`.  ''a'` should parse as `charList`. `++` should parse as `TWO_OPERATOR`.  `'b'` should parse as `charList` also, so I expect the overall file to be

elixirFile(
  twoOperation(
    value(
      quote(charList)
    ),
    value(
      quote(charList)
    )
)


What is the correct way to implement right-associative operators?  The last left-associative operator I implemented, addition (+/-) is working here https://github.com/KronicDeth/intellij-elixir/blob/a40e7adab62b7eaf54ee7ff63c6fb8bea97633f5/src/org/elixir_lang/Elixir.bnf.

2 comments
Comment actions Permalink

There's a very extensive use of left rules. This type of rule expects and then wraps any public rule "on the same level & to the left", e.g. as in this sequence:   willBeWrapped myLeftRuleHere.
Left rule cannot be the first part of a public rule and but it is possible in a private rule though one should be very careful.

Here's the problem:

twoOperation ::= additionOperationList EOL* TWO_OPERATOR EOL* twoOperation | additionOperationList
private left inner additionOperationList ::= multiplicationOperationList additionOperation*


I highly recommend to read once again README.md and HOWTO.md.

0
Comment actions Permalink

I got the use of the `left` modifier from looking at the haxe plugin's usage.  I had started using that pattern because I couldn't get the recursive pattern where is operator just works on a top-level expression.  After posting, I figured out that operators on expressions pattern only works if I ensure all operator extend the expression rule.  I had been missing that because I thought all it would do was make the tree less deep and I can do it later, but it doesn't even work without the extend.  Here's the new working grammar (https://github.com/KronicDeth/intellij-elixir/blob/2da1602b40c4db9fb1b8ea6ce55f7d40f115c815/src/org/elixir_lang/Elixir.bnf):

{
  parserClass="org.elixir_lang.parser.ElixirParser"

  extends="com.intellij.extapi.psi.ASTWrapperPsiElement"
  extends("atom|(binary|unary)Operation|value")=expression
  extends("(addition|hat|multiplication|two)Operation")=binaryOperation

  psiClassPrefix="Elixir"
  psiImplClassSuffix="Impl"
  psiPackage="org.elixir_lang.psi"
  psiImplPackage="org.elixir_lang.psi.impl"

  elementTypeHolderClass="org.elixir_lang.psi.ElixirTypes"
  elementTypeClass="org.elixir_lang.psi.ElixirElementType"
  tokenTypeClass="org.elixir_lang.psi.ElixirTokenType"

  tokens = [
    COMMENT = "regexp:#[^\r\n]*(\n|\r|\r\n)?"
  ]
}

// expressionList is optional to handle code-less file that contains only EOL between blank lines and order comment
// lines
elixirFile ::= EOL* (expressionList EOL*)?

// In alphabetical order

/* Unlike other binary operation, additionOperations cannot begin with EOLs: if there are EOLs, then the +/-
   is interpreted as unaryOperation */
additionOperation ::= expression DUAL_OPERATOR EOL* expression
atom ::= COLON (ATOM_FRAGMENT | quote)
fake binaryOperation ::= expression + {
  methods = [
    left = "/expr[0]"  // will be @NotNull as far as we have "+" in the expression
    right = "/expr[1]" // "expr" is the name of the auto-calculated child property (singular or list)
  ]
}
charList ::= CHAR_LIST_PROMOTER
             interpolatedCharListBody
             CHAR_LIST_TERMINATOR
charListHeredoc ::= CHAR_LIST_HEREDOC_PROMOTER EOL
                    interpolatedCharListBody
                    CHAR_LIST_HEREDOC_TERMINATOR
/* order of choices is lower precedence first as lower precedence operation are meant to enclose higher precedence
   operators.
   @see https://github.com/elixir-lang/elixir/blob/de39bbaca277002797e52ffbde617ace06233a2b/lib/elixir/src/elixir_parser.yrl#L44-L71 */
expression ::= twoOperation |
               additionOperation |
               multiplicationOperation |
               hatOperation |
               unaryOperation |
               value
private expressionList ::= expression (EOL+ expression)*
hatOperation ::= expression EOL* HAT_OPERATOR EOL* expression
private interpolatedCharListSigil ::= TILDE INTERPOLATING_CHAR_LIST_SIGIL_NAME CHAR_LIST_SIGIL_PROMOTER interpolatedCharListBody CHAR_LIST_SIGIL_TERMINATOR
private interpolatedCharListBody ::= (interpolation | CHAR_LIST_FRAGMENT | VALID_ESCAPE_SEQUENCE)*
private interpolatedHeredocCharListSigil ::= TILDE INTERPOLATING_CHAR_LIST_SIGIL_NAME CHAR_LIST_SIGIL_HEREDOC_PROMOTER EOL
                                             interpolatedCharListBody
                                             CHAR_LIST_SIGIL_HEREDOC_TERMINATOR
private interpolatedHeredocRegex ::= TILDE INTERPOLATING_REGEX_SIGIL_NAME REGEX_HEREDOC_PROMOTER EOL
                                     interpolatedRegexBody
                                     REGEX_HEREDOC_TERMINATOR SIGIL_MODIFIER*
private interpolatedHeredocSigil ::= TILDE INTERPOLATING_SIGIL_NAME SIGIL_HEREDOC_PROMOTER EOL
                                     interpolatedSigilBody
                                     SIGIL_HEREDOC_PROMOTER SIGIL_MODIFIER*
private interpolatedHeredocStringSigil ::= TILDE INTERPOLATING_STRING_SIGIL_NAME STRING_SIGIL_HEREDOC_PROMOTER EOL
                                           interpolatedStringBody
                                           STRING_SIGIL_HEREDOC_TERMINATOR
private interpolatedHeredocWords ::= TILDE INTERPOLATING_WORDS_SIGIL_NAME WORDS_HEREDOC_PROMOTER EOL
                                     interpolatedWordsBody
                                     WORDS_HEREDOC_TERMINATOR SIGIL_MODIFIER*
private interpolatedRegex ::= TILDE INTERPOLATING_REGEX_SIGIL_NAME REGEX_PROMOTER interpolatedRegexBody REGEX_TERMINATOR SIGIL_MODIFIER*
private interpolatedRegexBody ::= (interpolation | REGEX_FRAGMENT | VALID_ESCAPE_SEQUENCE)*
private interpolatedSigil ::= TILDE INTERPOLATING_SIGIL_NAME SIGIL_PROMOTER interpolatedSigilBody SIGIL_TERMINATOR SIGIL_MODIFIER*
private interpolatedSigilBody ::= (interpolation | SIGIL_FRAGMENT | VALID_ESCAPE_SEQUENCE)*
private interpolatedStringSigil ::= TILDE INTERPOLATING_STRING_SIGIL_NAME STRING_SIGIL_PROMOTER interpolatedStringBody STRING_SIGIL_TERMINATOR
private interpolatedStringBody ::=  (interpolation | STRING_FRAGMENT | VALID_ESCAPE_SEQUENCE)*
private interpolatedWordsBody ::= (interpolation | WORDS_FRAGMENT | VALID_ESCAPE_SEQUENCE)*
interpolation ::= INTERPOLATION_START expressionList? INTERPOLATION_END
private literalCharListBody ::= CHAR_LIST_FRAGMENT*
private literalCharListSigil ::= TILDE LITERAL_CHAR_LIST_SIGIL_NAME CHAR_LIST_SIGIL_PROMOTER literalCharListBody CHAR_LIST_SIGIL_TERMINATOR
private literalHeredocRegex ::= TILDE LITERAL_REGEX_SIGIL_NAME REGEX_HEREDOC_PROMOTER EOL
                                literalRegexBody
                                REGEX_HEREDOC_TERMINATOR SIGIL_MODIFIER*
private literalHeredocSigil ::= TILDE LITERAL_SIGIL_NAME SIGIL_HEREDOC_PROMOTER EOL
                                literalSigilBody
                                SIGIL_HEREDOC_TERMINATOR SIGIL_MODIFIER*
private literalHeredocStringSigil ::= TILDE LITERAL_STRING_SIGIL_NAME STRING_SIGIL_HEREDOC_PROMOTER EOL
                                      literalStringBody
                                      STRING_SIGIL_HEREDOC_TERMINATOR
private literalHeredocWords ::= TILDE LITERAL_WORDS_SIGIL_NAME WORDS_HEREDOC_PROMOTER EOL
                                literalWordsBody
                                WORDS_HEREDOC_TERMINATOR SIGIL_MODIFIER*
private literalRegex ::= TILDE LITERAL_SIGIL_NAME REGEX_PROMOTER literalRegexBody REGEX_TERMINATOR SIGIL_MODIFIER*
private literalRegexBody ::= REGEX_FRAGMENT*
private literalSigil ::= TILDE LITERAL_SIGIL_NAME SIGIL_PROMOTER literalSigilBody SIGIL_TERMINATOR SIGIL_MODIFIER*
private literalSigilBody ::= SIGIL_FRAGMENT*
private literalStringBody ::= STRING_FRAGMENT*
private literalStringSigil ::= TILDE LITERAL_STRING_SIGIL_NAME STRING_SIGIL_PROMOTER literalStringBody STRING_SIGIL_TERMINATOR
private literalWords ::=  TILDE LITERAL_SIGIL_NAME WORDS_PROMOTER literal WORDS_TERMINATOR SIGIL_MODIFIER*
private literalWordsBody ::= WORDS_FRAGMENT*
multiplicationOperation ::= expression EOL* MULTIPLICATION_OPERATOR EOL* expression
private quote ::= (charList | string)
sigil ::= interpolatedCharListSigil |
          interpolatedHeredocCharListSigil |
          interpolatedHeredocRegex |
          interpolatedHeredocSigil |
          interpolatedHeredocStringSigil |
          interpolatedHeredocWords |
          interpolatedRegex |
          interpolatedSigil |
          interpolatedStringSigil |
          literalCharListSigil |
          literalHeredocRegex |
          literalHeredocSigil |
          literalHeredocStringSigil |
          literalHeredocWords |
          literalRegex |
          literalSigil |
          literalStringSigil |
          literalWords
string ::= STRING_PROMOTER
           interpolatedStringBody
           STRING_TERMINATOR
stringHeredoc ::= STRING_HEREDOC_PROMOTER EOL
                  interpolatedStringBody
                  STRING_HEREDOC_TERMINATOR
twoOperation ::= expression EOL* TWO_OPERATOR EOL* expression { rightAssociative = true }
unaryOperation ::= (DUAL_OPERATOR | UNARY_OPERATOR) EOL* expression
value ::= atom | CHAR_TOKEN | NUMBER | charListHeredoc | quote | sigil | stringHeredoc



If I left out

  extends("atom|(binary|unary)Operation|value")=expression
  extends("(addition|hat|multiplication|two)Operation")=binaryOperation


Then the parse took a really long time and the parse had a real deep stack (which was only able to see because of the Pause button in the debugger).  (I really like the Pause feature.  Much kudos to whoever added that to IntelliJ and Rubymine.)  From the documentation I had thought `extends` just influences the class hierarchy, but it was actually significant to how fast the parse happens and whether it's realistically going to complete.

0

Please sign in to leave a comment.