.lr

An LR(1) parser generator and visualizer created for educational purposes.

---

Table of Contents

• What is an LR(1) parser?
• Why did you make this?
• How can I use the CLI in the picture?
• Can I use it as a standalone library?
• How it works?
  • 1) Parsing the grammar
  • 2) Computing FIRST sets
  • 3) Computing FOLLOW sets
  • 4) Constructing the LR(1) automaton
  • 5) Constructing ACTION and GOTO tables
  • 6) Tokenizing the input
  • 7) Parsing the tokens
• Can I have symbols that can match to empty string?
• Can I have an LALR(1) parser instead of an LR(1) parser?
• What happens if the grammar is ambiguous?
• Any benchmarks?
• Can I modify it?
• Which resources did you use when creating this?
• How is it licensed?

What is an LR(1) parser?

LR(1) parser is a type of bottom-up parser for parsing a subset of context free languages.

1 indicates that the parser will use a single lookahead token when making parsing decisions.

LR(1) parsers are powerful because they can parse a wide range of context free languages, including most programming languages!

Why did you make this?

To learn and to help others learn! This project allows you to visualize LR(1) parsers, from construction to parsing, which makes it easier to understand how they work.

How can I use the CLI in the picture?

If you want to play around with dotlr to visualize parser construction and step-by-step parsing of different grammars, you can use the main executable of the crate.

Installation

You can install the dotlr cli from crates.io.

cargo install dotlr

Usage

Paste the following into a file called grammar.lr:

P -> E

E -> E '+' T
E -> T

T -> %id '(' E ')'
T -> %id

%id -> /[A-Za-z][A-Za-z0-9]*/

Run dotlr cli with the grammar file and an input:

dotlr grammar.lr "foo(bar + baz)"

It'll print:

+--------------------------------+
|            Grammar             |
+--------------------------------+
| P -> E                         |
| E -> E '+' T                   |
| E -> T                         |
| T -> %id '(' E ')'             |
| T -> %id                       |
|                                |
| %id -> /^[A-Za-z][A-Za-z0-9]*/ |
+--------------------------------+
+--------+-----------+-----------------+
| Symbol | First Set |   Follow Set    |
+--------+-----------+-----------------+
| T      | { %id }   | { $, '+', ')' } |
+--------+-----------+-----------------+
| E      | { %id }   | { $, '+', ')' } |
+--------+-----------+-----------------+
| P      | { %id }   | { $ }           |
+--------+-----------+-----------------+
+-------+------------------------+--------------+---------------+
| State |         Items          |  Lookaheads  |  Transitions  |
+-------+------------------------+--------------+---------------+
| 0     |  P -> . E              | { $ }        |   E   ->  1   |
|       |  E -> . E '+' T        | { $, '+' }   |   T   ->  2   |
|       |  E -> . T              | { $, '+' }   |  %id  ->  3   |
|       |  T -> . %id '(' E ')'  | { $, '+' }   |               |
|       |  T -> . %id            | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 1     |  P -> E .              | { $ }        |  '+'  ->  14  |
|       |  E -> E . '+' T        | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 2     |  E -> T .              | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 3     |  T -> %id . '(' E ')'  | { $, '+' }   |  '('  ->  4   |
|       |  T -> %id .            | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 4     |  T -> %id '(' . E ')'  | { $, '+' }   |   E   ->  5   |
|       |  E -> . E '+' T        | { ')', '+' } |  %id  ->  6   |
|       |  E -> . T              | { ')', '+' } |   T   ->  9   |
|       |  T -> . %id '(' E ')'  | { ')', '+' } |               |
|       |  T -> . %id            | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 5     |  T -> %id '(' E . ')'  | { $, '+' }   |  '+'  ->  11  |
|       |  E -> E . '+' T        | { ')', '+' } |  ')'  ->  13  |
+-------+------------------------+--------------+---------------+
| 6     |  T -> %id . '(' E ')'  | { ')', '+' } |  '('  ->  7   |
|       |  T -> %id .            | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 7     |  T -> %id '(' . E ')'  | { ')', '+' } |  %id  ->  6   |
|       |  E -> . E '+' T        | { ')', '+' } |   E   ->  8   |
|       |  E -> . T              | { ')', '+' } |   T   ->  9   |
|       |  T -> . %id '(' E ')'  | { ')', '+' } |               |
|       |  T -> . %id            | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 8     |  T -> %id '(' E . ')'  | { ')', '+' } |  ')'  ->  10  |
|       |  E -> E . '+' T        | { ')', '+' } |  '+'  ->  11  |
+-------+------------------------+--------------+---------------+
| 9     |  E -> T .              | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 10    |  T -> %id '(' E ')' .  | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 11    |  E -> E '+' . T        | { ')', '+' } |  %id  ->  6   |
|       |  T -> . %id '(' E ')'  | { ')', '+' } |   T   ->  12  |
|       |  T -> . %id            | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 12    |  E -> E '+' T .        | { ')', '+' } |               |
+-------+------------------------+--------------+---------------+
| 13    |  T -> %id '(' E ')' .  | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 14    |  E -> E '+' . T        | { $, '+' }   |  %id  ->  3   |
|       |  T -> . %id '(' E ')'  | { $, '+' }   |   T   ->  15  |
|       |  T -> . %id            | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
| 15    |  E -> E '+' T .        | { $, '+' }   |               |
+-------+------------------------+--------------+---------------+
+-------+---------------------------------------+----------------------+
|       |                Action                 |         Goto         |
| State | ------------------------------------- | -------------------- |
|       |    '+'    '('    ')'    %id     $     |    P     E     T     |
+-------+---------------------------------------+----------------------+
| 0     |     -      -      -     s3      -     |    -     1     2     |
+-------+---------------------------------------+----------------------+
| 1     |    s14     -      -      -     a1     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 2     |    r3      -      -      -     r3     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 3     |    r5     s4      -      -     r5     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 4     |     -      -      -     s6      -     |    -     5     9     |
+-------+---------------------------------------+----------------------+
| 5     |    s11     -     s13     -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 6     |    r5     s7     r5      -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 7     |     -      -      -     s6      -     |    -     8     9     |
+-------+---------------------------------------+----------------------+
| 8     |    s11     -     s10     -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 9     |    r3      -     r3      -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 10    |    r4      -     r4      -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 11    |     -      -      -     s6      -     |    -     -     12    |
+-------+---------------------------------------+----------------------+
| 12    |    r2      -     r2      -      -     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 13    |    r4      -      -      -     r4     |    -     -     -     |
+-------+---------------------------------------+----------------------+
| 14    |     -      -      -     s3      -     |    -     -     15    |
+-------+---------------------------------------+----------------------+
| 15    |    r2      -      -      -     r2     |    -     -     -     |
+-------+---------------------------------------+----------------------+

