Translate left recursion in yecc (yacc) to left-recursion for Grammar Kit
Elixir's grammar (https://github.com/elixir-lang/elixir/blob/de39bbaca277002797e52ffbde617ace06233a2b/lib/elixir/src/elixir_parser.yrl#L387-L388) is written in yecc, which is an Erlang port of YACC. I haven't had any problems when using binary, prefix, or atom as long as I used `extends` correctly in my Grammar Kit grammar, but I can't figure out how to get this line of constructs to translate:
matched_expr -> no_parens_one_expr # Line 121
no_parens_one_expr -> dot_identifier # Line 194
dot_identifier -> identifier # 384
dot_identifier -> matched_expr dot_op identifier # 385
As you can see, dot_identifier refers back to matched_expr, but is not a direct child. My current grammar maps matched_expr to matchedExpression, no_parens_one_expr to noParenthesesOneExpression, and dotIdentifier to dot_identifier. I can't get line #385 to work, so dotIdentifier only implements line #384. If uncomment the beginning of dotIdentifier I get left-recursion warnings for all the binary matchedExpression*Operations
{ parserClass="org.elixir_lang.parser.ElixirParser" extends="com.intellij.extapi.psi.ASTWrapperPsiElement" /* * Ordered by rule being extended (extends(regex)=<rule-begin-extended) */ extends("emptyParentheses|matchedExpression")=expression extends("charList(Heredoc)?|maxExpression|number.*Operation|list|sigil|string(Heredoc)?")=accessExpression extends("accessExpression|dotIdentifier|matchedExpression.*|noParenthesesOneExpression")=matchedExpression extends("atom|dotAlias")=maxExpression 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 = [ CLOSING_BRACKET = "]" // TODO remove once CLOSING_PARENTHESIS is used in emptyParentheses rule CLOSING_PARENTHESIS = ")" COMMA = "," COMMENT = "regexp:#[^\r\n]*(\n|\r|\r\n)?" DOT_OPERATOR = "." IN_OPERATOR = "in" OPENING_BRACKET = "[" // TODO remove once OPENING_PARENTHESIS is used in emptyParentheses rule OPENING_PARENTHESIS = "(" // TOO remove once SEMICOLON is used in endOfExpression rule SEMICOLON = ";" // TODO remove once containers are available for `{}` after alias for empty structs STRUCT_OPERATOR = "%" ] } // expressionList is optional to handle code-less file that contains only EOL between blank lines and order comment // lines elixirFile ::= endOfExpression* (expressionList endOfExpression*)? /* * In alphabetical order */ accessExpression ::= numberCaptureOperation | numberUnaryOperation | numberAtOperation | OPENING_PARENTHESIS EOL* SEMICOLON EOL* CLOSING_PARENTHESIS | /* elixir_tokenizer.erl converts CHAR_TOKENs to their number representation, so `number` in elixir_parser.yrl matches Elixir.flex's NUMBER and CHAR_TOKEN. */ CHAR_TOKEN | NUMBER | list | binaryString | listString | sigil | maxExpression atom ::= COLON (ATOM_FRAGMENT | quote) private binaryString ::= string | stringHeredoc charList ::= CHAR_LIST_PROMOTER interpolatedCharListBody CHAR_LIST_TERMINATOR charListHeredoc ::= CHAR_LIST_HEREDOC_PROMOTER EOL interpolatedCharListBody CHAR_LIST_HEREDOC_TERMINATOR private containerExpression ::= emptyParentheses // TODO fix left-recursion dotAlias ::= /*(matchedExpression EOL* DOT_OPERATOR EOL*)?*/ ALIAS // TODO fix left-recursion dotIdentifier ::= matchedExpression EOL* DOT_OPERATOR EOL* IDENTIFIER emptyParentheses ::= OPENING_PARENTHESIS EOL* CLOSING_PARENTHESIS // Must have at least one EOL or SEMICOLON, but at most one SEMICOLON endOfExpression ::= EOL* SEMICOLON EOL* | EOL expression ::= emptyParentheses | matchedExpression private expressionList ::= expression (endOfExpression+ 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 keywordKey ::= ALIAS | AND_OPERATOR | ARROW_OPERATOR | ASSOCIATION_OPERATOR | AT_OPERATOR | BIT_STRING_OPERATOR | CAPTURE_OPERATOR | COMPARISON_OPERATOR | DUAL_OPERATOR | HAT_OPERATOR | IDENTIFIER | IN_MATCH_OPERATOR | IN_OPERATOR | MAP_OPERATOR | MATCH_OPERATOR | MULTIPLICATION_OPERATOR | OR_OPERATOR | PIPE_OPERATOR | RELATIONAL_OPERATOR | STAB_OPERATOR | STRUCT_OPERATOR | TUPLE_OPERATOR | TWO_OPERATOR | UNARY_OPERATOR | WHEN_OPERATOR | quote keywordPair ::= keywordKey KEYWORD_PAIR_COLON EOL* keywordValue keywordValue ::= containerExpression list ::= OPENING_BRACKET EOL* (keywordPair (COMMA EOL* keywordPair)* COMMA?)? CLOSING_BRACKET private listString ::= charList | charListHeredoc 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* /* 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 */ matchedExpression ::= matchedExpressionCaptureOperation | matchedExpressionInMatchOperation | matchedExpressionWhenOperation | matchedExpressionTypeOperation | matchedExpressionPipeOperation | matchedExpressionMatchOperation | matchedExpressionOrOperation | matchedExpressionAndOperation | matchedExpressionComparisonOperation | matchedExpressionRelationalOperation | matchedExpressionArrowOperation | matchedExpressionInOperation | matchedExpressionTwoOperation | matchedExpressionAdditionOperation | matchedExpressionMultiplicationOperation | matchedExpressionHatOperation | matchedExpressionUnaryOperation | matchedExpressionAtOperation | dotIdentifier accessExpression /* Unlike other binary operation, additionOperations cannot begin with EOLs: if there are EOLs, then the +/- is interpreted as unaryOperation */ matchedExpressionAdditionOperation ::= matchedExpression DUAL_OPERATOR EOL* matchedExpression matchedExpressionAndOperation ::= matchedExpression EOL* AND_OPERATOR EOL* matchedExpression matchedExpressionArrowOperation ::= matchedExpression EOL* ARROW_OPERATOR EOL* matchedExpression matchedExpressionAtOperation ::= AT_OPERATOR EOL* matchedExpression matchedExpressionCaptureOperation ::= CAPTURE_OPERATOR EOL* matchedExpression matchedExpressionComparisonOperation ::= matchedExpression EOL* COMPARISON_OPERATOR EOL* matchedExpression matchedExpressionHatOperation ::= matchedExpression EOL* HAT_OPERATOR EOL* matchedExpression matchedExpressionInOperation ::= matchedExpression EOL* IN_OPERATOR EOL* matchedExpression matchedExpressionInMatchOperation ::= matchedExpression EOL* IN_MATCH_OPERATOR EOL* matchedExpression matchedExpressionMatchOperation ::= matchedExpression EOL* MATCH_OPERATOR EOL* matchedExpression { rightAssociative = true } matchedExpressionMultiplicationOperation ::= matchedExpression EOL* MULTIPLICATION_OPERATOR EOL* matchedExpression matchedExpressionOrOperation ::= matchedExpression EOL* OR_OPERATOR EOL* matchedExpression matchedExpressionPipeOperation ::= matchedExpression EOL* PIPE_OPERATOR EOL* matchedExpression { rightAssociative = true } matchedExpressionRelationalOperation ::= matchedExpression EOL* RELATIONAL_OPERATOR EOL* matchedExpression matchedExpressionTwoOperation ::= matchedExpression EOL* TWO_OPERATOR EOL* matchedExpression { rightAssociative = true } matchedExpressionTypeOperation ::= matchedExpression EOL* TYPE_OPERATOR EOL* matchedExpression { rightAssociative = true } matchedExpressionUnaryOperation ::= (DUAL_OPERATOR | UNARY_OPERATOR) EOL* matchedExpression matchedExpressionWhenOperation ::= matchedExpression EOL* WHEN_OPERATOR EOL* matchedExpression { rightAssociative = true } maxExpression ::= atom | dotAlias //noParenthesesOneExpression ::= dotIdentifier /* * Number Operations - Used in accessExpression */ numberAtOperation ::= AT_OPERATOR EOL* NUMBER numberCaptureOperation ::= CAPTURE_OPERATOR EOL* NUMBER numberUnaryOperation ::= (DUAL_OPERATOR | UNARY_OPERATOR) EOL* NUMBER 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
Please sign in to leave a comment.