Parsing 3: LALR(1)

A LALR(1) parser refers to a Look-Ahead LR parser(with 1 token of lookahead).

Specifically a LALR(1) parser adds lookahead to a LR(0) parser keeping the same set of underlying states. This grants a substantial portion of the additional recognition power of LR(1).

In addition to the parser states being unchanged, the $N e x t (ρ, Τ)$ function from the LR(0) parser is also used as is, but with $Τ$ now referring to the lookahead token rather than the shift token.

What we need to compute is thus the values of the function $R e d u c e_{1} (ρ, Τ)$ , which are the reductions to perform in a state $ρ$ given that the lookahead token is $Τ$ (where $Τ$ is a terminal).

Thus if we defined $R e d u c e_{1}$ for a LR(0) parser we would do so as follows:

R e d u c e_{1} (ρ, Τ) = R e d u c e_{0} (ρ)

Completely ignoring $Τ$ like this should remind you of how back in the section on parse tables I mentioned the convention of filling in the reduction for every possible token in a row.

Definitions

We compute $R e d u c e_{1}$ through a series of steps which are described by the following equations, such that each step depends on the one below it.

This is going to be a lot all at once so it will likely be more useful as something to come back and refer to rather than an overview of what is to come.

\begin{matrix} R e d u c e_{1} (ρ, Τ) & = {Α \to ω \in ℙ | Τ \in L A (ρ, Α \to ω)} \\ L A (ρ, Α \to ω) & = ⋃_{σ \in 𝕊} {F o l l o w (σ, Α) | (ρ, Α \to ω) 𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌 (σ, Α)} \\ F o l l o w (ρ, Α) & = R e a d (ρ, Α) \cup ⋃_{\begin{matrix} σ \in 𝕊 \\ Β \in ℕ \end{matrix}} {F o l l o w (σ, Β) | (ρ, Α) 𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔 (σ, Β)} \\ R e a d (ρ, Α) & = D R (ρ, Α) \cup ⋃_{\begin{matrix} σ \in 𝕊 \\ Β \in ℕ \end{matrix}} {R e a d (σ, Β) | (ρ, Α) 𝒓 𝒆 𝒂 𝒅 𝒔 (σ, Β)} \\ D R (ρ, Α) & = {Τ \in 𝕋 | ρ \overset{\overset{}{Α}}{\mapsto} σ \overset{\overset{}{Τ}}{\mapsto}} \end{matrix}

To explain all of the new notation introduced above.

$⋃ {\dots}$ is the recursive union of all of the specified sets, which will be explained further as we describe the Digraph algorithm for computing it.

$ρ \overset{\overset{}{Α}}{\mapsto}$ represents the transition from state $ρ$ for the token $Α$ . Such that appearing to the right of the $|$ means that the expression to the left is conditional on the existence of such a transition.

$L A$ is short for Look Ahead.

$D R$ is short for Directly Reads, and it is the set of terminals that can be read directly after a given non-terminal transition.

$(ρ, Α \to ω) 𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌 (σ, Α)$ , $(ρ, Α) 𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔 (σ, Β)$ and $(ρ, Α) 𝒓 𝒆 𝒂 𝒅 𝒔 (σ, Β)$ mean that there exist edges defined by the $𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌$ , $𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔$ and $𝒓 𝒆 𝒂 𝒅 𝒔$ relations respectively.

Here relation refers specifically to such a set of edges between edges (or alternatively a function from pairs to pairs). We will get to explaining these in a moment.

Relations

To compute $L A$ we now need to determine values for the $𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌$ , $𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔$ and $𝒓 𝒆 𝒂 𝒅 𝒔$ relations. Like $D R$ these can be deduced from the LR(0) parser.

We define $𝒓 𝒆 𝒂 𝒅 𝒔$ such that $(ρ, Α) 𝒓 𝒆 𝒂 𝒅 𝒔 (σ, Β)$ if and only if all of the following are true

\begin{matrix} ρ \overset{\overset{}{Α}}{\mapsto} σ \\ σ \overset{\overset{}{Β}}{\mapsto} \\ Β \Rightarrow^{*} ϵ \end{matrix}

Where $Β$ and $Α$ are non-terminals and $ρ$ and $σ$ are states.

The notation $Β \Rightarrow^{*} ϵ$ means that there exists some sequence of productions starting at $ϵ$ and resulting in $Β$ .

This is used in the $R e a d$ function above to define the full list of terminals which can be the next terminal read after a given non-terminal transition.

As for what this looks like we can have a look at the graph generated for the following grammar:

S -> E

E -> F C D E
E -> "e"

F ->
C ->
D ->

Grammar 4

Grammar 4 parser with reads relation

We define $𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔$ such that $(ρ, Α) 𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔 (σ, Β)$ if and only if all of the following are true.

\begin{matrix} σ \overset{\overset{}{β}}{\to} ρ \\ N e x t (ρ, Α) \overset{\overset{}{γ}}{\to} τ \\ γ \Rightarrow^{*} ϵ \\ Β \to β Α γ \in R e d u c e_{0} (τ) \end{matrix}