> foo(bar + baz)

P
└─ E
   └─ T
      ├─ foo
      ├─ (
      ├─ E
      │  ├─ E
      │  │  └─ T
      │  │     └─ bar
      │  ├─ +
      │  └─ T
      │     └─ baz
      └─ )

+------+---------------+-------------------+---------------------------+-------------------------------+
| Step |  State Stack  |   Symbol Stack    |      Remaining Input      |         Action Taken          |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 0    | 0             |                   | %id '(' %id '+' %id ')' $ | Shift 3                       |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 1    | 0 3           | %id               |     '(' %id '+' %id ')' $ | Shift 4                       |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 2    | 0 3 4         | %id '('           |         %id '+' %id ')' $ | Shift 6                       |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 3    | 0 3 4 6       | %id '(' %id       |             '+' %id ')' $ | Reduce 4 (T -> %id)           |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 4    | 0 3 4 9       | %id '(' T         |             '+' %id ')' $ | Reduce 2 (E -> T)             |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 5    | 0 3 4 5       | %id '(' E         |             '+' %id ')' $ | Shift 11                      |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 6    | 0 3 4 5 11    | %id '(' E '+'     |                 %id ')' $ | Shift 6                       |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 7    | 0 3 4 5 11 6  | %id '(' E '+' %id |                     ')' $ | Reduce 4 (T -> %id)           |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 8    | 0 3 4 5 11 12 | %id '(' E '+' T   |                     ')' $ | Reduce 1 (E -> E '+' T)       |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 9    | 0 3 4 5       | %id '(' E         |                     ')' $ | Shift 13                      |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 10   | 0 3 4 5 13    | %id '(' E ')'     |                         $ | Reduce 3 (T -> %id '(' E ')') |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 11   | 0 2           | T                 |                         $ | Reduce 2 (E -> T)             |
+------+---------------+-------------------+---------------------------+-------------------------------+
| 12   | 0 1           | E                 |                         $ | Accept 0 (P -> E)             |
+------+---------------+-------------------+---------------------------+-------------------------------+

