ElixirConf 2015

The Road to IntelliJ Elixir 1.0.0

2015-10-02 to 2015-10-03

Luke Imhoff

	Kronic.Deth@gmail.com
	@KronicDeth
	@KronicDeth

This Presentation

Slides

Viewable: https://kronicdeth.github.io/the-road-to-intellij-elixir-1.0.0
Source: https://github.com/KronicDeth/the-road-to-intellij-elixir-1.0.0/tree/gh-pages

Project Source

https://github.com/KronicDeth/intellij-elixir/tree/v1.0.0

Outline

Introduction
BNF
Syntax
Interpolation
Matched Expressions
No Parentheses Function Calls
JInterface
Significant Whitespace
Stab
Unmatched Expressions
Parsing elixir-lang/elixir

Introduction

Why an IntelliJ Plugin?
Timeline

Why an IntelliJ Plugin?

I use Rubymine for Ruby development
Wanted vim key bindings
Wanted Cmd+Click Go To Definition for Elixir
Wanted Search Everywhere for Elixir
There was a tutorial

People may wonder why I took it upon myself to make an IDE plugin for Elixir, when I could have used a vim or emacs plugin.

I've used both emacs and vim. I started with emacs when I worked at Cray, only switching to vim when I needed something that worked over a high-latency, low-bandwidth CDMA modem on the high-way.

I started using Rubymine when my boss at a previous job, Nicholas Cancelliere, introduced me to it. I was shocked that an IDE for a dynamic language like Ruby could support Find Usage, Go To Definition, and Refactor. I had been use to using ctags for vim.

I haven't complete abandoned using vim either. I still use syntax highlighting plugins for vim in iTerm when I need to edit configuration files and I use the IDEAVim plugin for Jetbrains IDEs like Rubymine, Webstorm, and IntelliJ.

Without Rubymine I don't think I'd have been able to as quickly dive through the complex code-base in Metasploit and the graphical debugger allowed me to teach myself the internals of Rails and other DSLs.

I understood that many of the features I liked about Rubymine were shared across JetBrains' various IDEs, so if I could write the parts of a plugin to get JetBrains APIs to understand Elixir syntax and semantics, the features I really wanted would just work without me having to understand how to write the parts that were cross-language.

However, just getting syntax lexing and parsing right ended up taking a year...

Timeline

Date	Days		Commits		Version
Date	Delta	Total	Delta	Total	Commits/Day	Name
2014-07-27	0	0	1	1	1.00	Initial
2014‑08‑02	6	6	18	19	3.00	0.0.1
2014‑08‑03	1	7	14	33	14.00	0.0.2
2014‑08‑08	5	12	10	43	2.00	0.0.3
2014‑09‑13	36	48	64	107	1.78	0.1.0
2014‑09‑20	7	55	4	111	0.57	0.1.1
2014‑09‑25	5	60	12	123	2.50	0.1.2
2014‑10‑14	19	79	23	146	1.21	0.1.3
2014‑11‑30	47	126	226	373	4.81	0.2.0
2015‑04‑03	124	250	521	894	4.20	0.2.1
2015‑04‑10	7	257	27	921	3.86	0.3.0
2015‑04‑27	17	274	66	987	3.88	0.3.1
2015‑05‑01	4	278	8	995	2.00	0.3.2
2015‑05‑15	14	292	34	1029	2.43	0.3.3
2015‑06‑04	20	312	86	1115	4.30	0.3.4
2015‑07‑08	34	346	83	1198	2.44	0.3.5
2015‑07‑27	19	365	158	1356	2.44	1.0.0

BNF

Backus Naur Form
YECC
Grammar Kit
v0.0.1

Backus-Naur Form

Read as	Symbol
Metasyntactic Variable	`<variable>`
is defined as	`::=`
or	`\|`


<expr> ::= <integer> | <expr> <op> <integer>

YECC

lib/elixir/src/elixir_parser.yrl


grammar -> eoe : nil.
grammar -> expr_list : to_block('$1').
grammar -> eoe expr_list : to_block('$2').
grammar -> expr_list eoe : to_block('$1').
grammar -> eoe expr_list eoe : to_block('$2').
grammar -> '$empty' : nil.

YECC is a parser generator written in Erlang (and part of the standard distribution) that is based on yacc (with an 'a' instead of an 'e'), which is a parser generator written in C.

The YECC syntax differs from B-N-F in that it uses a skinny arrow (->) instead of colon colon equals (::=) and instead of using pipe (|) for OR, lines with the same rule name are repeated with alternative definitions. Finally, YECC supports running Erlang code on the tokens using dollar number ($n) for positional references to the matches tokens.

dollar empty ($empty) is a special token that matches no input. In formal grammars this is usually referred to as (lowercase) epsilon (ɛ).

Grammar Kit

src/org/elixir_lang/Elixir.bnf


private elixirFile ::= endOfExpression? (expressionList endOfExpression?)?
private expressionList ::= expression (endOfExpression expression | adjacentExpression)*

Grammar Kit is a parser generator written in Java and created by JetBrains.

GrammarKit's B-N-F format does use colon colon equals (::=) like Backus-Naur Form, but it has some more power constructs above pipe (|) for OR.

Question mark (?) can be used for 0 or 1, parentheses (()) can be used for grouping; and star can be used for 0 or more. Empty can be implied by question mark (?) or star (*) matching nothing or there being nothing on the right-hand-side of the colon colon equals (::=).

You'll also notice that there is no inline Java code after the rule definition unlike in YECC where there as Erlang code. This is because GrammarKit automatically generates an AST, which it calls a PSI (or Program Structure Interface) Tree from the matched rules, so there's no need to define how to build the tree.

Having GrammarKit generate the AST is both good and bad. It's good because it removes a lot of redundant code, but it's bad because rules must evaluate in the correct order to reflect the desired nesting and associativity without any manual fixups, which are possible with the Erlang code in YECC.

v0.0.1

Date	Days		Commits		Version
Date	Delta	Total	Delta	Total	Commits/Day
2014‑08‑02	6	6	18	19	3.00

Translate from YECC to Grammar Kit
Freeze IDE

YECC and Grammar Kit both support a form of BNF and Grammar Kit seems like it would support even a more compact grammar because question mark (?), star (star), pipe (|) and parentheses (()) could eliminate some of the redundancy needed in the multi-clause rules in YECC.

After only 6 days I had quote unquote translated the BNF from yecc to Grammar Kit and ended up with a parser that froze the IDE, which Julius "h4cc" Beckmann reported. That left the slow process of translating the grammar correctly over the next 359 days. At the time of the freeze, I didn't even really understand translating the BNF didn't work, all I knew was I needed to go slower and build the grammar up from simpler, testable pieces.

Syntax

Syntactic Analysis
Lexing/Tokenizing
Ignoring Characters

Syntactic Analysis

Step	Elixir	IntelliJ Elixir
Lexing	Erlang	JFlex
Parsing	YECC	GrammarKit

So, I went back and actually started to do the JetBrains tutorial step by step instead of jumping ahead and searched Wikipedia, trying to find CompSci articles that explained the correct way to do this.

In order to support color syntax highlighting and mark syntax errors with the nice red squiggly under line, IntelliJ Elixir needed to be able to analyze Elixir syntax.

Syntactic analysis is usually broken down into two parts: the first breaks the raw text into tokens and the second checks if those tokens are arranged in the correct order.

In most programming languages, both lexers and parsers are built using generators that have an external DSL. In Elixir, the lexer is built using Erlang directly because Erlang pattern matching is compact enough that a generator is unnecessary. Additionally, Elixir syntax contains some features that normal lexer generator aren't expecting.

For IntelliJ Elixir, I used JFlex because it was the lexer generator recommended by JetBrain's plugin tutorial.

For parsing Elixir does use a generator, called yecc, which generates Erlang code.

For IntelliJ Elixir, I used JetBrains' GrammarKit.

When I first started IntelliJ Elixir I didn't understand the important difference between these two stacks, but I hope to explain what I learned along the way to you.

Lexing/Tokenizing

Match Input
Emit Token

Ignoring Characters

Token Erlang JFlex

Comments

Token	Erlang	JFlex
Comments	`tokenize([$#\|String], Line, Scope, Tokens) -> Rest = tokenize_comment(String), tokenize(Rest, Line, Scope, Tokens); tokenize_comment("\r\n" ++ _ = Rest) -> Rest; tokenize_comment("\n" ++ _ = Rest) -> Rest; tokenize_comment([_\|Rest]) -> tokenize_comment(Rest); tokenize_comment([]) -> [].`	`COMMENT = "#" [^\r\n]* {EOL}? <YYINITIAL> { {COMMENT} { yybegin(BODY); return ElixirTypes.COMMENT; } } <BODY> { {COMMENT} { return ElixirTypes.COMMENT; } }`
EOL	`tokenize("\n" ++ Rest, Line, Scope, Tokens) -> tokenize(Rest, Line + 1, Scope, eol(Line, newline, Tokens)); tokenize("\r\n" ++ Rest, Line, Scope, Tokens) -> tokenize(Rest, Line + 1, Scope, eol(Line, newline, Tokens)); eol(_Line, _Mod, [{',',_}\|_] = Tokens) -> Tokens; eol(_Line, _Mod, [{eol,_,_}\|_] = Tokens) -> Tokens; eol(Line, Mod, Tokens) -> [{eol,Line,Mod}\|Tokens].`	`EOL = \n\|\r\|\r\n <YYINITIAL> { ({EOL}\|{WHITE_SPACE})+ { yybegin(BODY); return TokenType.WHITE_SPACE; } } <BODY> { {EOL}({EOL}\|{WHITE_SPACE})* { return ElixirTypes.EOL; } }`
Whitespace	`tokenize([T\|Rest], Line, Scope, Tokens) when ?is_horizontal_space(T) -> tokenize(strip_horizontal_space(Rest), Line, Scope, Tokens); strip_horizontal_space([H\|T]) when ?is_horizontal_space(H) -> strip_horizontal_space(T); strip_horizontal_space(T) -> T.`	`<BODY> { {WHITE_SPACE}+ { return TokenType.WHITE_SPACE; } }`


