The LR(0) parser we are going to create will be defined by the following two functions:

• $Next(\rho ,\mathrm{{\rm T}})$ which returns the next parser state to move to from the state $\rho$ given that the next token processed is $\mathrm{{\rm T}}$.
• $Reduc{e}_0(\rho )$ which returns a set of reductions to perform in a given state $\rho$.

For example consider the following grammar and corresponding $Next$ and $Reduc{e}_0$ values:

0. S -> E

1. E -> E "*" D
2. E -> E "+" D
3. E -> D

4. D -> "0"
5. D -> "1"

The parser makes use of this table through the following algorithm:

stack = [0]
while true
  state = stack[-1]
  if Reduce0(state)
    apply_reduction(Reduce0(state), stack)

    token = stack[-1]
    state = stack[-2]
    stack.push(Next(state, token))
  else
    # This is the "shift" case

    token = lexer.next

    if Next(state, token)
      if token == "$"
        # If the token to be shifted is the EOF token we stop now.
        #
        # This is preferred over detecting when production 0 is
        # reduced as we don't usually want the start token in the
        # output.
        break
      else
        stack.push(token)
        stack.push(Next(state, token))
      end
    else
      raise "parse error: invalid token"
    end
  end
end

With apply_reduction being the following:

def apply_reduction(reduction, stack)
  # Where the length of a reduction is the number of symbols on its
  # right hand side
  reduction_length = REDUCTION_LENGTHS[reduction]

  if reduction_length > 0
    popped_values = stack.pop(2 * reduction_length - 1)
  else
    popped_values = []
  end

  # Where make_non_terminal is assumed to create a token whose type
  # corresponds to the left hand side of the specified reduction.
  #
  # The popped values are passed in assuming that the ones
  # corresponding to tokens get saved into either the returned token
  # or some separate structure for keeping track of them.
  stack.push(make_non_terminal(reduction, popped_values))
end

Along with the $Next$ and $Reduc{e}_0$ values specified before we also need to identify what the parser states actually are.

Let us define a parser state as simply being a natural number which identifies it. Then we can define a bijective function from state to parse table, meaning each state corresponds to exactly one parse table.

Each parse table is a subset of the possible items for the parser. A LR(0) parser item is a pair $(\rho ,\gamma )$ where $\rho$ is the number of a production and $\gamma$ is an index into the right hand side of that production.

To make things easier to follow items are usually represented as the production written out with a . at the desired index and surrounded with square brackets.

A few examples from Grammar 3:

(1, 0) is
[E -> . E "*" D]

(2, 2) is
[E -> E "+" . D]

(5, 1) is
[D -> "1" .]

To avoid having to actually work with pairs in our algorithms we will use a convention of assigning an id to each item as follows.

i = 0
@item_ids = {}
@initial_items = {}
@productions.each do |production|
  @initial_items[production.id] = i

  # for each index from 0 to production.length - 1
  production.length.times do |index|
    @item_ids[[production.id, index]] = i
    i += 1
  end
end

This gives us a simple representation of each item which behaves well for set operations, but which we can easily use to associate additional data with each item by simply making an array of length equal to the number of items.

Similarly we will assign sequential ids to each token, first to each terminal then to each non-terminal (so that we can later tell them apart by checking if the id is less than the number of terminals).

To determine the states and parse tables we make use of two functions

• $Closure$ which takes a set of items and returns the set of all items that must be a part of the same set as the input
• $Successors$ which takes a set of items and produces a set of sets of items where each set contains the items that result from shifting a different symbol.

$Closure$ is defined recursively as

$Successors$ is defined as

Where $Nucleus$ is a helper function which produces the set of shifted items where the token shifted is some $\mathrm{{\rm T}}$

To compute these things in our code we are going to to make use of our item ids from earlier to create a helpful array called @items.

@items will contain, for each item id, the id of the next token in that production, when it exists. The last item for each production has no next token so instead in those locations we will store a non token value to identify them later. The non token value we use is -production_id.

def successors(item_set)
  shifted_items = item_set.select do |item|
    # For each item that isn't the last item in its production.
    @items[item] > 0
  end.map do |item|
    # Generate a shifted item
    item + 1
  end

  shifted_items.group_by do |item|
    # Now we group the shifted items we generated based on the
    # id of the token that was shifted.
    @items[item - 1]

    # Then this converts the lists of grouped items into sets
  end.transform_values do |array|
    array.to_set()
  end.sort_by do |token, _|
    token
  end
end

def closure(item_set)
  result = item_set.dup
  queue = item_set.to_a

  until queue.empty?
    i = queue.shift

    token = @items[i]

    # If the next token for the current item is a non-terminal
    if token > @terminals_count
      # Where @productions_for is assumed to map from token ids to
      # the set of production ids which have that token as their
      # left hand side.
      token_items = @productions_for[token].map do |production|
        @initial_items[production]
      end.to_set

      new_items = token_items - result

      queue += new_items.to_a
      result += new_items
    end
  end

  result