You can also enter REPL mode if you omit the input:

dotlr grammar.lr

Can I use it as a standalone library?

Yes, you can depend on the dotlr crate from crates.io.

Setup

Paste the following to your dependencies section of your Cargo.toml:

dotlr = { version = "0.4", default-features = false }

Example

Here is a basic example that shows the primary operations of the dotlr crate:

use dotlr::{
  Grammar,
  Parser,
  ParserError,
};

const GRAMMAR: &str = r#"

P -> E

E -> E '+' T
E -> T

T -> %id '(' E ')'
T -> %id

%id -> /[A-Za-z][A-Za-z0-9]*/

"#;

const INPUT: &str = r#"

foo(bar + baz)

"#;

fn main() {
  let grammar = match Grammar::parse(GRAMMAR.trim()) {
    Ok(grammar) => grammar,
    Err(error) => {
      eprintln!("grammar error: {}", error);
      return;
    }
  };
  let parser = match Parser::lr(grammar) {
    Ok(parser) => parser,
    Err(error) => {
      eprintln!("parser error: {}", error);
      if let ParserError::Conflict { parser, .. } = error {
        parser.dump();
      }
      return;
    }
  };
  let tokens = match parser.tokenize(INPUT.trim()) {
    Ok(tokens) => tokens,
    Err(error) => {
      eprintln!("tokenization error: {}", error);
      return;
    }
  };
  let (parse_trace, parse_tree) = match parser.trace(tokens) {
    Ok(result) => result,
    Err(error) => {
      eprintln!("parsing error: {}", error);
      return;
    }
  };

  parser.dump();
  println!();
  parse_tree.dump();
  println!();
  parse_trace.dump(parser.grammar());
}

How does it work?

Let's go over a step-by-step construction of the parser for the following grammar:

E -> E '+' F
E -> F

F -> F '*' T
F -> T

T -> %b

%b -> /[0-1]/

And then do a step-by-step explanation of the parsing steps for the following input:

1 + 0 * 1

Few notes before starting:

• $ represents the end of input token
• ε represents the empty token

1) Parsing the grammar

First, we need to parse the grammar string to a grammar object that we can work with.

The grammar object will consist of:

• symbols (HashSet):

  • The set of symbols in the grammar
    (e.g., { E, F, T })

• start_symbol (Symbol):

  • The symbol to parse
    (e.g., E)

• empty_symbols (HashSet):

  • The set of symbols that can expand to empty string (i.e., ∀S: S -> '' ∈ rules)
    (e.g., T)

• constant_tokens (HashSet):

  • The set of constant tokens in the grammar
    (e.g., { '+', '*' })

• regular_expressions (HashMap<RegexToken, Regex>):

  • The map of regular expression tokens to their corresponding compiled regular expressions
    (e.g., { b -> /[0-1]/ })

• rules (Vec):

  • The list of rules in the grammar
    (e.g., [ E -> E '+' F, E -> F, ... ])

This is done in src/grammar.rs with a simple handwritten parser.

2) Computing FIRST sets

Now, we need to compute a set of tokens for each symbol in the grammar according to the following constraints:

• For each token ∈ FIRST(Symbol), at least one of the following conditions must hold:

  • Symbol -> '' ∈ grammar.rules and token == ε

  • Symbol -> (EmptySymbol1 ... EmptySymbolN) ∈ grammar.rules and token == ε

  • Symbol -> (EmptySymbol1 ... EmptySymbolN) token ... ∈ grammar.rules

  • Symbol -> (EmptySymbol1 ... EmptySymbolN) NonEmptySymbol ... ∈ grammar.rules and token ∈ FIRST(NonEmptySymbol)

As for the implementation, here is a python-like pseudocode of the algorithm to compute FIRST sets:

# Start with FIRST(all_symbols) = {}
first_sets = {}