tokenize([$#|String], Line, Scope, Tokens) ->
  Rest = tokenize_comment(String),
  tokenize(Rest, Line, Scope, Tokens);

tokenize_comment("\r\n" ++ _ = Rest) -> Rest;
tokenize_comment("\n" ++ _ = Rest)   -> Rest;
tokenize_comment([_|Rest])           -> tokenize_comment(Rest);
tokenize_comment([])                 -> [].


COMMENT = "#" [^\r\n]* {EOL}?

<YYINITIAL> {
  {COMMENT} { yybegin(BODY); return ElixirTypes.COMMENT; }
}
<BODY> {
  {COMMENT} { return ElixirTypes.COMMENT; }
}

EOL


tokenize("\n" ++ Rest, Line, Scope, Tokens) ->
  tokenize(Rest, Line + 1, Scope, eol(Line, newline, Tokens));

tokenize("\r\n" ++ Rest, Line, Scope, Tokens) ->
  tokenize(Rest, Line + 1, Scope, eol(Line, newline, Tokens));

eol(_Line, _Mod, [{',',_}|_] = Tokens)   -> Tokens;
eol(_Line, _Mod, [{eol,_,_}|_] = Tokens) -> Tokens;
eol(Line, Mod, Tokens) -> [{eol,Line,Mod}|Tokens].


EOL = \n|\r|\r\n

<YYINITIAL> {
  ({EOL}|{WHITE_SPACE})+      { yybegin(BODY);
                                return TokenType.WHITE_SPACE; }
}
<BODY> {
  {EOL}({EOL}|{WHITE_SPACE})* { return ElixirTypes.EOL; }
}

Whitespace


tokenize([T|Rest], Line, Scope, Tokens) when ?is_horizontal_space(T) ->
  tokenize(strip_horizontal_space(Rest), Line, Scope, Tokens);

strip_horizontal_space([H|T]) when ?is_horizontal_space(H) ->
  strip_horizontal_space(T);
strip_horizontal_space(T) ->
  T.


<BODY> {
  {WHITE_SPACE}+ { return TokenType.WHITE_SPACE; }
}

In addition to turning runs of characters into single tokens, the lexer can be used to filter out runs that don't affect the meaning of code, such as spaces, extra new lines and comments.

The Erlang lexer processes the raw text as a char list. Pattern matching on the head of the list and then recursively calling tokenize on the rest of the raw text. The Erlang lexer only keeps track of the effect of ignored characters on the current line number, which was the only metadata in Elixir v0.14.3.

In contrast, the JFlex lexer processes the raw text as unicode characters. Regular expressions and references to other named regular expressions (as seen in COMMENT using EOL) can be used to match text with the longest match in a given state. In the Erlang Lexer, the order matches the order of the clauses. The JFlex lexer emits a token for even ignored characters because in an editor, unlike a compiler, one cares about comments, whitespace and extra newlines.

Interpolation

Interpolation
Computational Hierarchy
Elixir Native
JFlex

Interpolation


iex> greeting = "Hello #{"W#{"or"}ld"}"
"Hello World"
iex> tuple = "A tuple #{inspect {"Containing an #{:interpolated} string"}}"
"A tuple {\"Containing an interpolated string\"}"

Starts with #{ and ends with }
Valid in Char Lists, Strings, and (interpolating) Sigils
Recursive

Adding support for interpolation was tricky. At first glance the #{ and } that surround interpolation should work just like curly braces in a language like C or Java, but the braces in C or Java can just be lexed and the parser can decide about whether they are matched. In languages like Ruby or Elixir that support interpolation, whether you're parsing fragments for the string, char list or sigils or if you're in normal code needs to be tracked as fragments will be syntax highlighted and parsed differently than normal code. Finally, code inside interpolation can itself have strings, char lists, or sigils that also contain interpolation, recursively.

This recursion means that a non-deterministic finite automaton as generated by JFlex can't parse Elixir!

Computational Heirarchy

Language Class	Computational Model	Example
Regular	Finite Automaton/State Machine	Multiples of 3 in binary
Context-Free	Pushdown Automaton	Balanced Parentheses
Decidable	(Always-halting) Turing machine	`aⁿbⁿcⁿ`
Semidecidable	Turing machine	Halting Problem

Finite Automatons can lex regular languages, which are languages that match formal regular expressions. Formal regular expression only allow pipe (|) for or, parentheses (()) for grouping, and asterisk (*) for Kleene star, which means zero or more. They also can have question mark (?) to mean zero or one, if they can't use a symbol for no input, which would be lowercase epsilon formally. Formal regular expressions are missing the extended regular expression features like back references that would allow recursion.

Context-free languages are a step above regular expressions and can be lexed by pushdown automatons, which have a stack for keeping track of state. A pushdown automaton can use the current state along with the current input to decide whether parentheses are matched by pushing opening parentheses onto a stack and popping on closing parentheses. If you try to pop when the stack is empty, then you have an unmatched closing parenthesis and if the string ends with a non-empty stack then you have an unmatched opening parenthesis.

When writing compilers and IDEs, designers have to care about the computational hierarchy because performance guarantees get fuzzy and get more complex until you hit semidecidable and Turing machines, which may just spin forever on bad input.

Elixir Native Interpolation

lib/elixir/src/elixir_tokenizer.erl


tokenize([$"|T], Line, Scope, Tokens) ->
  handle_strings(T, Line, $", Scope, Tokens);
tokenize([$'|T], Line, Scope, Tokens) ->
  handle_strings(T, Line, $', Scope, Tokens);

handle_strings(T, Line, H, Scope, Tokens) ->
  case elixir_interpolation:extract(Line, Scope, true, T, H) of
    {error, Reason} ->
      interpolation_error(Reason, [H|T], Tokens, " (for string starting at line ~B)", [Line]);
    {NewLine, Parts, [$:|Rest]} when ?is_space(hd(Rest)) ->
      Unescaped = unescape_tokens(Parts),
      Key = case Scope#elixir_tokenizer.existing_atoms_only of
        true  -> kw_identifier_safe;
        false -> kw_identifier_unsafe
      end,
      tokenize(Rest, NewLine, Scope, [{Key, Line, Unescaped}|Tokens]);
    {NewLine, Parts, Rest} ->
      Token = {string_type(H), Line, unescape_tokens(Parts)},
      tokenize(Rest, NewLine, Scope, [Token|Tokens])
  end.

lib/elixir/src/elixir_interpolation.erl


extract(Line, Scope, true, [$#, ${|Rest], Buffer, Output, Last) ->
  Output1 = build_string(Line, Buffer, Output),

  case elixir_tokenizer:tokenize(Rest, Line, Scope) of
    {error, {EndLine, _, "}"}, [$}|NewRest], Tokens} ->
      Output2 = build_interpol(Line, Tokens, Output1),
      extract(EndLine, Scope, true, NewRest, [], Output2, Last);
    {error, Reason, _, _} ->
      {error, Reason};
    {ok, _EndLine, _} ->
      {error, {string, Line, "missing interpolation terminator:}", []}}
  end;

JFlex Interpolation

src/org/elixir_lang/Elixr.flex


%{
  private java.util.Stack<Integer> lexicalStateStack = new java.util.Stack<Integer>();
%}

<YYINITIAL> {
  {DOUBLE_QUOTES}  { lexicalStateStack.push(BODY);
                     yybegin(DOUBLE_QUOTED_STRING);
                     return ElixirTypes.DOUBLE_QUOTES; }
}

<DOUBLE_QUOTED_STRING> {
  {INTERPOLATION_START} { lexicalStateStack.push(yystate());
                          yybegin(INTERPOLATION);
                          return ElixirTypes.INTERPOLATION_START; }
  {DOUBLE_QUOTES}       { int previousLexicalState = lexicalStateStack.pop();
                          yybegin(previousLexicalState);
                          return ElixirTypes.DOUBLE_QUOTES; }
}

<BODY, INTERPOLATION> {
  {DOUBLE_QUOTES} { lexicalStateStack.push(yystate());
                    yybegin(DOUBLE_QUOTED_STRING);
                    return ElixirTypes.DOUBLE_QUOTES; }
}

<INTERPOLATION> {
  {INTERPOLATION_END} { int previousLexicalState = lexicalStateStack.pop();
                        yybegin(previousLexicalState);
                        return ElixirTypes.INTERPOLATION_END; }
}

JFlex's flex DSL only supports creating finite automaton, so I added a manually managed stack in the Java code that I can run on each rule match.

If the lexer hits a non-escaped double quote, it enters the DOUBLE_QUOTED_STRING state, which treats the #{ of the interpolation start token special: it pushes the current state on top the stack and begins the INTERPOLATION state.

The INTERPOLATION and BODY states are the same except that INTERPOLATION needs to pop and restore the previous lexical state if the closing curly brace (}) for INTERPOLATION is hit.

Matched Expressions

Associativity
Grammars
YECC Associativity and Precedence
Grammar Kit Precedence
Grammar Kit Associativity
Pratt Parsing
- Trigger
- Head
- Tail

Associativity

Associativity	Left	Right
Code	`a or b \|\| c`	`a ++ b <> c`
Nesting	`\|\|` `or` `a` `b` `c`	`++` `a` `<>` `b` `c`
Effective Parentheses	`(a or b) \|\| c`	`a ++ (b <> c)`
Execution Pipeline	a \|> Kernel.or(b) \|> Kernel.\|\|(c)	a \|> Kernel.++(b \|> Kernel.<>(c))

Associativity is how to group repeated operations of the same precedence.

I'm using the or operators, the word or and double pipes (||) for the left-associative operator because they're easy to distinguish. Similarly, I'm using the two operators, double plus (++) and diamond (<>), for the right-associative operator. Remember, the operators in each example are of the same precedence, so it's just the associativity controlling the nesting.

For left-associative, the left-most operator becomes the root of the tree with the right operand executing first, so it looks like the operators are in the wrong order, but if you rearrange the nesting to pipeline order it makes sense.

For right-associative, reading the tree in order, it looks like it matches, the order of the code, but when you change it to pipeline order you can see the the second operation must actually complete at the same time as the first argument.

Grammars

	Look-ahead, Left-to-Right, Rightmost deriviation (LALR)	Parsing Expression Grammar
Inventor	Frank DeRemer	Bryan Ford
Invented	1969	2004
Terminal symbols	✓	✓
Nonterminal rules	✓	✓
Empty string	✓	✓
Sequence	✓	✓
Choice	Ambiguous	Ordered
Zero-or-more	❌	`*`
One-or-more	❌	`+`
Optional	❌	`?`
Positive Look-ahead	❌	`&`
Negative Look-ahead	❌	`!`
Derivation	Rightmost	Leftmost
Left-Recursion	Favored	Infinite Loop
Right-Recursion	Unfavored	Favored
Direction	Bottom-up	Top-down

YECC is a LALR, or look-ahead, left-to-right, rightmost derivation parser generator. Grammar Kit is a Parsing Expression Grammar parser generator.

Rightmost derivation means the parse tree is actually built up from the right-most end of the text, so opposite the way the text is read, which is somewhat counter-intuitive for human, but turns out to be really powerful and efficient.

Leftmost derivation means the parse tree is built in the same order as the text is read and is easier for humans to understand, but it's not as theoretically powerful.

Importantly, when rightmost derivation favors left-recursion, but left-recursion will cause an infinite loop in a leftmost derivation, so in basic Parsing Expression Grammar one would need to rewrite the rules to eliminate the left-recursion.

YECC associativity and precedence

lib/elixir/src/elixir_parser.yrl


%% Changes in ops and precedence should be reflected on lib/elixir/lib/macro.ex
%% Note though the operator => in practice has lower precedence than all others,
%% its entry in the table is only to support the %{user | foo => bar} syntax.
Left       5 do.
Right     10 stab_op_eol.     %% ->
Left      20 ','.
Nonassoc  30 capture_op_eol.  %% &
Left      40 in_match_op_eol. %% <-, \\ (allowed in matches along =)
Right     50 when_op_eol.     %% when
Right     60 type_op_eol.     %% ::
Right     70 pipe_op_eol.     %% |
Right     80 assoc_op_eol.    %% =>
Right     90 match_op_eol.    %% =
Left     130 or_op_eol.       %% ||, |||, or, xor
Left     140 and_op_eol.      %% &&, &&&, and
Left     150 comp_op_eol.     %% ==, !=, =~, ===, !==
Left     160 rel_op_eol.      %% <, >, <=, >=
Left     170 arrow_op_eol.    %% < (op), (op) > (e.g |>, <<<, >>>)
Left     180 in_op_eol.       %% in
Right    200 two_op_eol.      %% ++, --, .., <>
Left     210 add_op_eol.      %% + (op), - (op)
Left     220 mult_op_eol.     %% * (op), / (op)
Left     250 hat_op_eol.      %% ^ (op) (e.g ^^^)
Nonassoc 300 unary_op_eol.    %% +, -, !, ^, not, ~~~
Left     310 dot_call_op.
Left     310 dot_op.          %% .
Nonassoc 320 at_op_eol.       %% @
Nonassoc 330 dot_identifier.

Grammar Kit Precedence

src/org/elixir_lang/Elixir.bnf


matchedExpression ::= matchedExpressionCaptureOperation |
                      matchedExpressionInMatchOperation |
                      matchedExpressionWhenOperation |
                      matchedExpressionTypeOperation |
                      matchedExpressionPipeOperation |
                      matchedExpressionMatchOperation |
                      matchedExpressionOrOperation |
                      matchedExpressionAndOperation |
                      matchedExpressionComparisonOperation |
                      matchedExpressionRelationalOperation |
                      matchedExpressionArrowOperation |
                      matchedExpressionInOperation |
                      matchedExpressionTwoOperation |
                      matchedExpressionAdditionOperation |
                      matchedExpressionMultiplicationOperation |
                      matchedExpressionHatOperation |
                      matchedExpressionUnaryOperation |
                      matchedExpressionDotOperation |
                      matchedExpressionAtOperation |
                      identifierExpression |
                      accessExpression

Grammar Kit Associativity

src/org/elixir/Elixir.bnf


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
matchedExpressionDotOperation ::= matchedExpression EOL* DOT_OPERATOR EOL* matchedExpression
matchedExpressionHatOperation ::= matchedExpression EOL* HAT_OPERATOR EOL* matchedExpression
matchedExpressionInMatchOperation ::= matchedExpression EOL* IN_MATCH_OPERATOR EOL* matchedExpression
matchedExpressionInOperation ::= matchedExpression EOL* IN_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 }

The pattern for binary operations are matchedExpression on either side of the operator.

Left associativity is assumed by default, so right associativity is indicated with right associative equals true (rightAssociative = true) in the braces after the rule.

You may have noticed that these rules appear to be recursive: on the previous slide, matchedExpression was defined as the ordered choice of all the operations on this on this slide, but all the operations use matchedExpression as both the left and right operand, so why doesn't parser go into an infinite loop on the first binary rule, matched expression in match operation (matchedExpressionInMatchOperation)?

There is no loop because Grammar Kit has some extensions that allow it to detect this pattern of rules.

Pratt Parsing

Trigger

Pratt Parsing

Head

gen/org/elixir_lang/parser/ElixirParser.java


public class ElixirParser implements PsiParser {
  /* ********************************************************** */
  // Expression root: matchedExpression
  // Operator priority table:
  // 0: PREFIX(matchedExpressionCaptureOperation)
  // 1: BINARY(matchedExpressionInMatchOperation)
  // 2: BINARY(matchedExpressionWhenOperation)
  // 3: BINARY(matchedExpressionTypeOperation)
  // 4: BINARY(matchedExpressionPipeOperation)
  // 5: BINARY(matchedExpressionMatchOperation)
  // 6: BINARY(matchedExpressionOrOperation)
  // 7: BINARY(matchedExpressionAndOperation)
  // 8: BINARY(matchedExpressionComparisonOperation)
  // 9: BINARY(matchedExpressionRelationalOperation)
  // 10: BINARY(matchedExpressionArrowOperation)
  // 11: BINARY(matchedExpressionInOperation)
  // 12: BINARY(matchedExpressionTwoOperation)
  // 13: BINARY(matchedExpressionAdditionOperation)
  // 14: BINARY(matchedExpressionMultiplicationOperation)
  // 15: BINARY(matchedExpressionHatOperation)
  // 16: PREFIX(matchedExpressionUnaryOperation)
  // 17: BINARY(matchedExpressionDotOperation)
  // 18: PREFIX(matchedExpressionAtOperation)
  // 19: ATOM(identifierExpression)
  // 20: ATOM(accessExpression)
  public static boolean matchedExpression(PsiBuilder b, int l, int g) {
    if (!recursion_guard_(b, l, "matchedExpression")) return false;
    addVariant(b, "<matched expression>");
    boolean r, p;
    Marker m = enter_section_(b, l, _NONE_, "<matched expression>");
    r = matchedExpressionCaptureOperation(b, l + 1);
    if (!r) r = matchedExpressionUnaryOperation(b, l + 1);
    if (!r) r = matchedExpressionAtOperation(b, l + 1);
    if (!r) r = identifierExpression(b, l + 1);
    if (!r) r = accessExpression(b, l + 1);
    p = r;
    r = r && matchedExpression_0(b, l + 1, g);
    exit_section_(b, l, m, null, r, p, null);
    return r || p;
  }
}

Pratt parsing is an extension to recursive-descent parsers, which include parsing expression grammars, that allows for optimization for parsing operators by noticing patterns in how humans write binary operators to eliminate left-recursion.

The optimization involves noticing that eventually all operation rules get to rules that aren't left-recursive or that are tokens, so the parser generator itself can do the left-recursion elimination by looking for those non-left-recursive rules first, then try to consume an operator, then do it all over again, but keep track of the precedence of the operator.

Here, you can see that the prefix operations, matchedExpressionUnaryOperation and matchedexpressionAtOperation, can be checked for because they consume an operator token first and so aren't left-recursive.

Likewise, identifierExpression and accessExpression are atoms, so they don't include matchedExpression at all and so can be used to consume input immediately.

Once some input is consumed, matchedExpression goes into matched expression underscore 0 (matchedExpression_0). For user written rules the underscore number system is used for anonymous groups in parentheses, but here's it's meant to indicate that the parser is checking the tail of all the matchedExpression rules.

Pratt Parsing

Tail

gen/org/elixir_lang/parser/ElixirParser.java


public class ElixirParser implements PsiParser {
 public static boolean matchedExpression_0(PsiBuilder b, int l, int g) {
    if (!recursion_guard_(b, l, "matchedExpression_0")) return false;
    boolean r = true;
    while (true) {
      Marker m = enter_section_(b, l, _LEFT_, null);
      if (g < 1 && matchedExpressionInMatchOperation_0(b, l + 1)) {
        r = matchedExpression(b, l, 1);
        exit_section_(b, l, m, MATCHED_EXPRESSION_IN_MATCH_OPERATION, r, true, null);
      }
      else if (g < 2 && matchedExpressionWhenOperation_0(b, l + 1)) {
        r = matchedExpression(b, l, 1);
        exit_section_(b, l, m, MATCHED_EXPRESSION_WHEN_OPERATION, r, true, null);
      }
      else if (g < 3 && matchedExpressionTypeOperation_0(b, l + 1)) {
        r = matchedExpression(b, l, 2);
        exit_section_(b, l, m, MATCHED_EXPRESSION_TYPE_OPERATION, r, true, null);
      }
      else if (g < 4 && matchedExpressionPipeOperation_0(b, l + 1)) {
        r = matchedExpression(b, l, 3);
        exit_section_(b, l, m, MATCHED_EXPRESSION_PIPE_OPERATION, r, true, null);
      }
      else if (g < 5 && matchedExpressionMatchOperation_0(b, l + 1)) {
        r = matchedExpression(b, l, 4);
        exit_section_(b, l, m, MATCHED_EXPRESSION_MATCH_OPERATION, r, true, null);
      }
      else if (g < 6 && matchedExpressionOrOperation_0(b, l + 1)) {
        r = matchedExpression(b, l, 6);
        exit_section_(b, l, m, MATCHED_EXPRESSION_OR_OPERATION, r, true, null);
      }
      // ...
      else {
        exit_section_(b, l, m, null, false, false, null);
        break;
      }
    }
    return r;
  }								
}

The pattern used in matched expression (matchedExpression) and matced expression zero (matchedExpression_0) is based on Douglas Crockford's Top Down Operator Precedence implementation in Javascript.

g is the right-binding power of the currently matched operator. Only operators with a stronger binding power (because they are higher precedence) can be matched when recursing, but if no stronger rule is matched on the recursive call to matchedExpression, then the while loop allows for matching operators of equal right-binding power.

The left-associative, InMatch at the beginning and or at the end of the excerpt all follow the pattern of recursive call to matchedExpression with g one greater than the max for the current operator (For example: g less than 1 and recurse with 1; g less than 6 and recurse with 6.) This ensures that adjacent left operators at the same level are matched by the while loop, which are then properly left-nested by the underscore left underscore (_LEFT_) directive in the m marker at the top of while loop.

The underscore left underscore (_LEFT_) directive is similar how the pipelines are rearranged in Elixir.

For right-associative operators, like when, type, pipe, and match, the if clauses recursively calls matched expression (matchedExpression with g that can match the current operator, which means adjacent right-associative operators or any higher precedence operator is properly nested at a lower level. Since the parser is left-most derivation, any nesting occurs on the right-end, so nesting gets the proper right-associative behavior.

No Parentheses Function Calls

YECC
Conversion
Unqualified
Qualified
Arguments
No Parentheses Strict
Many Arguments
No Parentheses Expression
MatchedExpression vs KeywordKey
In Matched Expression
matchedCallOperation
Qualified matchedCallOperation

YECC

lib/elixir/src/elixir_parser.yrl


expr -> no_parens_expr : '$1'.

no_parens_expr -> dot_op_identifier call_args_no_parens_many_strict : build_identifier('$1', '$2').
no_parens_expr -> dot_identifier call_args_no_parens_many_strict : build_identifier('$1', '$2').

dot_identifier -> identifier : '$1'.
dot_identifier -> matched_expr dot_op identifier : build_dot('$2', '$1', '$3').

dot_op_identifier -> op_identifier : '$1'.
dot_op_identifier -> matched_expr dot_op op_identifier : build_dot('$2', '$1', '$3').

call_args_no_parens_comma_expr -> matched_expr ',' call_args_no_parens_expr : ['$3', '$1'].
call_args_no_parens_comma_expr -> call_args_no_parens_comma_expr ',' call_args_no_parens_expr : ['$3'|'$1'].

call_args_no_parens_many -> matched_expr ',' call_args_no_parens_kw : ['$1', '$3'].
call_args_no_parens_many -> call_args_no_parens_comma_expr : reverse('$1').
call_args_no_parens_many -> call_args_no_parens_comma_expr ',' call_args_no_parens_kw : reverse(['$3'|'$1']).

call_args_no_parens_many_strict -> call_args_no_parens_many : '$1'.
call_args_no_parens_many_strict -> empty_paren : throw_no_parens_strict('$1').
call_args_no_parens_many_strict -> open_paren call_args_no_parens_kw close_paren : throw_no_parens_strict('$1').
call_args_no_parens_many_strict -> open_paren call_args_no_parens_many close_paren : throw_no_parens_strict('$1').

Conversion

Original


no_parens_expr -> dot_identifier call_args_no_parens_many_strict

dot_identifier -> identifier
dot_identifier -> matched_expr dot_op identifier

Compact dot_identifier


no_parens_expr -> dot_identifier call_args_no_parens_many_strict

dot_identifier ::= (matched_expr dot_op)? identifier

Inline dot_identifer


no_parens_expr ::= (matched_expr dot_op)? identifier call_args_no_parens_many_strict

Unqualified

src/org/elixir_lang/Elixir.bnf


private expression ::= emptyParentheses |
                       unqualifiedNoParenthesesManyArgumentsCall |
                       matchedExpression

noParenthesesManyArgumentsUnqualifiedIdentifier ::= IDENTIFIER

unqualifiedNoParenthesesManyArgumentsCall ::= noParenthesesManyArgumentsUnqualifiedIdentifier
                                              noParenthesesManyArgumentsStrict

Qualified

src/org/elixir_lang/Elixir.bnf#


noParenthesesNoArgumentsUnqualifiedCallOrVariable ::= IDENTIFIER

matchedExpression ::= matchedCaptureNonNumericOperation |
                      // ...
                      matchedCallOperation |
                      noParenthesesNoArgumentsUnqualifiedCallOrVariable |
                      accessExpression

matchedCallOperation ::= matchedExpression noParenthesesManyArgumentsStrict

Arguments

lib/elixir/src/elixir_parser.yrl


call_args_no_parens_many_strict -> call_args_no_parens_many : '$1'.
call_args_no_parens_many_strict -> empty_paren : throw_no_parens_strict('$1').
call_args_no_parens_many_strict -> open_paren call_args_no_parens_kw close_paren : throw_no_parens_strict('$1').
call_args_no_parens_many_strict -> open_paren call_args_no_parens_many close_paren : throw_no_parens_strict('$1').

src/org/elixir_lang/Elixir.bnf


/* Special class for wrapping rules so that
   {@link: org.elixir_lang.inspection.NoParenthesesStrict} can just search for
   ElixirNoParenthesesStrict instead of having to differentiate between valid and invalid
   rule classes. */
noParenthesesStrict ::= emptyParentheses |
                        OPENING_PARENTHESIS (
                                             noParenthesesKeywords |
                                             noParenthesesManyArguments
                                            ) CLOSING_PARENTHESIS
                        { implements = "org.elixir_lang.psi.QuotableArguments" methods = [quoteArguments] }

private noParenthesesManyArgumentsStrict ::= noParenthesesManyArguments |
                                             noParenthesesStrict

No Parentheses Strict

Test Code


function (first_positional, second_positional, key: value)

Code.string_to_quoted


{:error,
 {1,
  "unexpected parenthesis. If you are making a function call, do not insert spaces in between the function name and the opening parentheses. Syntax error before: ",
  "'('"}}

The Elixir parser throws errors immediately, but this stops the user from being able to correct later errors. This can be a wise choice if anyone has ever seen the noise that a single error in C or C++ can make later in the file.

For an IDE however, it would be annoying if syntax and error highlighting stopped at the first error, so invalid syntax, such as ambiguous parentheses are allowed in IntelliJ Elixir's parser and only marked as errors using an Inspection, which does the red highlighting. Inspection in the JetBrains API allows the user to Quick Fix the error with Alt Enter (ALT+Enter) when the cursor is hovering over it.

Being able to correct errors is one of the reasons that an IDEs grammar can be more permissive than the compiler's grammar: permissiveness in parser allows for more robust heuristics to mark the errors later.

Many Arguments

lib/elixir/src/elixir_parser.yrl


call_args_no_parens_expr -> matched_expr : '$1'.
call_args_no_parens_expr -> empty_paren : nil.
call_args_no_parens_expr -> no_parens_expr : throw_no_parens_many_strict('$1').

call_args_no_parens_comma_expr -> matched_expr ',' call_args_no_parens_expr : ['$3', '$1'].
call_args_no_parens_comma_expr -> call_args_no_parens_comma_expr ',' call_args_no_parens_expr : ['$3'|'$1'].

call_args_no_parens_many -> matched_expr ',' call_args_no_parens_kw : ['$1', '$3'].
call_args_no_parens_many -> call_args_no_parens_comma_expr : reverse('$1').
call_args_no_parens_many -> call_args_no_parens_comma_expr ',' call_args_no_parens_kw : reverse(['$3'|'$1']).

src/org/elixir_lang/Elixir.bnf


private noParenthesesCommaExpression ::= matchedExpression (infixComma noParenthesesExpression)+
noParenthesesFirstPositional ::= matchedExpression
                                 { implements = "org.elixir_lang.psi.Quotable" methods = [quote] }
noParenthesesOnePositionalAndKeywordsArguments ::= noParenthesesFirstPositional infixComma noParenthesesKeywords
                                                   { implements = "org.elixir_lang.psi.QuotableArguments" methods = [quoteArguments] }
noParenthesesManyPositionalAndMaybeKeywordsArguments ::= noParenthesesCommaExpression (infixComma noParenthesesKeywords)?
                                                         { implements = "org.elixir_lang.psi.QuotableArguments" methods = [quoteArguments] }

No Parentheses Expression

lib/elixir/src/elixir_parser.yrl


call_args_no_parens_expr -> matched_expr : '$1'.
call_args_no_parens_expr -> empty_paren : nil.
call_args_no_parens_expr -> no_parens_expr : throw_no_parens_many_strict('$1').

src/org/elixir_lang/Elixir.bnf


/* Have to prevent matchedExpression that is actually a keywordKey from being parsed as just a matchedExpression or
   callArgumentsNoParenthesesCommaExpression COMMA EOL* callArgumentsNoParenthesesKeywords will never match. */
noParenthesesExpression ::= emptyParentheses |
                            /* Must be before matchedExpression because noParenthesesExpression is
                               `matchedExpressionDotIdentifier callArgumentsNoParenthesesManyStrict` which is longer
                               than `matchedExpressionDotIdentifier` in matchedExpression. */
                            /* This will be marked as an error by
                               {@link org.elixir_lang.inspection.NoParenthesesManyStrict} */
                            noParenthesesManyStrictNoParenthesesExpression |
                            matchedExpression !KEYWORD_PAIR_COLON
                            { implements = "org.elixir_lang.psi.Quotable" methods = [quote] }

MatchedExpression vs KeywordKey

matchedExpression
matchedExpression ::= accessExpression
accessionExpression ::= stringLine
quote ::= stringLine
keywordKey ::= quote
private keywordKeyColonEOL ::= keywordKey KEYWORD_PAIR_COLON EOL*
noParenthesesKeywordPair ::= keywordKeyColonEOL noParenthesesExpression
noParenthesesKeywords ::= noParenthesesKeywordPair (infixComma noParenthesesKeywordPair)*
noParenthesesOnePositionalAndKeywordsArguments ::= noParenthesesFirstPositional infixComma noParenthesesKeywords
noParenthesesManyPositionalAndMaybeKeywordsArguments ::= noParenthesesCommaExpression (infixComma noParenthesesKeywords)?

matchedExpression) contains accessExpression. [hit space] accessExpression contains stringLine [hit space], but a string (or char list) is contained in quoted [hit space], which is contained in (keywordKey) [hit space], which is contained in noParenthesesKeywordPair [hit space], which is contained in no parentheses keywords (noParenthesesKeywords) [hit space], which is the tail of no parentheses function calls. [hit space]

The native parser does not have this problem because it tokenizes quoted keyword key atoms as just keyword identifiers, which it can do since it can hold as much text as it wants in a buffer to represent a token instead of just the current match like JFlex.

In Matched Expression

lib/elixir/src/elixir_parser.yrl


matched_expr -> matched_expr no_parens_op_expr : build_op(element(1, '$2'), '$1', element(2, '$2')).
matched_expr -> unary_op_eol no_parens_expr : build_unary_op('$1', '$2').
matched_expr -> at_op_eol no_parens_expr : build_unary_op('$1', '$2').
matched_expr -> capture_op_eol no_parens_expr : build_unary_op('$1', '$2').

no_parens_op_expr -> match_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> add_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> mult_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> hat_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> two_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> and_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> or_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> in_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> in_match_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> type_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> pipe_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> comp_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> rel_op_eol no_parens_expr : {'$1', '$2'}.
no_parens_op_expr -> arrow_op_eol no_parens_expr : {'$1', '$2'}.

Matched Call Operation

src/org/elixir_lang/Elixir.bnf


matchedExpression ::= matchedCaptureNonNumericOperation |
                      matchedInMatchOperation |
                      matchedWhenNoParenthesesKeywordsOperation |
                      matchedWhenOperation |
                      matchedTypeOperation |
                      matchedPipeOperation |
                      matchedMatchOperation |
                      matchedOrOperation |
                      matchedAndOperation |
                      matchedComparisonOperation |
                      matchedRelationalOperation |
                      matchedArrowOperation |
                      matchedInOperation |
                      matchedTwoOperation |
                      matchedAdditionOperation |
                      matchedMultiplicationOperation |
                      matchedHatOperation |
                      matchedUnaryNonNumericOperation |
                      matchedDotOperation |
                      matchedAtNonNumericOperation |
                      matchedCallOperation |
                      noParenthesesNoArgumentsUnqualifiedCallOrVariable |
                      accessExpression

matchedCallOperation ::= matchedExpression noParenthesesManyArgumentsStrict

Qualified Matched Call Operation

Rule Subset


matchedExpression ::= matchedDotOperation |
                      matchedCallOperation |
                      noParenthesesNoArgumentsUnqualifiedCallOrVariable |
                      accessExpression
matchedDotOperation ::= matchedExpression dotInfixOperator matchedExpression
matchedCallOperation ::= matchedExpression noParenthesesManyArgumentsStrict
accessExpression ::= alias

Inline alias


matchedExpression ::= matchedDotOperation |
                      matchedCallOperation |
                      noParenthesesNoArgumentsUnqualifiedCallOrVariable
matchedDotOperation ::= alias dotInfixOperator matchedExpression
matchedCallOperation ::= matchedExpression noParenthesesManyArgumentsStrict

Inline matchedCallOperation


matchedExpression ::= matchedDotOperation |
                      matchedCallOperation |
                      noParenthesesNoArgumentsUnqualifiedCallOrVariable |
matchedDotOperation ::= alias dotInfixOperator matchedCallOperation
matchedCallOperation ::= matchedExpression noParenthesesManyArgumentsStrict

Expand matchedCallOperation


matchedExpression ::= matchedDotOperation |
                      noParenthesesNoArgumentsUnqualifiedCallOrVariable
matchedDotOperation ::= alias dotInfixOperator matchedExpression noParenthesesManyArgumentsStrict

Inline noParenthesesNoArgumentsUnqualifiedCallOrVariable


matchedDotOperation ::= alias dotInfixOperator noParenthesesNoArgumentsUnqualifiedCallOrVariable noParenthesesManyArgumentsStrict


                        Kernel .               inspect                                           0..1, structs: false

JInterface

Quoted vs PSI
Node
Mailbox
Message
Quoted
- Expected
- Pattern
  - YECC
  - IntelliJ Elixir
- Actual
- Block
- Comparison
Char List
Protocol

Quoted vs PSI

Code.string_to_quoted! psiToString

`1 + 2 = 3 + 4`
`Code.string_to_quoted!`	`psiToString`
`{:=, [line: 1], [{:+, [line: 1], [1, 2]}, {:+, [line: 1], [3, 4]}]}` `{ :=, [line: 1], [ { :+, [line: 1], [ 1, 2 ] }, { :+, [line: 1], [ 3, 4 ] } ] }`	Elixir File(0,13) ElixirMatchedMatchOperationImpl(MATCHED_MATCH_OPERATION)(0,13) ElixirMatchedAdditionOperationImpl(MATCHED_ADDITION_OPERATION)(0,5) ElixirAccessExpressionImpl(ACCESS_EXPRESSION)(0,1) ElixirDecimalWholeNumberImpl(DECIMAL_WHOLE_NUMBER)(0,1) ElixirDecimalDigitsImpl(DECIMAL_DIGITS)(0,1) PsiElement(VALID_DECIMAL_DIGITS)('1')(0,1) PsiWhiteSpace(' ')(1,2) ElixirAdditionInfixOperatorImpl(ADDITION_INFIX_OPERATOR)(2,3) PsiElement(DUAL_OPERATOR)('+')(2,3) PsiWhiteSpace(' ')(3,4) ElixirAccessExpressionImpl(ACCESS_EXPRESSION)(4,5) ElixirDecimalWholeNumberImpl(DECIMAL_WHOLE_NUMBER)(4,5) ElixirDecimalDigitsImpl(DECIMAL_DIGITS)(4,5) PsiElement(VALID_DECIMAL_DIGITS)('2')(4,5) PsiWhiteSpace(' ')(5,6) ElixirMatchInfixOperatorImpl(MATCH_INFIX_OPERATOR)(6,7) PsiElement(MATCH_OPERATOR)('=')(6,7) PsiWhiteSpace(' ')(7,8) ElixirMatchedAdditionOperationImpl(MATCHED_ADDITION_OPERATION)(8,13) ElixirAccessExpressionImpl(ACCESS_EXPRESSION)(8,9) ElixirDecimalWholeNumberImpl(DECIMAL_WHOLE_NUMBER)(8,9) ElixirDecimalDigitsImpl(DECIMAL_DIGITS)(8,9) PsiElement(VALID_DECIMAL_DIGITS)('3')(8,9) PsiWhiteSpace(' ')(9,10) ElixirAdditionInfixOperatorImpl(ADDITION_INFIX_OPERATOR)(10,11) PsiElement(DUAL_OPERATOR)('+')(10,11) PsiWhiteSpace(' ')(11,12) ElixirAccessExpressionImpl(ACCESS_EXPRESSION)(12,13) ElixirDecimalWholeNumberImpl(DECIMAL_WHOLE_NUMBER)(12,13) ElixirDecimalDigitsImpl(DECIMAL_DIGITS)(12,13) PsiElement(VALID_DECIMAL_DIGITS)('4')(12,13)


{:=, [line: 1], [{:+, [line: 1], [1, 2]}, {:+, [line: 1], [3, 4]}]}


{
 :=,
 [line: 1],
 [
  {
   :+,
   [line: 1],
   [
    1,
    2
   ]
  },
  {
   :+,
   [line: 1],
   [
    3,
    4
   ]
  }
 ]
}


Elixir File(0,13)
  ElixirMatchedMatchOperationImpl(MATCHED_MATCH_OPERATION)(0,13)
    ElixirMatchedAdditionOperationImpl(MATCHED_ADDITION_OPERATION)(0,5)
      ElixirAccessExpressionImpl(ACCESS_EXPRESSION)(0,1)
        ElixirDecimalWholeNumberImpl(DECIMAL_WHOLE_NUMBER)(0,1)
          ElixirDecimalDigitsImpl(DECIMAL_DIGITS)(0,1)
            PsiElement(VALID_DECIMAL_DIGITS)('1')(0,1)
      PsiWhiteSpace(' ')(1,2)
      ElixirAdditionInfixOperatorImpl(ADDITION_INFIX_OPERATOR)(2,3)
        PsiElement(DUAL_OPERATOR)('+')(2,3)
      PsiWhiteSpace(' ')(3,4)
      ElixirAccessExpressionImpl(ACCESS_EXPRESSION)(4,5)
        ElixirDecimalWholeNumberImpl(DECIMAL_WHOLE_NUMBER)(4,5)
          ElixirDecimalDigitsImpl(DECIMAL_DIGITS)(4,5)
            PsiElement(VALID_DECIMAL_DIGITS)('2')(4,5)
    PsiWhiteSpace(' ')(5,6)
    ElixirMatchInfixOperatorImpl(MATCH_INFIX_OPERATOR)(6,7)
      PsiElement(MATCH_OPERATOR)('=')(6,7)
    PsiWhiteSpace(' ')(7,8)
    ElixirMatchedAdditionOperationImpl(MATCHED_ADDITION_OPERATION)(8,13)
      ElixirAccessExpressionImpl(ACCESS_EXPRESSION)(8,9)
        ElixirDecimalWholeNumberImpl(DECIMAL_WHOLE_NUMBER)(8,9)
          ElixirDecimalDigitsImpl(DECIMAL_DIGITS)(8,9)
            PsiElement(VALID_DECIMAL_DIGITS)('3')(8,9)
      PsiWhiteSpace(' ')(9,10)
      ElixirAdditionInfixOperatorImpl(ADDITION_INFIX_OPERATOR)(10,11)
        PsiElement(DUAL_OPERATOR)('+')(10,11)
      PsiWhiteSpace(' ')(11,12)
      ElixirAccessExpressionImpl(ACCESS_EXPRESSION)(12,13)
        ElixirDecimalWholeNumberImpl(DECIMAL_WHOLE_NUMBER)(12,13)
          ElixirDecimalDigitsImpl(DECIMAL_DIGITS)(12,13)
            PsiElement(VALID_DECIMAL_DIGITS)('4')(12,13)

Node

src/org/elixir_lang/IntellijElixir.java


package org.elixir_lang;

import com.ericsson.otp.erlang.OtpNode;

import java.io.IOException;

public class IntellijElixir {
    private static OtpNode localNode = null;
    public static final String REMOTE_NODE = "intellij_elixir@127.0.0.1";

    public static OtpNode getLocalNode() throws IOException {
        if (localNode == null) {
            localNode = new OtpNode(
                "intellij-elixir@127.0.0.1",
                "intellij_elixir"
            );
        }

        return localNode;
    }
}

Mailbox

src/org/elixir_lang/intellij_elixir/Quoter.java


package org.elixir_lang.intellij_elixir;

public class Quoter {
    public static OtpErlangTuple quote(@NotNull String code) throws IOException,
                                                                    OtpErlangExit,
                                                                    OtpErlangDecodeException {
        final OtpNode otpNode = IntellijElixir.getLocalNode();
        final OtpMbox otpMbox = otpNode.createMbox();

        OtpErlangObject quoteMessage = Quoter.quoteMessage(code, otpMbox.self());
        otpMbox.send(REMOTE_NAME, IntellijElixir.REMOTE_NODE, quoteMessage);

        return (OtpErlangTuple) otpMbox.receive(TIMEOUT_IN_MILLISECONDS);
    }
}

Message

src/org/elixir_lang/intellij_elixir/Quoter.java


package org.elixir_lang.intellij_elixir;

public class Quoter {
    public static OtpErlangObject quoteMessage(final String text, final OtpErlangPid self) {
        final OtpErlangAtom[] messageKeys = new OtpErlangAtom[]{
                new OtpErlangAtom("quote"),
                new OtpErlangAtom("for")
        };
        final OtpErlangObject[] messageValues = new OtpErlangObject[]{
                elixirString(text),
                self
        };

        return new OtpErlangMap(messageKeys, messageValues);
    }
}

Quoted

Expected

lib/intellij_elixir/supervisor.ex


defmodule IntellijElixir.Supervisor do
  use Supervisor

  def start_link do
    Supervisor.start_link(__MODULE__, :ok)
  end

  @quoter_module IntellijElixir.Quoter

  def init(:ok) do
    children = [
      worker(@quoter_module, [[], [name: @quoter_module]])
    ]

    supervise(children, strategy: :one_for_one)
  end
end

lib/intellij_elixir/quoter.ex


defmodule IntellijElixir.Quoter do
  use GenServer

  def start_link(args, opts \\ []) do
    GenServer.start_link(__MODULE__, args, opts)
  end

  def handle_info(%{quote: code, for: pid}, state) do
    {status, quoted} = Code.string_to_quoted(code)
    send pid, {status, %{code: code, quoted: quoted}}

    {:noreply, state}
  end
end

Quoted

Pattern

lib/elixir/src/elixir_parser.yrl


matched_expr -> matched_expr matched_op_expr : build_op(element(1, '$2'), '$1', element(2, '$2')).
matched_expr -> matched_expr no_parens_op_expr : build_op(element(1, '$2'), '$1', element(2, '$2')).

matched_op_expr -> match_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> add_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> mult_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> hat_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> two_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> and_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> or_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> in_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> in_match_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> type_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> when_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> pipe_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> comp_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> rel_op_eol matched_expr : {'$1', '$2'}.
matched_op_expr -> arrow_op_eol matched_expr : {'$1', '$2'}.

Quoted

Pattern

src/org/elixir_lang/Elixir.bnf


matchedMatchOperation ::= matchedExpression matchInfixOperator matchedExpression
                          { implements = "org.elixir_lang.psi.InfixOperation" methods = [quote] rightAssociative = true }

matchedOrOperation ::= matchedExpression orInfixOperator matchedExpression
                       { implements = "org.elixir_lang.psi.InfixOperation" methods = [quote] }

src/org/elixir_lang/psi/impl/ElixirPsiImplUtil.java#


public class ElixirPsiImplUtil {
    @Contract(pure = true)
    @NotNull
    public static OtpErlangObject quote(@NotNull final InfixOperation infixOperation) {
        PsiElement[] children = infixOperation.getChildren();

        if (children.length != 3) {
            throw new NotImplementedException(
                "BinaryOperation expected to have 3 children (left operand, operator, right operand"
            );
        }

        Quotable leftOperand = (Quotable) children[0];
        OtpErlangObject quotedLeftOperand = leftOperand.quote();

        Quotable operator = (Quotable) children[1];
        OtpErlangObject quotedOperator = operator.quote();

        Quotable rightOperand = (Quotable) children[2];
        OtpErlangObject quotedRightOperand = rightOperand.quote();

        return quotedFunctionCall(
                quotedOperator,
                metadata(operator),
                quotedLeftOperand,
                quotedRightOperand
        );
    }
}

Quoted

Actual

src/org/elixir_lang/psi/impl/ElixirPsiImplUtil.java


package org.elixir_lang.psi.impl;

public class ElixirPsiImplUtil {
    public static OtpErlangObject quote(ElixirFile file) {
        final Deque<OtpErlangObject> quotedChildren = new LinkedList<OtpErlangObject>();

        file.acceptChildren(
                new PsiElementVisitor() {
                    @Override
                    public void visitElement(PsiElement element) {
                        if (element instanceof Quotable) {
                            visitQuotable((Quotable) element);
                        } else if (!isUnquoted(element)) {
                            throw new NotImplementedException("Don't know how to visit " + element);
                        }

                        super.visitElement(element);
                    }

                    public void visitQuotable(@NotNull Quotable child) {
                        final OtpErlangObject quotedChild = child.quote();
                        quotedChildren.add(quotedChild);
                    }
                }
        );

        return block(quotedChildren);
    }
}

Quoted

Block

Erlang Java

Erlang	Java
`lib/elixir/src/elixir_parser.yrl` `to_block([One]) -> One; to_block(Other) -> {'__block__', [], reverse(Other)}.`	`src/org/elixir_lang/psi/impl/ElixirPsiImplUtil.java` package org.elixir_lang.psi.impl; public class ElixirPsiImplUtil { @Contract(pure = true) @NotNull public static OtpErlangObject block(@NotNull final Deque<OtpErlangObject> quotedChildren) { OtpErlangObject asBlock; final int size = quotedChildren.size(); if (size == 0) { asBlock = NIL; } else if (size == 1) { asBlock = quotedChildren.getFirst(); } else { OtpErlangObject[] quotedArray = new OtpErlangObject[size]; OtpErlangList blockMetadata = new OtpErlangList(); asBlock = quotedFunctionCall( BLOCK, blockMetadata, quotedChildren.toArray(quotedArray) ); } return asBlock; } }

lib/elixir/src/elixir_parser.yrl


to_block([One]) -> One;
to_block(Other) -> {'__block__', [], reverse(Other)}.

src/org/elixir_lang/psi/impl/ElixirPsiImplUtil.java


package org.elixir_lang.psi.impl;

public class ElixirPsiImplUtil {
    @Contract(pure = true)
    @NotNull
    public static OtpErlangObject block(@NotNull final Deque<OtpErlangObject> quotedChildren) {
        OtpErlangObject asBlock;
        final int size = quotedChildren.size();

        if (size == 0) {
            asBlock = NIL;
        } else if (size == 1) {
            asBlock = quotedChildren.getFirst();
        } else {
            OtpErlangObject[] quotedArray = new OtpErlangObject[size];
            OtpErlangList blockMetadata = new OtpErlangList();

            asBlock = quotedFunctionCall(
                    BLOCK,
                    blockMetadata,
                    quotedChildren.toArray(quotedArray)
            );
        }

        return asBlock;
    }
}

Quoted

Comparison

src/org/elixir_lang/intellij_elixir/Quoter.java


package org.elixir_lang.intellij_elixir;

public class Quoter {
    public static void assertQuotedCorrectly(PsiFile file) {
        final String text = file.getText();

        try {
            OtpErlangTuple quotedMessage = Quoter.quote(text);
            Quoter.assertMessageReceived(quotedMessage);

            OtpErlangAtom status = (OtpErlangAtom) quotedMessage.elementAt(0);
            String statusString = status.atomValue();
            OtpErlangMap map = (OtpErlangMap) quotedMessage.elementAt(1);
            assertCodeEquals(text, map);
            OtpErlangObject expectedQuoted = quoted(map);

            if (statusString.equals("ok")) {
                OtpErlangObject actualQuoted = ElixirPsiImplUtil.quote(file);
                assertEquals(expectedQuoted, actualQuoted);
            } else if (statusString.equals("error")) {
                OtpErlangTuple error = (OtpErlangTuple) expectedQuoted;

                OtpErlangLong line = (OtpErlangLong) error.elementAt(0);

                OtpErlangBinary messageBinary = (OtpErlangBinary) error.elementAt(1);
                String message = javaString(messageBinary);

                OtpErlangBinary tokenBinary = (OtpErlangBinary) error.elementAt(2);
                String token = javaString(tokenBinary);

                throw new AssertionError(
                        "intellij_elixir returned \"" + message + "\" on line " + line + " due to " + token  +
                                ", use assertQuotesAroundError if error is expect in Elixir natively, " +
                                "but not in intellij-elixir plugin"
                );
            }
        }
        catch (IOException e) {
            throw new RuntimeException(e);
        } catch (OtpErlangDecodeException e) {
            throw new RuntimeException(e);
        } catch (OtpErlangExit e) {
            throw new RuntimeException(e);
        }
    }
}

Char List

Range		Java Class
Start	End	Java Class
0	255	`OtpErlangString`
256	N/A	`OtpErlangList`

Protocol

lib/jinterface/java_src/com/ericsson/otp/erlang/OtpInputStream.java


package com.ericsson.otp.erlang;

public class OtpInputStream extends ByteArrayInputStream {
    public OtpErlangObject read_any() throws OtpErlangDecodeException {
        // ...
        switch(tag) {
        // ...
        case OtpExternal.stringTag:
            return new OtpErlangString(this);

        case OtpExternal.listTag:
            return new OtpErlangList(this);
        // ...
        }
    }
}

lib/jinterface/java_src/com/ericsson/otp/erlang/OtpExternal.java


package com.ericsson.otp.erlang;

public class OtpExternal {
    /** The tag used for empty lists */
    public static final int nilTag = 106;

    /** The tag used for strings and lists of small integers */
    public static final int stringTag = 107;

    /** The tag used for non-empty lists */
    public static final int listTag = 108;
}

Significant Whitespace

Comment After Dot
DOT_OPERATION
strip_dot_space
Arguments vs Calls
bracket_identifier and paren_identifier
CALL
Operations

Comment after Dot

Uncommented Commented

Code Quoted Code Quoted

Issue #3316 Fixed in Elixir v1.1.0
Uncommented	Commented
Code	Quoted	Code	Quoted
`Module. identifier`	`{ :ok, { { :., [line: 1], [ { :__aliases__, [counter: 0, line: 1], [:Module] }, :function ] }, [line: 1], [] } }`	`Module. # a comment identifier`	`{ :ok, { { :., [line: 1], [ { :__aliases__, [counter: 0, line: 1], [:Module] }, :function ] }, [line: 1], [] } }`
`Module. \|>`	`{ :ok, { { :., [line: 1], [ { :__aliases__, [counter: 0, line: 1], [:Module] }, :\|> ] }, [line: 1], [] } }`	`Module. # a comment \|>`	`{ :error, { 2, "syntax error before: ", "'\|>'" } }`


Module.
identifier


{
 :ok,
 {
  {
   :.,
   [line: 1],
   [
    {
     :__aliases__,
     [counter: 0, line: 1],
     [:Module]
    },
    :function
   ]
  },
  [line: 1],
  []
 }
}


Module. # a comment
identifier


{
 :ok,
 {
  {
   :.,
   [line: 1],
   [
    {
     :__aliases__,
     [counter: 0, line: 1],
     [:Module]
    },
    :function
   ]
  },
  [line: 1],
  []
 }
}


Module.
|>


{
 :ok,
 {
  {
   :.,
   [line: 1],
   [
    {
     :__aliases__,
     [counter: 0, line: 1],
     [:Module]
    },
    :|>
   ]
  },
  [line: 1],
  []
 }
}


Module. # a comment
|>


{
 :error,
 {
  2,
  "syntax error before: ",
  "'|>'"
  }
}

Dot Operation

src/org/elixir_lang/Elixir.flex


<YYINITIAL, INTERPOLATION> {
  {DOT_OPERATOR} { pushAndBegin(DOT_OPERATION);
                   return ElixirTypes.DOT_OPERATOR; }
}

<DOT_OPERATION> {
  {AND_OPERATOR} { yybegin(CALL_MAYBE);
                   return ElixirTypes.AND_OPERATOR; }

  /*
   * Emulates strip_space in elixir_tokenizer.erl
   */

  {ESCAPED_EOL}|{WHITE_SPACE}+ { return TokenType.WHITE_SPACE; }
  {EOL}                        { return ElixirTypes.EOL; }

  {COMMENT}                    { return ElixirTypes.COMMENT; }

  .                            { org.elixir_lang.lexer.StackFrame stackFrame = pop();
                                 handleInState(stackFrame.getLastLexicalState()); }
}

`strip_dot_space`

Time Code

Before

Time	Code
Before	`tokenize([$.\|T], Line, Column, Scope, Tokens) -> {Rest, Counter, Offset} = strip_space(T, 0, Column + 1), handle_dot([$.\|Rest], Line + Counter, Offset - 1, Column, Scope, Tokens); strip_space(T, Counter, Column) -> case strip_horizontal_space(T) of {"\r\n" ++ Rest, _} -> strip_space(Rest, Counter + 1, 1); {"\n" ++ Rest, _} -> strip_space(Rest, Counter + 1, 1); {Rest, Length} -> {Rest, Counter, Column + Length} end.`
After	tokenize([$.\|T], Line, Column, Scope, Tokens) -> {Rest, Counter, Offset} = strip_dot_space(T, 0, Column + 1), handle_dot([$.\|Rest], Line + Counter, Offset - 1, Column, Scope, Tokens); strip_dot_space(T, Counter, Column) -> case strip_horizontal_space(T) of {"#" ++ Rest, _} -> strip_dot_space(tokenize_comment(Rest), Counter, 1); {"\r\n" ++ Rest, _} -> strip_dot_space(Rest, Counter + 1, 1); {"\n" ++ Rest, _} -> strip_dot_space(Rest, Counter + 1, 1); {Rest, Length} -> {Rest, Counter, Column + Length} end.


tokenize([$.|T], Line, Column, Scope, Tokens) ->
  {Rest, Counter, Offset} = strip_space(T, 0, Column + 1),
  handle_dot([$.|Rest], Line + Counter, Offset - 1, Column, Scope, Tokens);

strip_space(T, Counter, Column) ->
  case strip_horizontal_space(T) of
    {"\r\n" ++ Rest, _} -> strip_space(Rest, Counter + 1, 1);
    {"\n" ++ Rest, _}   -> strip_space(Rest, Counter + 1, 1);
    {Rest, Length}      -> {Rest, Counter, Column + Length}
  end.

After


tokenize([$.|T], Line, Column, Scope, Tokens) ->
  {Rest, Counter, Offset} = strip_dot_space(T, 0, Column + 1),
  handle_dot([$.|Rest], Line + Counter, Offset - 1, Column, Scope, Tokens);

strip_dot_space(T, Counter, Column) ->
  case strip_horizontal_space(T) of
    {"#" ++ Rest, _}    -> strip_dot_space(tokenize_comment(Rest), Counter, 1);
    {"\r\n" ++ Rest, _} -> strip_dot_space(Rest, Counter + 1, 1);
    {"\n" ++ Rest, _}   -> strip_dot_space(Rest, Counter + 1, 1);
    {Rest, Length}      -> {Rest, Counter, Column + Length}
  end.

Arguments vs Calls

No Space Space

Code Quoted Code Quoted

Parentheses

	No Space	Space
Parentheses	`function(positional)`	`{ :function, [line: 1], [ {:positional, [line: 1], nil} ] }`	`function (grouped)`	Error
Brackets	`dict[key]`	`{ { :., [line: 1], [Access, :get] }, [line: 1], [ {:dict, [line: 1], nil}, {:key, [line: 1], nil} ] }`	`function [element]`	`{ :function, [line: 1], [ [ {:element, [line: 1], nil} ] ] }`


function(positional)


{
 :function,
 [line: 1],
 [
  {:positional, [line: 1], nil}
 ]
}


function (grouped)

Error

Brackets


dict[key]


{
 {
  :.,
  [line: 1],
  [Access, :get]
 },
 [line: 1],
 [
  {:dict, [line: 1], nil},
  {:key, [line: 1], nil}
 ]
}


function [element]


{
 :function,
 [line: 1],
 [
  [
   {:element, [line: 1], nil}
  ]
 ]
}

Bracket and Paren Identifier

lib/elixir/src/elixir_tokenizer.erl


tokenize([H|_] = String, Line, Scope, Tokens) when ?is_downcase(H); H == $_ ->
  case tokenize_any_identifier(String, Line, Scope, Tokens) of
    {keyword, Rest, Check, T} ->
      handle_terminator(Rest, Line, Scope, Check, T);
    {identifier, Rest, Token} ->
      tokenize(Rest, Line, Scope, [Token|Tokens]);
    {error, _, _, _} = Error ->
      Error
  end;

tokenize_any_identifier(Original, Line, Scope, Tokens) ->
  {Rest, Identifier} = tokenize_identifier(Original, []),

  {AllIdentifier, AllRest} =
    case Rest of
      [H|T] when H == $?; H == $! -> {Identifier ++ [H], T};
      _ -> {Identifier, Rest}
    end,

  case unsafe_to_atom(AllIdentifier, Line, Scope) of
    {ok, Atom} ->
      tokenize_kw_or_other(AllRest, identifier, Line, Atom, Tokens);
    {error, Reason} ->
      {error, Reason, Original, Tokens}
  end.

tokenize_kw_or_other(Rest, Kind, Line, Atom, Tokens) ->
  case check_keyword(Line, Atom, Tokens) of
    nomatch ->
      {identifier, Rest, check_call_identifier(Kind, Line, Atom, Rest)};
    {ok, [Check|T]} ->
      {keyword, Rest, Check, T};
    {error, Token} ->
      {error, {Line, "syntax error before: ", Token}, atom_to_list(Atom) ++ Rest, Tokens}
  end.

check_call_identifier(_Kind, Line, Atom, [$(|_]) -> {paren_identifier, Line, Atom};
check_call_identifier(_Kind, Line, Atom, [$[|_]) -> {bracket_identifier, Line, Atom};
check_call_identifier(Kind, Line, Atom, _Rest)   -> {Kind, Line, Atom}.

Zero-Width Call

src/org/elixir_lang/Elixir.flex


<YYINITIAL, INTERPOLATION> {
  {IDENTIFIER} { pushAndBegin(CALL_OR_KEYWORD_PAIR_MAYBE);
                 return ElixirTypes.IDENTIFIER; }
}

<CALL_MAYBE, CALL_OR_KEYWORD_PAIR_MAYBE> {
  {OPENING_BRACKET}|{OPENING_PARENTHESIS} { org.elixir_lang.lexer.StackFrame stackFrame = pop();
                                            handleInState(stackFrame.getLastLexicalState());
                                            // zero-width token
                                            return ElixirTypes.CALL; }
}

<DOT_OPERATION> {
  {AND_OPERATOR} { yybegin(CALL_MAYBE);
                   return ElixirTypes.AND_OPERATOR; }
}

Because tokens are tied to highlighting in the JetBrains API, I didn't want to have to have separate bracket and parentheses identifier. It would also be more complicated for me because operators and quoted need to be bracket and parentheses identifier, but I can't tokenize them that way with JFlex.

So, instead of changing the identifier token type, I added a zero-width CALL token for when something that could act as an identifer is immediately followed by an opening bracket or a parentheses.

I needed a token for when there WASN'T a space instead of when there WAS a space because whitepace tokens are stripped when going from the tokenizer to the parser and I'd have had to change more rules to have significant white space instead of significant non-space.

Operations

src/org/elixir_lang/Elixir.bnf


matchedExpression ::= matchedBracketOperation |
                      matchedQualifiedBracketOperation |
                      matchedQualifiedParenthesesCall |
                      matchedQualifiedNoArgumentsCall |
                      matchedUnqualifiedParenthesesCall |
                      matchedUnqualifiedBracketOperation |
                      variable |
                      accessExpression

matchedParenthesesArguments ::= CALL parenthesesArguments parenthesesArguments?

matchedBracketOperation ::= matchedExpression bracketArguments
matchedQualifiedBracketOperation ::= matchedExpression dotInfixOperator relativeIdentifier CALL bracketArguments
matchedQualifiedParenthesesCall ::= matchedExpression dotInfixOperator relativeIdentifier matchedParenthesesArguments
matchedQualifiedNoArgumentsCall ::= matchedExpression dotInfixOperator relativeIdentifier !CALL
matchedUnqualifiedParenthesesCall ::= IDENTIFIER matchedParenthesesArguments
matchedUnqualifiedBracketOperation ::= IDENTIFIER CALL bracketArguments

Stab

Usage
YECC
Merging expressions into clauses
Grammar Kit

Usage

Code	Description
`fn x -> x + 1 end`	Anonymous function clause
`receive do {:ping, pid} -> send pid, :pong after 10 -> :timeout end`	Do block clauses
`try do raise "oops" rescue e in Runtimeerror -> e end`	Do block start
`(1 + 2)`	Parenthetical groups

YECC

lib/elixir/src/elixir_parser.yrl


access_expr -> fn_eol stab end_eol : build_fn('$1', build_stab(reverse('$2'))).
access_expr -> open_paren stab close_paren : build_stab(reverse('$2')).

stab -> stab_expr : ['$1'].
stab -> stab eol stab_expr : ['$3'|'$1'].

stab_eol -> stab : '$1'.
stab_eol -> stab eol : '$1'.

stab_expr -> expr : '$1'.
stab_expr -> stab_op_eol stab_maybe_expr : build_op('$1', [], '$2').
stab_expr -> call_args_no_parens_all stab_op_eol stab_maybe_expr :
               build_op('$2', unwrap_when(unwrap_splice('$1')), '$3').
stab_expr -> stab_parens_many stab_op_eol stab_maybe_expr :
               build_op('$2', unwrap_splice('$1'), '$3').
stab_expr -> stab_parens_many when_op expr stab_op_eol stab_maybe_expr :
               build_op('$4', [{'when', meta('$2'), unwrap_splice('$1') ++ ['$3']}], '$5').

stab_maybe_expr -> 'expr' : '$1'.
stab_maybe_expr -> '$empty' : nil.

To get a plain parenthetical group, like addition in parentheses, you start with access_expr, then get an open parenthesis. Dive into stab, then stab_expr. stab_expr can just be an expression, such as adding 1 + 2, so you climb back up to the close parenthesis and you have 1 + 2 in parentheses and no stab operator.

The other part of stabs that I couldn't figure out at first was how any anonymous function clause could have more than one line of code in it because there were only expr and no expr_list, but there is a pseudo-expression list because the second rule for stab says a stab is stab followed by an E-O-L and a stab_expr, so that can just recursively add more eol expr.

But, that still leaves the problem that all the expressions in a row aren't actually associated with the pattern or argument names before the stab operator.

Merging expressions into clauses

lib/elixir/src/elixir_parser.yrl


build_stab([{'->', Meta, [Left, Right]}|T]) ->
  build_stab(Meta, T, Left, [Right], []);

build_stab(Else) ->
  build_block(Else).

build_stab(Old, [{'->', New, [Left, Right]}|T], Marker, Temp, Acc) ->
  H = {'->', Old, [Marker, build_block(reverse(Temp))]},
  build_stab(New, T, Left, [Right], [H|Acc]);

build_stab(Meta, [H|T], Marker, Temp, Acc) ->
  build_stab(Meta, T, Marker, [H|Temp], Acc);

build_stab(Meta, [], Marker, Temp, Acc) ->
  H = {'->', Meta, [Marker, build_block(reverse(Temp))]},
  reverse([H|Acc]).

Grammar Kit

src/org/elixir_lang/Elixir.bnf


stabNoParenthesesSignature ::= noParenthesesArguments

stabParenthesesSignature ::= parenthesesArguments (whenInfixOperator expression)?
stabSignature ::= (stabParenthesesSignature |
                   stabNoParenthesesSignature)?

stabInfixOperator ::= EOL* STAB_OPERATOR EOL*

private stabOperationPrefix ::= stabSignature stabInfixOperator
private stabBodyExpression ::= !stabOperationPrefix expression
stabBody ::= stabBodyExpression (endOfExpression+ stabBodyExpression)*

stabOperation ::= stabOperationPrefix stabBody?
                  { implements = "org.elixir_lang.psi.Quotable" methods = [quote] }

stab ::= stabOperation (endOfExpression stabOperation)* |
         stabBody

anonymousFunction ::= FN endOfExpression?
                      stab
                      endOfExpression* END

parentheticalStab ::= OPENING_PARENTHESIS EOL*
                      (infixSemicolon? stab infixSemicolon? | infixSemicolon)
                      EOL* CLOSING_PARENTHESIS

accessExpression ::= anonymousFunction |
                     parentheticalStab

Like, I said, I thought that was a dirty trick to not have the grammar actually represent the AST directly, so I made IntellIJ Elixir's stab definition match the clauses directly and not do merge in Java. This was also necessary because the PSI tree is walked for other IDE features like Find Usage and Goto Definition.

The key to making this work is the negative look-ahead in stab body expression (stabBodyExpression), which prevents the start of a new stab clause from being included in the body of the previous stab.

This look-ahead is more expensive in terms of parse time because the look-ahead includes stabSignature, which can be any matched expression, which can be quite large, but in real world Elixir code, the function clause arguments and bodies should be small enough that this backtracking isn't an issue.

Unmatched Expressions

unmatched_expr
block_expr
block_list
block_identifier
Dangling Else Problem
unmatchedExpression

`unmatched_expr`

lib/elixir/src/elixir_parser.yrl


expr -> unmatched_expr : '$1'.

unmatched_expr -> empty_paren op_expr : build_op(element(1, '$2'), nil, element(2, '$2')).
unmatched_expr -> matched_expr op_expr : build_op(element(1, '$2'), '$1', element(2, '$2')).
unmatched_expr -> unmatched_expr op_expr : build_op(element(1, '$2'), '$1', element(2, '$2')).
unmatched_expr -> unary_op_eol expr : build_unary_op('$1', '$2').
unmatched_expr -> at_op_eol expr : build_unary_op('$1', '$2').
unmatched_expr -> capture_op_eol expr : build_unary_op('$1', '$2').
unmatched_expr -> block_expr : '$1'.

op_expr -> match_op_eol expr : {'$1', '$2'}.
op_expr -> add_op_eol expr : {'$1', '$2'}.
op_expr -> mult_op_eol expr : {'$1', '$2'}.
op_expr -> hat_op_eol expr : {'$1', '$2'}.
op_expr -> two_op_eol expr : {'$1', '$2'}.
op_expr -> and_op_eol expr : {'$1', '$2'}.
op_expr -> or_op_eol expr : {'$1', '$2'}.
op_expr -> in_op_eol expr : {'$1', '$2'}.
op_expr -> in_match_op_eol expr : {'$1', '$2'}.
op_expr -> type_op_eol expr : {'$1', '$2'}.
op_expr -> when_op_eol expr : {'$1', '$2'}.
op_expr -> pipe_op_eol expr : {'$1', '$2'}.
op_expr -> comp_op_eol expr : {'$1', '$2'}.
op_expr -> rel_op_eol expr : {'$1', '$2'}.
op_expr -> arrow_op_eol expr : {'$1', '$2'}.

`block_expr`

lib/elixir/src/elixir_parser.yrl


block_expr -> parens_call call_args_parens do_block : build_identifier('$1', '$2' ++ '$3').
block_expr -> parens_call call_args_parens call_args_parens do_block : build_nested_parens('$1', '$2', '$3' ++ '$4').
block_expr -> dot_do_identifier do_block : build_identifier('$1', '$2').
block_expr -> dot_identifier call_args_no_parens_all do_block : build_identifier('$1', '$2' ++ '$3').

do_block -> do_eol 'end' : [[{do,nil}]].
do_block -> do_eol stab end_eol : [[{do, build_stab(reverse('$2'))}]].
do_block -> do_eol block_list 'end' : [[{do, nil}|'$2']].
do_block -> do_eol stab_eol block_list 'end' : [[{do, build_stab(reverse('$2'))}|'$3']].

`block_list`

lib/elixir/src/elixir_parser.yrl


block_eol -> block_identifier : '$1'.
block_eol -> block_identifier eol : '$1'.

block_item -> block_eol stab_eol : {?exprs('$1'), build_stab(reverse('$2'))}.
block_item -> block_eol : {?exprs('$1'), nil}.

block_list -> block_item : ['$1'].
block_list -> block_item block_list : ['$1'|'$2'].

`block_identifier`

lib/elixir/src/elixir_tokenizer.erl


tokenize_kw_or_other(Rest, Kind, Line, Atom, Tokens) ->
  case check_keyword(Line, Atom, Tokens) of
    nomatch ->
      {identifier, Rest, check_call_identifier(Kind, Line, Atom, Rest)};
    {ok, [Check|T]} ->
      {keyword, Rest, Check, T};
    {error, Token} ->
      {error, {Line, "syntax error before: ", Token}, atom_to_list(Atom) ++ Rest, Tokens}
  end.

check_keyword(Line, Atom, Tokens) ->
  case keyword(Atom) of
    false    -> nomatch;
    token    -> {ok, [{Atom, Line}|Tokens]};
    block    -> {ok, [{block_identifier, Line, Atom}|Tokens]};
    unary_op -> {ok, [{unary_op, Line, Atom}|Tokens]};
    Kind     -> {ok, add_token_with_nl({Kind, Line, Atom}, Tokens)}
  end.

keyword('after')  -> block;
keyword('else')   -> block;
keyword('rescue') -> block;
keyword('catch')  -> block;

Dangling Else Problem


Ambiguous code	if a then if b then s else s2	a b, c do s end
Bind to Outermost	if a then (if b then s) else s2	a b, (c) do s end
Bind to Closest	if a then (if b then s else s2)	a b, (c do s end)

The dangling else problem is a problem with languages like C or Java that have an optional else when nesting.

The problem can be resolved by either saying the else binds to the outer most if or the closest if.

This problem is also possible with do blocks in Elixir when resolving which function call a do block binds to.

In actual Elixir grammar, the do block always binds to the outer-most function call, which turns out to be the easy choice for rightmost derivation parsers like yecc. But, for leftmost derivation parsers like Grammar Kit, all the text books on compiler design advise to pick binding to the closest because it's just not possible in simple LL(1) parsers to even do bind to outermost. Thankfully, Grammar Kit is not a simple LL(1) parser, so I was able to find a solution.

`unmatchedExpression`

src/org/elixir_lang/Elixir/bnf


private expression ::= emptyParentheses |
                       unmatchedExpression |
                       unqualifiedNoParenthesesManyArgumentsCall

unmatchedExpression ::= unmatchedCaptureNonNumericOperation |
                        // ...
                        unmatchedQualifiedNoParenthesesCall |
                        // ...
                        unmatchedAccessExpression

unmatchedQualifiedNoParenthesesCall ::= unmatchedExpression dotInfixOperator relativeIdentifier noParenthesesOneArgument doBlock?

noParenthesesOneArgument ::= // ...
                             !(DUAL_OPERATOR SIGNIFICANT_WHITE_SPACE) matchedExpression

When adding unmatchedExpression to Elixir.bnf, I ended up eliminating matchedExpression from the list of valid expressions.

This is because the important distinction from matchedExpression is that unmatchedExpressions can optionally have a block, but any unparenthesised function call as an argument to an unmatchedExpression function call must be a matchedExpression because blocks always bind to the outermost function call.

Both matchedExpression and unmatchedExpression use noParenthesesOneArgument, but crucially in unmatchedExpression, it switches the grammar from looking for unmatchedExpression and do blocks to disallowing do blocks.

So, while in the YECC grammar, a block expression is a matched expression followed by do block, in the grammar kit grammar, a matched expression is an unmatched expression that can't have a block.

Parsing `elixir-lang/elixir`

Function Captures
REFERENCE_OPERATION
operator_kw
Piping blocks
Unmatched Associativity
v1.0.0

Function Captures

Code	Quoted
`&Module.function/2`	`{ :&, [line: 1], [ { :/, [line: 1], [ { { :., [line: 1], [ {:__aliases__, [counter: 0, line: 1], [:Module]}, :function ] }, [line: 1], [] }, 2 ] } ] }`
`&function/2`	`{ :&, [line: 1], [ { :/, [line: 1], [ {:function, [line: 1], nil}, 2 ] } ] }`
`&\|\|/2`	`{ :&, [line: 1], [ { :/, [line: 1], [ {:\|\|, [line: 1], nil}, 2 ] } ] }`
`&or/2`	Error

`REFERENCE_OPERATION`

src/org/elixir_lang/Elixir.flex


TWO_TOKEN_OR_OPERATOR = "or" |
                        "||"

TWO_TOKEN_OPERATOR = {TWO_TOKEN_AND_OPERATOR} |
                     {TWO_TOKEN_ARROW_OPERATOR} |
                     {TWO_TOKEN_ASSOCIATION_OPERATOR} |
                     {TWO_TOKEN_COMPARISON_OPERATOR} |
                     {TWO_TOKEN_IN_MATCH_OPERATOR} |
                     {TWO_TOKEN_OR_OPERATOR} |
                     {TWO_TOKEN_RELATIONAL_OPERATOR} |
                     {TWO_TOKEN_STAB_OPERATOR} |
                     {TWO_TOKEN_TUPLE_OPERATOR} |
                     {TWO_TOKEN_TWO_OPERATOR} |
                     {TWO_TOKEN_TYPE_OPERATOR}

REFERENCABLE_OPERATOR = {FOUR_TOKEN_OPERATOR} |
                        {THREE_TOKEN_OPERATOR} |
                        {TWO_TOKEN_OPERATOR} |
                        {ONE_TOKEN_REFERENCABLE_OPERATOR}

REFERENCE_OPERATOR = "/"
REFERENCE_INFIX_OPERATOR = ({WHITE_SPACE}|{EOL})*{REFERENCE_OPERATOR}

<YYINITIAL, INTERPOLATION> {
 {REFERENCABLE_OPERATOR} / {REFERENCE_INFIX_OPERATOR} { pushAndBegin(REFERENCE_OPERATION);
                                                         return ElixirTypes.IDENTIFIER; }
}

<REFERENCE_OPERATION> {
  {ESCAPED_EOL}|{WHITE_SPACE}+ { return TokenType.WHITE_SPACE; }
  {EOL}                        { return ElixirTypes.EOL; }
  {REFERENCE_OPERATOR}         { org.elixir_lang.lexer.StackFrame stackFrame = pop();
                                 yybegin(stackFrame.getLastLexicalState());
                                 return ElixirTypes.MULTIPLICATION_OPERATOR; }
}

Issue #3486 fixed in v1.1.0

lib/elixir/src/elixir_tokenizer.erl


-define(operator_kw(A),
  A == 'and';
  A == 'or';
  A == 'when';
  A == 'not';
  A == 'in').

check_keyword(_Line, _Column, _Length, Atom, [{capture_op, _, _}|_]) when ?operator_kw(Atom) ->
  nomatch;

Piping blocks

lib/mix/lib/mix/tasks/deps.clean.ex


defmodule Mix.Tasks.Deps.Clean do
  defp checked_deps(build, deps) do
    for root <- [deps, build],
        path <- Path.wildcard(Path.join(root, "*")),
        File.dir?(path) do
      Path.basename(path)
    end
    |> Enum.uniq()
    |> List.delete(to_string(Mix.Project.config[:app]))
  end
end

Issue Fixed in v1.1.0

Matched Unmatched

Code

	Matched	Unmatched
Code	`one \|> two \|> three`	`one do end \|> two \|>`
Quoted	`{ :\|>, [line: 3], [ { :\|>, [line: 2], [ {:one, [line: 1], nil}, {:two, [line: 2], nil} ] }, {:three, [line: 3], nil} ] }`	`{ :\|>, [line: 2], [ {:one, [line: 1], [[do: nil]]}, { :\|>, [line: 3], [ {:two, [line: 2], nil}, {:three, [line: 3], nil} ] } ] }`


one
|> two
|> three


one do end
|> two
|>

Quoted


{
 :|>,
 [line: 3],
 [
  {
   :|>,
   [line: 2],
   [
    {:one, [line: 1], nil},
    {:two, [line: 2], nil}
   ]
  },
  {:three, [line: 3], nil}
 ]
}


{
 :|>,
 [line: 2],
 [
  {:one, [line: 1], [[do: nil]]},
   {
    :|>,
    [line: 3],
    [
     {:two, [line: 2], nil},
     {:three, [line: 3], nil}
   ]
  }
 ]
}

The arrow operators, including the pipeline operator, are left-associative, but when the operand in the pipeline is an umatched expression, then the quoted form made it look effectively right-associative.

I thought I had missed some post-processing in the Erlang code, but José Valim confirmed it was a bug in the native parser due to in his word, "`bar pipe baz` ends up being reduced first as the current grammar rules forced it to happen".

So, because I used a different class of parser that doesn't do reduce and shift operations, I was able to stumble upon this bug. Having more test cases, because I didn't trust my own understanding of the original grammar and how to translate it to Grammar Kit also let me find the other bugs, so an alternative implementation is a good way to ensure a tokenizer and parser for a language has covered all the edge cases.

v1.0.0

Date	Days		Commits		Version
Date	Delta	Total	Delta	Total	Commits/Day	Name
2015‑07‑27	19	365	158	1356	2.44	1.0.0

Enhancements
- Update ant build on travis-ci.org to use IDEA 14.1.4 (from 14.0.2)
- Parser is verified to quote the same as native Elixir
Bug Fixes
- Fix parsing of unary vs binary +/- with leading and trailing spaces and newlines
- Allow EOL between list arguments and ]
- Relative identifiers after . that start with and, or, and not will be lexed as a single identifier instead of and, or, or not followed by another identifier.
- end is allowed as a relative identifier after .
- Fix (...) as part of matched expression in no parentheses stab signature
- Allow multiple newlines to mark the end of an expression, but only one ;
- Allow operators in function references (<op>/<arity>) for function captures (&<op>/<arity>)
- unquote_splicing is properly wrapped in __block__ when in stab bodies
- Check for matching terminator in heredocs when determining white space type at beginning of line
- Allow <space>+<EOL> to count as addition
- Unary expressions inside parentheses are no longer marked ambiguous_op: nil
- Differentiate between Qualifier.'relative'() vs Qualifier.'relative' () and Qualifier."relative"() vs Qualifier."relative" ()
- Fix link to Elixir website in README
- All tokens have human-readable names and/or expected characters for better error messages
Incompatible Changes
- New Elixir File has moved to the last item in the New File menu to preserve CTRL+N ENTER keyboard shortcut for New > File