Where $Β$ and $Α$ are non-terminals; $ρ$ , $σ$ , and $τ$ are states; $β$ is a sequence of tokens; and $γ$ is a sequence of non-terminals.

$σ \overset{\overset{}{β}}{\to} ρ$ means that, given $β$ is some sequence of tokens, if we start at state $σ$ and follow the sequence of transitions labelled by the tokens of $β$ , we arrive at state $ρ$ . Note that if $β = ϵ$ then $σ = ρ$ because traversing a path of length 0 means staying in place.

$γ$ is allowed to be an empty string in the above, in which case $N e x t (ρ, Α) = τ$ .

$R e d u c e_{0}$ is from the associated LR(0) parser.

The $𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔$ relation captures what edges can follow the specified edge after taking into account backtracking from performing a reduction.

Diagramatic view of the relation

The following is an example grammar and parser diagram to illustrate what $𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔$ looks like in practice.

S -> E
E -> "f" F
E -> "e"

F -> "g" G
G -> "h" E

Grammar 5

Grammar 5 parser with includes relation

The $𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌$ relation is a bit different from the others because it does not relate transitions to transitions.

Unfortunately that means it doesn't have such a nice graphical representation to help illustrate it, but computing it will be very similar to computing $𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔$ .

We define $𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌$ such that $(ρ, Α \to ω) 𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌 (σ, Α)$ if and only if all of following are true.

\begin{matrix} σ \overset{\overset{}{ω}}{\to} ρ \\ ρ \overset{\overset{}{Α}}{\mapsto} \end{matrix}

Where $Α$ is a non-terminal; $ρ$ and $σ$ are states; and $ω$ is a sequence of tokens.

The Digraph Algorithm

To compute $R e a d$ and $F o l l o w$ from their respective relations we need to make use of a graph algorithm referred to as Digraph.

The way these two functions are defined, each strongly connected component of the relation graph converges to the same value for each vertex in the component, then the other components have dependencies on that value as if the whole component was a single vertex.

In a directed graph a node's strongly connected component, or SCC, is composed of every other reachable node which can also reach the starting node.

Graph where each colour represents a different SCC

The Digraph algorithm is a modified SCC traversal algorithm which computes a specific form of graph function as it does so. Namely one in the following form:

Λ (ρ, Α) = λ (ρ, Α) \cup ⋃ {Λ (σ, Β) | (ρ, Α) Ξ (σ, Β)}

Where $Λ$ is what we are trying to compute, $λ$ is some function we know how to compute without the use of $Λ$ , and $Ξ$ is a relation.

# &f means that the argument is passed using the ruby block syntax
# i.e. {}
# For now this can be mostly ignored as we use it as if it was
# just another hashmap from edges to some value.
#
# To facilitate this ruby allows you to pass in a hash as a block
# argument using the & operator, and you invoke it using [] rather
# than ().
def digraph(relation, edges, &f)
  stack = []
  path = []
  state = {}
  result = {}

  edges.each do |starting_point|
    # The outer loop starts an iteration with the next unvisited
    # edge after the previous starting point has traversed all
    # reachable nodes.
    unless state.key?(starting_point)
      stack.push(starting_point)
      state[starting_point] = 0
    end

    until stack.empty?
      edge = stack.pop()

      if state[edge] == 0
        # Each edge is queued for processing exactly twice. Once
        # when traversing downwards in this branch, doing the
        # initial setup, then again in the other branch when
        # ascending back up to propagate the computed values
        # across the component.
        #
        # Thus the weird step of queueing the same element again
        # immediately after popping it.
        stack.push(edge)
        path.push(edge)

        state[edge] = path.length
        result[edge] = f[edge]

        (relation[edge]).each do |other|
          unless state.key?(other)
            state[other] = 0
            stack.push(other)
          end
        end
      else
        (relation[edge]).each do |other|
          unless state[other] == 0
            state[edge] = [state[edge], state[other]].min
            result[edge] = result[edge] + result[other]
          end
        end

        # Given how state[edge] is assigned to the minimum of the
        # the current node and its neighbours above, this check
        # should only be true for the first node visited in each
        # SCC.
        if path[state[edge] - 1] == edge
          while true
            popped = path.pop()
            # The state gets set to infinity here so that the edge
            # is never considered for being a part of any other
            # component later. Otherwise the trick with setting
            # the minimum value from neighbours wouldn't work
            # properly.
            state[popped] = Float::INFINITY

            if popped == edge
              break
            else
              result[popped] = result[edge]
            end
          end
        end
      end
    end
  end

  result
end

lib/lr_examples/digraph.rb#L11

The original formulation of this algorithm is considerably simpler but accomplishes that with an inner recursive function. I've unwound it here as that is generally the desired form and the transformation is non-trivial.

Computing LA

The steps of the algorithm are as follows:

Compute nullable non-terminals from the grammar
Compute $D R$ for each transition from the LR(0) parser
Compute the $𝒓 𝒆 𝒂 𝒅 𝒔$ from the LR(0) parser
Apply Digraph to $𝒓 𝒆 𝒂 𝒅 𝒔$ and $D R$ to compute $R e a d$
Compute $𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔$ and $𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌$ from the LR(0) parser
Apply Digraph to $𝒊 𝒏 𝒄 𝒍 𝒖 𝒅 𝒆 𝒔$ and $R e a d$ to compute $F o l l o w$
Union all of the follow sets for each reduction as defined by $𝒍 𝒐 𝒐 𝒌 𝒃 𝒂 𝒄 𝒌$ to compute $L A$