# Iterate until no more changes
while first_sets.has_changed():
    # Iterate over the rules of the grammar
    for rule in grammar:
        # If rule is empty pattern
        if rule.is_empty_pattern:
            # S -> '' <==> S can start with ε
            # -------------------------------
            # Add ε to the FIRST set of the symbol of the rule
            first_sets[rule.symbol].add(ε)
            # Break the processing of the rule as it's fully processed
            break

        # Iterate over the atoms of the pattern of the rule
        for atom in rule.pattern:
            # If atom is a token
            if atom.is_token:
                # S -> (EmptySymbol1 ... EmptySymbolN) '+' ... <==> S can start with '+'
                # ----------------------------------------------------------------------
                # Add the matching token to the FIRST set of the symbol of the rule
                first_sets[rule.symbol].add(atom)
                # Break the processing of the rule
                # as the rule cannot provide any other first tokens
                break

            # If atom is a symbol
            elif atom.is_symbol:
                # S -> (EmptySymbol1 ... EmptySymbolN) E ... <==> S can start with anything E can start with
                # ------------------------------------------------------------------------------------------
                # Add every token in the FIRST set of the matching symbol
                # to the FIRST set of the symbol except ε as it's treated
                # in a special way through the loop
                first_sets[rule.symbol].extend(first_sets[atom].exclude(ε))
                # If the symbol cannot be empty (E -> '' ∉ grammar.rules)
                if not atom.can_be_empty:
                    # Break the processing of the rule
                    # as the rule cannot provide any other first tokens
                    break

        # If the loop is not broken manually
        else:
            # S -> EmptySymbol1 ... EmptySymbolN <==> S can start with 'ε'
            # -------------------------------------------------------------
            # Add ε to the FIRST set of the symbol of the rule
            first_sets[rule.symbol].add(ε)

This is done in src/tables.rs.

FIRST sets of the example grammar:

+--------+-----------+
| Symbol | First Set |
+--------+-----------+
| T      | { %b }    |
+--------+-----------+
| F      | { %b }    |
+--------+-----------+
| E      | { %b }    |
+--------+-----------+

3) Computing FOLLOW sets

Next, we need to compute another set of tokens for each symbol in the grammar according the following constraints:

• For each token ∈ FOLLOW(Symbol), at least one of the following conditions must hold:

  • Symbol == grammar.start_symbol and token == $

  • Anything -> ... Symbol (EmptySymbol1 ... EmptySymbolN) token ... ∈ grammar.rules

  • Anything -> ... Symbol (EmptySymbol1 ... EmptySymbolN) AnotherSymbol ... ∈ grammar.rules and token ∈ FIRST(AnotherSymbol) and token != ε

  • AnotherSymbol -> ... Symbol (EmptySymbol1 ... EmptySymbolN) ∈ grammar.rules and token ∈ FOLLOW(AnotherSymbol)

  • Symbol -> ... AnotherSymbol ∈ grammar.rules and token ∈ FOLLOW(AnotherSymbol)

As for the implementation, here is a python-like pseudocode of the algorithm to compute FOLLOW sets:

# Start with just FOLLOW(grammar.start_symbol) = { $ }
follow_sets = { grammar.start_symbol: { $ } }

# Iterate until no more changes
while follow_sets.has_changed():
    # Iterate over the rules of the grammar
    for rule in grammar:
        # Iterate over the atoms of the pattern of the rule
        for i in range(len(rule.pattern) - 1):
            # If the atom is a symbol
            if rule.pattern[i].is_symbol:
                # Iterate over the remaining atoms
                for j in range(i + 1, len(rule.pattern)):
                    # If the next atom is a token
                    if rule.pattern[j].is_token:
                        # S -> ... E (EmptySymbol1 ... EmptySymbolN) '+' ... <==> E can follow '+'
                        # ------------------------------------------------------------------------
                        # Add the matching token to the FOLLOW set of the matching symbol
                        follow_sets[rule.pattern[i]].add(rule.pattern[j])
                        # Break the processing of the rule
                        # as the rule cannot provide any other follow tokens
                        break

                    # Or if the next atom is a symbol
                    elif rule.pattern[j].is_symbol:
                        # S -> ... E (EmptySymbol1 ... EmptySymbolN) F ... <==> E can follow anything F can start with
                        # --------------------------------------------------------------------------------------------
                        # Add every token in the FIRST set of the second symbol
                        # to the FOLLOW set of the first symbol
                        # except ε as it's shouldn't be in the follow set
                        follow_sets[rule.pattern[i]].extend(first_sets[rule.pattern[j]].exclude(ε))
                        # If the symbol cannot be empty (F -> '' ∉ grammar.rules)
                        if not rule.pattern[j].can_be_empty:
                            # Break the processing of the rule
                            # as the rule cannot provide any other follow tokens
                            break

                # If the loop is not broken manually
                else:
                    # A -> ... S (EmptySymbol1 ... EmptySymbolN) <==> S can follow anything A can follow
                    # ----------------------------------------------------------------------------------
                    # Add every token in the FOLLOW set of the symbol of the rule
                    # to the FOLLOW set of the symbol of the atom
                    follow_sets[rule.patten[i]].extend(follow_sets[rule.symbol])

        # If pattern of ends with a symbol
        if rule.pattern[-1].is_symbol:
            # S -> ... E <==> S can follow anything E can follow
            # --------------------------------------------------
            # Add every token in the FOLLOW set of the symbol of the last atom
            # to the FOLLOW set of the symbol of the rule
            follow_sets[rule.symbol].extend(follow_sets[rule.patten[-1]])