end

Finally we can put these tools together to compute the LR(0) parse tables and their associated $Next$ and $Reduc{e}_0$ values.

The following code populates @table_states with a mapping from item set to state id. The inverse mapping is available as @table_states.inverted.

def build_table_states!
  # BiHash is a class I wrote that defines a bidirectional
  # hashmap, such that you can access it in the opposite direction
  # through the `inverted` method.
  #
  # This keeps the implementation a bit shorter, but you will
  # likely want to just maintain both maps in sync when doing this
  # yourself.
  #
  # There are many quirks to such a data-structure and there is
  # thus a good reason it isn't in the standard library for any
  # language.
  @table_states = BiHash.new

  # The item set for state 0 is initialized to be the closure of
  # item 0, the start item.
  @table_states[closure(Set[0])] = 0

  # Initialize @next0 to a hash that initializes any missing keys
  # to a new nested hash when you attempt to access them.
  @next0 = Hash.with_default(Hash)

  i = 0
  while i < @table_states.length
    table = @table_states.inverted[i]

    successors(table).each do |token, new_table|
      # Skip generating the table that would shift the eof token,
      # as we accept the input instead of visiting that state.
      if token == 0
        next
      end

      new_table = closure(new_table)

      # The only terribly smart thing we have to do in this whole
      # process is checking to see if the generated item set
      # already exists, and if so simply put in a @next0 entry
      # pointing to it.
      if @table_states.key?(new_table)
        @next0[i][token] = @table_states[new_table]
      else
        id = @table_states.length
        @table_states[new_table] = id
        @next0[i][token] = id
      end
    end

    i += 1
  end

  # Initialize @reduce0 to a hash that initializes any missing
  # keys to an empty set when you attempt to access them.
  @reduce0 = Hash.with_default(Set)

  @table_states.each do |table, i|
    table.each do |item|
      token = @items[item]
      # This is where putting the -production ids in the @items
      # array starts to pay off. We can find all of the items that
      # result in a reduction in a state just by looking for the
      # negative tokens
      if token < 0
        @reduce0[i].add(-token)
      end
    end
  end
end

For grammar 3 the above algorithm produces the following parse tables:

Table 0 {
  [Start -> . E $] (E, 1)
  [E -> . E "*" D] (E, 1)
  [E -> . E "+" D] (E, 1)
  [E -> . D] (D, 2)
  [D -> . "0"] ("0", 3)
  [D -> . "1"] ("1", 4)
}

Table 1 {
  [Start -> E . $] ($, accept)
  [E -> E . "*" D] ("*", 5)
  [E -> E . "+" D] ("+", 6)
}

Table 2 (reduce 3) {
  [E -> D .]
}

Table 3 (reduce 4) {
  [D -> "0" .]
}

Table 4 (reduce 5) {
  [D -> "1" .]
}

Table 5 {
  [E -> E "*" . D] (D, 7)
  [D -> . "0"] ("0", 3)
  [D -> . "1"] ("1", 4)
}

Table 6 {
  [E -> E "+" . D] (D, 8)
  [D -> . "0"] ("0", 3)
  [D -> . "1"] ("1", 4)
}

Table 7 (reduce 1) {
  [E -> E "*" D .]
}

Table 8 (reduce 2) {
  [E -> E "+" D .]
}

The annotations here next to the table numbers denote the values of $Reduc{e}_0$ for a given state. In each table $\sigma$ the pair of values $(\mathrm{{\rm T}},\rho )$ represent the contents of $Next$ such that $Next(\sigma ,\mathrm{{\rm T}})=\rho$.

For the algorithms that follow we are also going to make heavy use of the following graph representation of a parser, where each $\sigma$ is a vertex and $Next$ defines an edge to $\rho$ labelled with $\mathrm{{\rm T}}$.

The above algorithm will generate LR(0) parse tables regardless of whether the language being parsed is actually recognizable by a LR(0) parser.

In those cases the resulting parse table will contain conflicts. Either shift-reduce conflicts, where a state is labelled with both a reduction and shift actions, or reduce-reduce conflicts, where a state has multiple reduce actions.

In both cases the parser is not able to determine what action to take in such states, and so will not function when used in the manner described before. When this happens we say that the parser is ambiguous.

That does imply that in some cases ambiguity can be resolved by producing a different grammar that represents the same language. It is in fact often the case when writing LR parsers that you need to make repeated adjustments to a grammar to reduce ambiguity.

When a language is not in LR(0), we will instead need a more powerful parser.

1. F. DeRemer and T. Pennello, "Efficient Computation of LALR(1) Look-Ahead sets," ACM Transactions on Programming Languages and Systems, vol. 4, no. 4, pp. 615-649, Oct. 1982, doi: https://doi.org/10.1145/69622.357187.