I will include explanations of some of the less obvious elements of the above however, rather than post the whole implementation with little discussion, I will direct you to the full example source in lalr.rb for all of the remaining details.

Nullable Non-terminals

The process of computing the nullable non-terminals is obvious, but non-trivial. Here is an example of an algorithm to do so making use of something very similar to the digraph algorithm to recursively traverse the tree.

There are certainly some clever tricks that can be used to cut this down.

def nullable_tokens
  nullable = Set.new

  # The set of non_terminals on the right hand side of each
  # production. As the algorithm proceeds we will prune the
  # nullable tokens as we find them until it the set is empty at
  # which point we know the production is nullable.
  production_dependencies = Hash.new { |h, k| h[k] = Set.new }

  # This is the inverse mapping for the initial value of
  # production_dependencies
  has_token = Hash.new { |h, k| h[k] = Set.new }

  @production_tokens.each do |production, left|
    tokens = production_items(production).map do |item|
      @items[item]
    end.to_set

    if tokens.empty?
      nullable.add(left)
    else
      if (tokens & terminals).empty?
        production_dependencies[production] = tokens

        tokens.each do |token|
          has_token[token].add(production)
        end
      end
    end
  end

  queue = nullable.to_a

  # For each nullable token there must exist a parse tree with
  # that token at the root such that every node in the tree is
  # also a nullable token.
  #
  # The implication of that is that we can enumerate all such
  # tokens by iteratively computing all of the tokens that can
  # be generated with a tree of each depth. That is accomplished
  # here by processing them in FIFO order as we find them.
  until queue.empty?
    token = queue.shift()

    (has_token[token]).each do |production|
      left_token = @production_tokens[production]

      unless nullable.include?(left_token)
        production_dependencies[production].delete(token)

        if production_dependencies[production].empty?
          nullable.add(left_token)
          queue.push(left_token)
        end
      end
    end
  end

  nullable
end

lib/lr_examples/lr0.rb#L87

includes and lookback

# The lookback and includes relations can be computed efficiently
# at the same time because they both involve the same traversal of
# paths defined by the tokens in some production.
def compute_path_relations
  @lookback_relation = Hash.with_default(Set)
  @includes_relation = Hash.with_default(Set)

  non_terminal_transitions.each do |edge, _|
    (productions_for[edge.label]).each do |production|
      tokens = tokens_for(production)
      state = edge.from
      included = Set.new

      tokens.each do |token|
        next_edge = Edge[state, token]
        state = transitions[next_edge]
        if state.nil?
          # if we don't find a transition for a given token along
          # the path described by the production, then state will
          # be nil here and that value will be available outside
          # the loop as a flag indicating whether the path was
          # found.
          break
        end

        # If we find a path from the initial state, then the
        # transitions which include the start state are those for
        # the nullable non-terminals at the end of the path, and
        # at most one non-nullable non-terminal that immediately
        # proceeds those.
        if non_terminals.include?(token)
          unless nullable_tokens.include?(token)
            included.clear
          end

          included.add(next_edge)
        else
          included.clear
        end
      end

      unless state.nil?
        @lookback_relation[Edge[state, production]].add(edge)
        included.each do |other_edge|
          @includes_relation[other_edge].add(edge)
        end
      end
    end
  end

  # Here I have marked these sets as immutable because otherwise
  # the Hash.with_default will insert new empty sets when they are
  # used later.
  @includes_relation.freeze
  @lookback_relation.freeze
end

lib/lr_examples/lalr.rb#L161

Using Digraph

Once we've completed generating the relations, computing the $R e a d$ and $F o l l o w$ functions is incredibly straightforward. Literally just filling in the arguments as described e.g.

def read
  digraph(reads_relation, transitions.keys, &direct_reads)
end

lib/lr_examples/lalr.rb#L139

Putting it all Together

Then the final step of computing $L A$ is just merging everything together. In the code here this is combined with the step of generating the value of $R e d u c e_{1}$ .

def reduce
  reduce = Hash.with_default { Hash.with_default(Set) }

  lookahead.each do |edge, tokens|
    # This is syntax to destructure the `edge` variable and assign
    # its two fields to the variables `state` and `production`.
    edge => Edge[state, production]
    if reduce0[state].include?(production)
      tokens.each do |token|
        reduce[state][token].add(production)
      end
    end
  end

  reduce
end

lib/lr_examples/lalr.rb#L238

Ambiguity

Like with a LR(0) parser, a grammar is only considered to be in LALR(1) if the parser generated by the described algorithm is unambiguous.

Thus the output needs to be checked to ensure that each edge only corresponds to a single action, either shift or reduce.

Some additional checks can be performed during the steps which make use of the digraph algorithm to identify grammars which are not LR at all. See [1] for more details.

References

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.

Parsing

Contents