This is done in src/tables.rs.

FOLLOW sets of the example grammar:

+--------+-----------------+
| Symbol |   Follow Set    |
+--------+-----------------+
| T      | { $, '+', '*' } |
+--------+-----------------+
| F      | { $, '+', '*' } |
+--------+-----------------+
| E      | { $, '+' }      |
+--------+-----------------+

4) Constructing the LR(1) automaton

It's time to construct the LR(1) automaton for the grammar.

Here is the drawing of the LR(1) automaton of a different grammar to get an intuition of what an LR(1) automaton is:

An automaton object is just of a list of states.

Each state has:

• id (StateId = usize):

  • The identifier of the state
    (e.g., 0, 1)

• items (Vec):

  • The list of LR(1) items of the state
    (e.g., E -> E . '+' F | { $, '+' })

• transitions (HashMap<AtomicPattern, StateId>):

  • The map of atomic patterns that would make transition to a new state
    (e.g., { '+' -> 7 }, { %b -> 4, T -> 6 })

Each item has:

• rule (Rule):

  • Underlying rule of the item
    (e.g., E -> E '+' F in E -> E . '+' F | { $, '+' })

• dot (usize):

  • Position of the dot in the rule
    (e.g., 1 in E -> E . '+' F | { $, '+' })

• lookahead (HashSet):

  • The set of tokens that could follow after the rule is applied. Keep in mind that, one of the lookahead tokens MUST follow for the rule to be applied.
    (e.g., { $, '+' } in E -> E . '+' F | { $, '+' })

As for the implementation, here is a python-like pseudocode of the algorithm to construct the LR(1) automaton:

# Setup the kernel of the first state
first_state = next_empty_state()
for rule in grammar.rules:
    if rule.symbol == grammar.start_symbol:
        first_state.add_item(Item(rule, dot=0, lookahead={$}))

# Initialize construction state
states_to_process = [first_state]
processed_states = []

# Iterate until there aren't any more states to process.
while len(states_to_process) > 0:
    # Get the state to process
    state_to_process = states_to_process.pop()

    # Computing closure of the state to process
    # Loop until no more items are added
    while True:
        new_items = []
        # Iterate current items to obtain new items
        for item in state_to_process.items:
            # If dot is not at the end of the pattern
            if item.dot != len(item.rule.pattern):
                # And if there is a symbol after dot
                if item.rule.pattern[item.dot].is_symbol:
                    # Compute the lookahead for the new item
                    if item.dot == len(item.rule.pattern) - 1:
                        # S -> ... . E <==> Tokens in the current lookahead can follow E
                        # --------------------------------------------------------------
                        lookahead = item.lookahead
                    elif item.rule.pattern[item.dot + 1].is_token:
                        # S -> ... . E '+' <==> '+' can follow E
                        # --------------------------------------
                        lookahead = {item.rule.pattern[item.dot + 1]}
                    elif item.rule.pattern[item.dot + 1].is_symbol:
                        # S -> ... . E F ... <==> Tokens in FIRST(F) can follow E
                        # -------------------------------------------------------
                        lookahead = first_sets[item.rule.pattern[item.dot + 1]]
                        if grammar.can_all_be_empty(item.rule.pattern[item.dot + 1:]):
                            # S -> ... . E ε ... ε <==> Tokens in the current lookahead can follow E
                            # S -> ... . E ε ... ε <==> Tokens in FOLLOW(E) can follow E
                            # ----------------------------------------------------------------------
                            lookahead = union(
                                lookahead,
                                item.lookahead,
                                follow_sets[item.rule.pattern[item.dot + 1]],
                            )


                    # Iterate over the rules of the grammar
                    for rule in grammar.rules:
                        # If the rule is for the symbol after dot
                        if rule.symbol == item.rule.pattern[item.dot]:
                            # Create a new item from the rule, with dot at the beginning
                            new_item = Item(rule, dot=0, lookahead=lookahead)
                            # If the item is not already in items of the state
                            if new_item not in state_to_process.items:
                                # Add it the set of new items
                                new_items.push(new_item)

        # Process new items
        for new_item in new_items:
            # If a similar item with the same rule and the same dot but a different lookahead exists
            if state_to_process.has_same_base_item(new_item):
                # Merge lookaheads
                state_to_process.merge_base_items(new_item)

            # Otherwise
            else:
                # Add the new item directly
                state_to_process.items.add(new_item)

        # If state hasn't changed, break the loop
        if not state_to_process.items.has_changed():
            break

    # Merge the states to process with an already existing state with the same closure.
    replaced = False
    for existing_state_with_same_items in processed_states:
        if existing_state_with_same_items.items == state_to_process.items:
            replaced = True
            for state in processed_states:
                # Replace transitions from existing states to point to the correct state.
                state.transitions.replace_value(state_to_process, existing_state_with_same_items)
            break
    if replaced:
        # If it's merged with an existing state, there is nothing else to do
        continue

    # Compute transitions of from the state to process.
    for item in state_to_process.items:
        # If the rule of the items is empty pattern
        if item.rule.is_empty_pattern:
            # S -> . ε <==> No need to create a transition to item  S -> ε .
            # --------------------------------------------------------------
            continue

        # If dot is not at the end
        if item.dot == len(item.rule.pattern):
            # S -> ... . <==> Can't create a transition as the dot is already at the end
            # --------------------------------------------------------------------------
            continue

        # S -> ... . E ... <==> Seeing E would cause a transition to another state
        # S -> ... . '+' ... <==> Seeing '+' would cause a transition to another state
        # ----------------------------------------------------------------------------
        atomic_pattern_after_dot = item.rule.pattern[item.dot]

        # If state to transition is not created yet, create an empty state for it.
        if atomic_pattern_after_dot is not in transitions:
            # Create an empty state to transition to
            state_to_process.transitions[atomic_pattern_after_dot] = next_empty_state()

        # Setup the kernel of the state to transition
        state_to_transition = state_to_process.transitions[atomic_pattern_after_dot]
        state_to_transition.items.push(item.shift_dot_to_right())

    # Add state to process to processed states, as we're done with it
    processed_states.push(state_to_process)

This is done in src/automaton.rs.

The LR(1) automaton of the example grammar:

+-------+------------------+-----------------+--------------+
| State |      Items       |   Lookaheads    | Transitions  |
+-------+------------------+-----------------+--------------+
| 0     |  E -> . E '+' F  | { $, '+' }      |  E   ->  1   |
|       |  E -> . F        | { $, '+' }      |  F   ->  2   |
|       |  F -> . F '*' T  | { $, '+', '*' } |  T   ->  3   |
|       |  F -> . T        | { $, '+', '*' } |  %b  ->  4   |
|       |  T -> . %b       | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 1     |  E -> E . '+' F  | { $, '+' }      |  '+'  ->  7  |
+-------+------------------+-----------------+--------------+
| 2     |  E -> F .        | { $, '+' }      |  '*'  ->  5  |
|       |  F -> F . '*' T  | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 3     |  F -> T .        | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 4     |  T -> %b .       | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 5     |  F -> F '*' . T  | { $, '+', '*' } |  %b  ->  4   |
|       |  T -> . %b       | { $, '+', '*' } |  T   ->  6   |
+-------+------------------+-----------------+--------------+
| 6     |  F -> F '*' T .  | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 7     |  E -> E '+' . F  | { $, '+' }      |  T   ->  3   |
|       |  F -> . F '*' T  | { $, '+', '*' } |  %b  ->  4   |
|       |  F -> . T        | { $, '+', '*' } |  F   ->  8   |
|       |  T -> . %b       | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+
| 8     |  E -> E '+' F .  | { $, '+' }      |  '*'  ->  5  |
|       |  F -> F . '*' T  | { $, '+', '*' } |              |
+-------+------------------+-----------------+--------------+