#  Briefly on Bottom-up

Paola Quaglia
University of Trento

### Abstract

These short notes are meant as a quick reference for the construction of
SLR(1), of LR(1), and of LALR(1) parsing tables.

1998 ACM Subject Classification F.4.2 Grammars and Other Rewriting Systems

Keywords and phrases SLR(1) grammars; LR(1) grammars; LALR(1) grammars

##  1 Outline

We provide descriptions and references relative to the construction of parsing
tables for SLR(1), for LR(1), and for LALR(1) grammars. The report is
organized as follows. Basic definitions and conventions are collected in Sec.
2. SLR(1), LR(1), and LALR(1) grammars are the subjects of Sec. 4, of Sec. 5,
and of Sec. 6, respectively. For grammars in each of these three classes, the
construction of the relative parsing tables is presented as an instance of a
single schema. The schema itself is described beforehand in Sec. 3.

##  2 Notation and basic definitions

Basic definitions and notational conventions are summerized below.

A context-free grammar is a tuple $\mathcal{G}=(V,T,S,\mathcal{P})$, where the
elements of the tuple represent, respectively, the vocabulary of terminal and
nonterminal symbols, the set of terminal symbols, the start symbol, and the
set of productions. Productions have the shape $A\rightarrow\beta$ where
$A\in{V\setminus{T}}$ is called the _driver_ , and $\beta\in{V^{*}}$ is called
the _body_. The one-step rightmost derivation relation is denoted by
“$\Rightarrow$”, and “$\Rightarrow^{*}$” stands for its reflexive and
transitive closure. A grammar is said _reduced_ if it does not contain any
useless production, namely any production that is never involved in the
derivation of strings of terminals from $S$. We assume grammars be reduced.

The following notational conventions are adopted. The empty string is denoted
by $\epsilon$. Lowercase letters early in the Greek alphabet stand for strings
of grammar symbols ($\alpha,\beta,\ldots\in V^{*}$), lowercase letters early
in the alphabet stand for terminals ($a,b,\ldots\in T$), uppercase letters
early in the alphabet stand for nonterminals ($A,B,\ldots\in(V\setminus T)$),
uppercase letters late in the alphabet stand for either terminals or
nonterminals ($X,Y,\ldots\in V$), and strings of terminals, i.e. elements of
$T^{*}$, are ranged over by $w,w_{0},\ldots$.

For every $\alpha$, ${\rm{first}}(\alpha)$ denotes the set of terminals that
begin strings $w$ such that $\alpha\Rightarrow^{*}w$. Moreover, if
$\alpha\Rightarrow^{*}\epsilon$ then
$\epsilon\in\mbox{${\rm{first}}(\alpha)$}$. For every $A$, ${\rm{follow}}(A)$
denotes the set of terminals that can follow $A$ in a derivation, and is
defined in the usual way.

Given any context-free grammar $\mathcal{G}$, parsing is applied to strings
followed by the symbol $\$\notin V$ used as endmarker. Also, the parsing table
is produced for an enriched version of $\mathcal{G}$, denoted by
$\mathcal{G}^{\prime}=(V^{\prime},T,S^{\prime},\mathcal{P}^{\prime})$. The
enriched grammar $\mathcal{G}^{\prime}$ is obtained from $\mathcal{G}$ by
augmenting $V$ with a fresh nonterminal symbol $S^{\prime}$, and by adding the
production $S^{\prime}\rightarrow S$ to $\mathcal{P}$.

An LR(0)-item of $\mathcal{G}^{\prime}$ is a production of
$\mathcal{G}^{\prime}$ with the distinguished marker “$\cdot$” at some
position of its body, like, e.g., $A\rightarrow\alpha\cdot\beta$. The single
LR(0)-item for a production of the shape $A\rightarrow\epsilon$ takes the form
$A\rightarrow\cdot$. The LR(0)-items ${S^{\prime}\rightarrow\cdot{S}}$ and
${S^{\prime}\rightarrow{S}\cdot}$ are called, respectively, _initial item_ and
_accepting item_. The LR(0)-item ${A\rightarrow\alpha\cdot\beta}$ is called

  * •

_kernel item_ if it is either initial or such that $\alpha\neq\epsilon$,

  * •

_closure item_ if it is not kernel, and

  * •

_reducing item_ if it is not accepting and if $\beta=\epsilon$.

For a set of LR(0)-items $P$, ${\rm{kernel}}(P)$ is the set of the kernel
items in $P$. By definition, the initial item is the single kernel item of
$\mathcal{G}^{\prime}$ with the dot at the leftmost position, and items of the
shape $A\rightarrow\cdot$ are the only non-kernel reducing items.

An LR(1)-item of $\mathcal{G}^{\prime}$ is a pair consisting of an LR(0)-item
of $\mathcal{G}^{\prime}$ and of a subset of $T\cup\mbox{$\\{\$\\}$}$, like,
e.g., $[A\rightarrow\alpha\cdot\beta,\mbox{$\\{a,\$\\}$}]$. The second
component of an LR(1)-item is called lookahead-set and is ranged over by
$\Delta,\Gamma,\ldots$. An LR(1)-item is said _initial_ , _accepting_ ,
_kernel_ , _closure_ or _reducing_ if so is its first component. For a set $P$
of LR(1)-items, ${\rm{prj}}(P)$ is the set of LR(0)-items occurring as first
components of the elements of $P$. Also, function ${\rm{kernel}}(\\_)$ is
overloaded, so that for a set of LR(1)-items $P$, ${\rm{kernel}}(P)$ is the
set of the kernel items in $P$.

##  3 Characteristic automata and parsing tables

Given a context-free grammar $\mathcal{G}$ and a string of terminals $w$, the
aim of bottom-up parsing is to deterministically reconstruct, in reverse order
and while reading $w$ from the left, a rightmost derivation of $w$ if the
string belongs to the language generated by $\mathcal{G}$. If $w$ does not
belong to the language, then parsing returns an error. The computation is
carried over on a stack, and before terminating with success or failure, it
consists in _shift_ steps and in _reduce_ steps. A shift step amounts to
pushing onto the stack the symbol of $w$ that is currently pointed by the
input cursor, and then advancing the cursor. Each reduce step is relative to a
specific production of $\mathcal{G}$. A reduce step under $A\rightarrow\beta$
consists in popping $\beta$ off the stack and then pushing $A$ onto it. Such
reduction is the appropriate kind of move when, for some $\alpha$ and $w_{1}$,
the global content of the stack is $\alpha\beta$ and the rightmost derivation
of the analyzed string $w$ takes the form

$S\Rightarrow^{*}\alpha Aw_{1}\Rightarrow\alpha\beta w_{1}\Rightarrow^{*}w.$
(1)

A seminal result by Knuth [9] is that for reduced grammars the language of the
_characteristic strings_ , i.e. of the strings like $\alpha\beta$ in (1), is a
regular language. By that, a deterministic finite state automaton can be
defined and used as the basis of the finite control of the parsing procedure
[3, 4]. This automaton is referred to as the _characteristic automaton_ , and
is at the basis of the construction of the actual controller of the parsing
algorithm, the so-called _parsing table_.

If $\mathcal{Q}$ is the set of states of the characteristic automaton, then
the parsing table is a matrix $\mathcal{Q}\times(V\cup\mbox{$\\{\$\\}$})$, and
the decision about which step to take next depends on the current state and on
the symbol read from the parsed word. Various parsing techniques use the same
shift/reduce algorithm but are driven by different controllers, which in turn
are built on top of distinct characteristic automata.

States of characteristic automata are sets of items. A state $P$ contains the
item $A\rightarrow\alpha\cdot\beta$ (or an item whose first projection is
$A\rightarrow\alpha\cdot\beta$) if $P$ is the state reached after recognizing
a portion of the parsed word whose suffix corresponds to an expansion of
$\alpha$. Each state of the characteristic automaton is generated from a
kernel set of items by closing it up to include all those items that, w.r.t.
the parsing procedure, represent the same progress as that expressed by the
items in the kernel.

The transition function $\tau$ of the automaton describes the evolution
between configurations. Every state has as many transitions as the number of
distinct symbols that follow the marker “$\cdot$” in its member items. Assume
the parser be in state $P_{n}$, and let $a$ be the current symbol read from
the parsed word. If the entry $(P_{n},a)$ of the parsing table is a shift
move, then the control goes to the state $\tau(P_{n},a)$. If it is a reduction
move under $A\rightarrow\beta$, then the next state is $\tau(P,A)$ where $P$
is the origin of the path spelling $\beta$ and leading to $P_{n}$. Precisely,
suppose that $\beta=Y_{1}\ldots{Y_{n}}$ and let
$P\mathrel{\stackrel{{\scriptstyle Y}}{{\longmapsto}}}P^{\prime}$ denote that
$\tau(P,Y)=P^{\prime}$. Then the state of the parser after the reduction
$A\rightarrow\beta$ in $P_{n}$ is $\tau(P,A)$ where $P$ is such that
$P\mathrel{\stackrel{{\scriptstyle
Y_{1}}}{{\longmapsto}}}P_{1}\mathrel{\stackrel{{\scriptstyle
Y_{2}}}{{\longmapsto}}}\ldots\mathrel{\stackrel{{\scriptstyle
Y_{n}}}{{\longmapsto}}}P_{n}$.

The common features of the various characteristic automata used to construct
bottom-up parsing tables are listed below.

  * •

Each state in $\mathcal{Q}$ is a set of items.

  * •

The initial state contains the initial item.

  * •

The set $\mathcal{F}$ of final states consists of all the states containing at
least one reducing item.

  * •

The vocubularly is the same as the vocabulary of the given grammar, so that
the transition function takes the form $\tau:(\mathcal{Q}\times
V)\rightarrow\mathcal{Q}$.

In the shift/reduce algorithm, the decision about the next step depends on the
current configuration of the parser and on the current input terminal. So, in
order to set up a parsing table, it is also necessary to define, for each
final state $Q$ and for each reducing item in $Q$, which set of terminals
should trigger the relative reduction. This is achieved by providing an actual
definition of the _lookahed function_
$\mathcal{L}\mathcal{A}:\mathcal{F}\times\mathcal{P}\rightarrow\wp(V\cup\mbox{$\\{\$\\}$})$.
For the argument pair $(P,A\rightarrow\beta)$ the lookahead function returns
the set of symbols calling for a reduction after $A\rightarrow\beta$ when the
parser is in state $P$. E.g., referring to (1) and assuming that $P$ is the
state of the parser when $\alpha\beta$ is on the stack,
$\mathcal{L}\mathcal{A}(P,A\rightarrow\beta)$ is expected to contain the first
symbol of $w_{1}$.

Once the underlying characteristic automaton and lookahead function are
defined, the corresponding parsing table is obtained as described below.

######  Definition 3.1.

Let $\mathcal{Q}$, $V$, and $\tau$ be, respectively, the set of states, the
vocabulary, and the transition function of a characteristic automaton. Also,
let $\mathcal{L}\mathcal{A}_{i}$ be an actual instance of the lookahead
function. Then, the parsing table for the pair constisting of the given
characteristic automaton and of the given lookahead function is the matrix
$\mathcal{Q}\times(V\cup\mbox{$\\{\$\\}$})$ obtained by filling in each entry
$(P,Y)$ after the following rules.

  * •

Insert _“Shift $Q$”_ if $Y$ is a terminal and $\tau(P,Y)=Q$.

  * •

Insert _“Reduce $A\rightarrow\beta$”_ if $P$ contains a reducing item for
$A\rightarrow\beta$ and
$Y\in{\mathcal{L}\mathcal{A}}_{i}(P,A\rightarrow\beta)$.

  * •

Set to _“Accept”_ if $P$ contains the accepting item and $Y=\$$.

  * •

Set to _“Error”_ if $Y$ is a terminal or $\$$, and none of the above applies.

  * •

Set to _“Goto $Q$”_ if $Y$ is a nonterminal and $\tau(P,Y)=Q$.

initialize $\mathcal{Q}$ to contain $P_{0}$;

tag $P_{0}$ as unmarked;

while  _there is an unmarked state $P$ in $\mathcal{Q}$ _ do

mark $P$ ;

foreach  _ $Y$ on the right side of the marker in some item of $P$ _ do

Compute in $T\\!mp$ the kernel-set of the $Y$-target of $P$;

if  _ $\mathcal{Q}$ already contains a state $Q$ whose kernel is $T\\!mp$ _
then

Let $Q$ be the $Y$-target of $P$;

else

Add ${\rm{closure}}(\mbox{$T\\!mp$})$ as an unmarked state to the collection
$\mathcal{Q}$;

Let ${\rm{closure}}(\mbox{$T\\!mp$})$ be the $Y$-target of $P$;

($P_{0}$, $T\\!mp$, and ${\rm{closure}}(\\_)$ to be instantiated accordingly)

Algorithm 1 Construction of LR(0)-automaton and of LR(1)-automaton

($P_{0}$, $T\\!mp$, and ${\rm{closure}}(\\_)$ to be instantiated accordingly)

The table might have multiply-defined entries, mentioning either a shift and a
reduce directive (known as a shift/reduce conflict), or multiple reduce
directives for different productions (known as a reduce/reduce conflict). If
so, then the constructed table cannot possibly drive a deterministic parsing
procedure. Consequently, grammar $\mathcal{G}$ is said not to belong to the
class of grammars syntactically analyzable by the methodology (choice of
automaton and of lookahead function) underlying the definition of the parsing
table. Viceversa, if the constructed parsing table contains no conflict, then
$\mathcal{G}$ belongs to the class of grammars parsable by the chosen
methodology.

Below we focus on SLR(1) grammars, LR(1) grammars, and LALR(1) grammars. Seen
as classes of grammars, SLR(1) is strictly contained in LALR(1) which is
strictly contained in LR(1).

Some of the algorithms reported in the following are run on the grammar
$\mathcal{G}_{1}$ below, which is taken from [2]. The language generated by
$\mathcal{G}_{1}$ can be thought of as a language of assignments of r-values
to l-values, where an l-value can denote the content of an r-value.
Interestingly, $\mathcal{G}_{1}$ separates the class SLR(1) from the class
LALR(1).

$\begin{array}[]{llcl}\mathcal{G}_{1}:&S&\rightarrow&L=R\mid R\\\
&L&\rightarrow&*R\mid\mbox{${\rm{id}}$}\\\ &R&\rightarrow&L\end{array}$

##  4 SLR(1) grammars

function  _${\rm{closure}}_{0}(P)$ _

tag every item in $P$ as unmarked ;

while  _there is an unmarked item $I$ in $P$ _ do

mark $I$ ;

if  _ $I$ has the form ${A\rightarrow\alpha\cdot{B}\beta}$ _ then

foreach  _${B\rightarrow\gamma}\in\mathcal{P}^{\prime}$ _ do

if  _ ${B\rightarrow\cdot\gamma}\notin{P}$ _ then

add ${B\rightarrow\cdot\gamma}$ as an unmarked item to $P$ ;

return $P$ ;

Algorithm 2 Computation of ${\rm{closure}}_{0}(P)$

The SLR(1) parsing table for $\mathcal{G}$ is constructed from an automaton,
called LR(0)-automaton, whose states are sets of LR(0)-items. Correspondingly,
function ${\mathcal{L}\mathcal{A}_{i}}$ is instantiated as follows.

> For every final state $P$ of the LR(0)-automaton and for every
> $A\rightarrow\beta\cdot\in P$,
>
> $\mathcal{L}\mathcal{A}_{SLR}(P,A\rightarrow\beta)=\mbox{${\rm{follow}}(A)$}$.

LR(0)-automata are obtained by applying Alg. 1 after:

  * •

using ${\rm{closure}}_{0}(\\_)$ (see Alg. 2) as ${\rm{closure}}(\\_)$
function, and

  * •

taking
$P_{0}=\mbox{${\rm{closure}}_{0}(\mbox{$\\{S^{\prime}\rightarrow\cdot{S}\\}$})$}$,
and

  * •

taking
$\mbox{$T\\!mp$}=\mbox{$\\{{A\rightarrow\alpha{Y}\cdot\beta}\mid{A\rightarrow\alpha\cdot{Y}\beta}\in{P}\mbox{
for some }A,\alpha,\mbox{ and }\beta\\}$}$.

The intuition behind the definition of ${\rm{closure}}_{0}(\\_)$ is that, if
the parsing procedure progressed as encoded by
${A\rightarrow\alpha\cdot{B}\beta}$, and if
${B\rightarrow\gamma}\in\mathcal{P}^{\prime}$, then the coming input can be an
expansion of $\gamma$ followed by an expansion of $\beta$. In fact,
${\rm{closure}}_{0}(P)$ is defined as the smallest set of items that satisfies
the following equation:

>
> $\mbox{${\rm{closure}}_{0}(P)$}=P\mathrel{\cup}\mbox{$\\{{B\rightarrow\cdot\gamma}\mbox{
> such that
> }{A\rightarrow\alpha\cdot{B}\beta}\in\mbox{${\rm{closure}}_{0}(P)$}\mbox{
> and }{B\rightarrow\gamma}\in{\mathcal{P}^{\prime}}\\}$}.$

As an example of application of Alg. 2, the items belonging to
${\rm{closure}}_{0}(\mbox{$\\{S^{\prime}\rightarrow\cdot{S}\\}$})$ for
$\mathcal{G}_{1}$ are shown below.

$\begin{array}[]{l@{\hspace{2ex}}l}\mbox{${\rm{closure}}_{0}(\mbox{$\\{S^{\prime}\rightarrow\cdot{S}\\}$})$}:\hfil\hskip
8.61108pt&{S^{\prime}\rightarrow\cdot S}\\\ \hfil\hskip
8.61108pt&{S\rightarrow\cdot L=R}\\\ \hfil\hskip 8.61108pt&{S\rightarrow\cdot
R}\\\ \hfil\hskip 8.61108pt&{L\rightarrow\cdot*R}\\\ \hfil\hskip
8.61108pt&{L\rightarrow\cdot\mbox{${\rm{id}}$}}\\\ \hfil\hskip
8.61108pt&{R\rightarrow\cdot L}\end{array}$

The rationale for Alg. 1 is the following.

  * •

Compute the set of states of the automaton by starting from the initial state
$P_{0}$ and incrementally adding the targets, under possible $Y$-transitions,
of states already collected.

  * •

To decide which, if any, is the $Y$-target of a certain state $P$, first
compute in $T\\!mp$ the set of the kernel items of the $Y$-target.

  * •

Compare $T\\!mp$ to the states in the current collection. If, for some
collected $Q$, $T\\!mp$ and $Q$ have the same kernel items, then take $Q$ as
the $Y$-target of $P$. If no match is found for $T\\!mp$, then add
${\rm{closure}}_{0}(\mbox{$T\\!mp$})$ to the current collection of states.

Figure 1:  Layout of the LR(0)-automaton for $\mathcal{G}_{1}$

The layout of the LR(0)-automaton for $\mathcal{G}_{1}$ is reported in Fig. 1.
The accepting item is in state $P_{1}$. The final states of the automaton, and
the reducing items they contain, are listed below.

$\begin{array}[]{l@{\hspace{4ex}}l}\mbox{{\bf State}}\hfil\hskip
17.22217pt&\mbox{{\bf Reducing item}}\\\\[3.01385pt] P_{2}:\hfil\hskip
17.22217pt&{R\rightarrow L\cdot}\\\\[3.01385pt] P_{3}:\hfil\hskip
17.22217pt&{S\rightarrow R\cdot}\\\\[3.01385pt] P_{5}:\hfil\hskip
17.22217pt&{L\rightarrow\mbox{${\rm{id}}$}\cdot}\\\\[3.01385pt]
P_{7}:\hfil\hskip 17.22217pt&{L\rightarrow*R\cdot}\\\\[3.01385pt]
P_{8}:\hfil\hskip 17.22217pt&{R\rightarrow L\cdot}\\\\[3.01385pt]
P_{9}:\hfil\hskip 17.22217pt&{S\rightarrow L=R\cdot}\end{array}$

$\mathcal{G}_{1}$ is not SLR(1). Indeed, the SLR(1) parsing table for
$\mathcal{G}_{1}$ has a shift/reduce conflict at the entry $(P_{2},=)$. This
is due to the fact that $P_{2}$ has an outgoing transition labelled by $=$
(which induces a shift to $P_{6}$), and to the fact that
${=}\in\mbox{${\rm{follow}}(R)$}$ (which induces a reduce after ${R\rightarrow
L}$).

##  5 LR(1) grammars

function  _${\rm{closure}}_{1}(P)$ _

tag every item in $P$ as unmarked ;

while  _there is an unmarked item $I$ in $P$ _ do

mark $I$ ;

if  _ $I$ has the form $[A\rightarrow\alpha\cdot{B}\beta,\Delta]$ _ then

$\Delta_{1}\longleftarrow\bigcup_{d\in\Delta}{\mbox{${\rm{first}}(\beta{d})$}}$
;

foreach  _${B\rightarrow\gamma}\in\mathcal{P}^{\prime}$ _ do

if  _ ${B\rightarrow\cdot\gamma}\notin\mbox{${\rm{prj}}(P)$}$ _ then

add $[B\rightarrow\cdot\gamma,\Delta_{1}]$ as an unmarked item to $P$ ;

else

if  _ $(\mbox{$[B\rightarrow\cdot\gamma,\Gamma]$}\in{P}$ and
$\Delta_{1}\not\subseteq\Gamma)$ _ then

update $[B\rightarrow\cdot\gamma,\Gamma]$ to
$[B\rightarrow\cdot\gamma,\Gamma\cup{\Delta_{1}}]$ in $P$ ;

tag $[B\rightarrow\cdot\gamma,\Gamma\cup{\Delta_{1}}]$ as unmarked ;

return $P$ ;

Algorithm 3 Computation of ${\rm{closure}}_{1}(P)$

The LR(1) parsing table for $\mathcal{G}$ is constructed from an automaton,
called LR(1)-automaton, whose states are sets of LR(1)-items. Correspondingly,
function ${\mathcal{L}\mathcal{A}_{i}}$ is instantiated as follows.

> For every final state $P$ of the LR(1)-automaton and for every
> $\mbox{$[A\rightarrow\beta\cdot,\Delta]$}\in P$,
> ${\mathcal{L}\mathcal{A}_{LR}}(P,A\rightarrow\beta)=\Delta$.

LR(1)-automata are obtained by applying Alg. 1 after:

  * •

using ${\rm{closure}}_{1}(\\_)$ (see Alg. 3) as ${\rm{closure}}(\\_)$
function, and

  * •

taking
$P_{0}=\mbox{${\rm{closure}}_{1}(\mbox{$\\{\mbox{$[S^{\prime}\rightarrow\cdot{S},\mbox{$\\{\$\\}$}]$}\\}$})$}$,
and

  * •

taking
$\mbox{$T\\!mp$}=\mbox{$\\{\mbox{$[A\rightarrow\alpha{Y}\cdot\beta,\Delta]$}\mid\mbox{$[A\rightarrow\alpha\cdot{Y}\beta,\Delta]$}\in{P}\mbox{
for some }A,\alpha,\beta,\mbox{ and }\Delta\\}$}$.

When applied to an item with projection ${A\rightarrow\alpha\cdot{B}\beta}$,
${\rm{closure}}_{1}(\\_)$ refines ${\rm{closure}}_{0}(\\_)$ by propagating the
symbols following $B$ to the closure items whose driver is $B$. By definition,
${\rm{closure}}_{1}(P)$ is the smallest set of items, with smallest lookahead-
sets, that satisfies the following equation:
$\mbox{
}\qquad\mbox{${\rm{closure}}_{1}(P)$}=P\cup\\{\mbox{$[B\rightarrow\cdot\gamma,\Gamma]$}\mbox{
such that }$
$\mbox{
}\qquad\mbox{${\rm{closure}}_{1}(P)$}=P\cup\\{$$\mbox{$[A\rightarrow\alpha\cdot{B}\beta,\Delta]$}\in\mbox{${\rm{closure}}_{1}(P)$}\mbox{
and }{B\rightarrow\gamma}\in{\mathcal{P}^{\prime}}\mbox{ and
}\mbox{${\rm{first}}(\beta\Delta)$}\subseteq\Gamma\\}.$

The computation of
${\rm{closure}}_{1}(\mbox{$\\{\mbox{$[S^{\prime}\rightarrow\cdot{S},\mbox{$\\{\$\\}$}]$}\\}$})$
for $\mathcal{G}_{1}$ is detailed in the following, where we assume that items
are processed in the same order in which they are tagged as unmarked in the
collection under construction.

  1. 1.

First round of while

     * •

$[S^{\prime}\rightarrow\cdot{S},\mbox{$\\{\$\\}$}]$ taken as $I$ in Alg. 3,
marked

     * •

$\Delta_{1}=\mbox{$\\{\$\\}$}$

     * •

$[S\rightarrow\cdot L=R,\mbox{$\\{\$\\}$}]$ added to $P$, unmarked

     * •

$[S\rightarrow\cdot R,\mbox{$\\{\$\\}$}]$ added to $P$, unmarked.

  2. 2.

Next round of while

     * •

$[S\rightarrow\cdot L=R,\mbox{$\\{\$\\}$}]$ taken as $I$, marked

     * •

$\Delta_{1}=\mbox{$\\{=\\}$}$

     * •

$[L\rightarrow\cdot*R,\mbox{$\\{=\\}$}]$ added to $P$, unmarked

     * •

$[L\rightarrow\cdot\mbox{${\rm{id}}$},\mbox{$\\{=\\}$}]$ added to $P$,
unmarked.

  3. 3.

Next round of while

     * •

$[S\rightarrow\cdot R,\mbox{$\\{\$\\}$}]$ taken as $I$, marked

     * •

$\Delta_{1}=\mbox{$\\{\$\\}$}$

     * •

$[R\rightarrow\cdot L,\mbox{$\\{\$\\}$}]$ added to $P$, unmarked.

  4. 4.

Next round of while

     * •

$[L\rightarrow\cdot*R,\mbox{$\\{=\\}$}]$ taken as $I$, marked.

  5. 5.

Next round of while

     * •

$[L\rightarrow\cdot\mbox{${\rm{id}}$},\mbox{$\\{=\\}$}]$ taken as $I$, marked.

  6. 6.

Next round of while

     * •

$[R\rightarrow\cdot L,\mbox{$\\{\$\\}$}]$ taken as $I$, marked

     * •

$\Delta_{1}=\mbox{$\\{\$\\}$}$

     * •

$[L\rightarrow\cdot*R,\mbox{$\\{=\\}$}]$ updated to
$[L\rightarrow\cdot*R,\mbox{$\\{=,\$\\}$}]$, unmarked

     * •

$[L\rightarrow\cdot\mbox{${\rm{id}}$},\mbox{$\\{=\\}$}]$ updated to
$[L\rightarrow\cdot\mbox{${\rm{id}}$},\mbox{$\\{=,\$\\}$}]$, unmarked.

  7. 7.

Next round of while

     * •

$[L\rightarrow\cdot*R,\mbox{$\\{=,\$\\}$}]$ taken as $I$, marked.

  8. 8.

Last round of while

     * •

$[L\rightarrow\cdot\mbox{${\rm{id}}$},\mbox{$\\{=,\$\\}$}]$ taken as $I$,
marked.

Figure 2:  Layout of the LR(1)-automaton for $\mathcal{G}_{1}$

The layout of the LR(1)-automaton for $\mathcal{G}_{1}$ is reported in Fig. 2.
The accepting item is in state $P_{1}$. The final states of the automaton, and
the reducing items they contain, are listed below.

$\begin{array}[]{l@{\hspace{4ex}}l}\mbox{{\bf State}}\hfil\hskip
17.22217pt&\mbox{{\bf Reducing item}}\\\\[3.01385pt] P_{2}:\hfil\hskip
17.22217pt&\mbox{$[R\rightarrow L\cdot,\mbox{$\\{\$\\}$}]$}\\\\[3.01385pt]
P_{3}:\hfil\hskip 17.22217pt&\mbox{$[S\rightarrow
R\cdot,\mbox{$\\{\$\\}$}]$}\\\\[3.01385pt] P_{5}:\hfil\hskip
17.22217pt&\mbox{$[L\rightarrow\mbox{${\rm{id}}$}\cdot,\mbox{$\\{=,\$\\}$}]$}\\\\[3.01385pt]
P_{7}:\hfil\hskip
17.22217pt&\mbox{$[L\rightarrow*R\cdot,\mbox{$\\{=,\$\\}$}]$}\\\\[3.01385pt]
P_{8}:\hfil\hskip 17.22217pt&\mbox{$[R\rightarrow
L\cdot,\mbox{$\\{=,\$\\}$}]$}\\\\[3.01385pt] P_{9}:\hfil\hskip
17.22217pt&\mbox{$[S\rightarrow L=R\cdot,\mbox{$\\{\$\\}$}]$}\\\\[3.01385pt]
P_{10}:\hfil\hskip 17.22217pt&\mbox{$[R\rightarrow
L\cdot,\mbox{$\\{\$\\}$}]$}\\\\[3.01385pt] P_{12}:\hfil\hskip
17.22217pt&\mbox{$[L\rightarrow\mbox{${\rm{id}}$}\cdot,\mbox{$\\{\$\\}$}]$}\\\\[3.01385pt]
P_{13}:\hfil\hskip
17.22217pt&\mbox{$[L\rightarrow*R\cdot,\mbox{$\\{\$\\}$}]$}\end{array}$

##  6 LALR(1) grammars

LALR(1) parsing tables are based on automata whose size is the same as the
size of LR(0)-automata. Various algorithms achieve the same goal.

### From LR(1)-automata

The less efficient algorithm for the construction of LALR(1) parsing tables is
based on the use of _LRm(1)-automata_ (for LR(1)-_merged_ -automata).

Call ${\mathscr{A}}_{m}$ the LRm(1)-automaton for $\mathcal{G}^{\prime}$. The
construction of ${\mathscr{A}}_{m}$ requires, as pre-processing, the
computation of the LR(1)-automaton for $\mathcal{G}^{\prime}$, say
${\mathscr{A}}_{l}$. Given ${\mathscr{A}}_{l}$, the states and the transitions
of ${\mathscr{A}}_{m}$ are defined as follows.

States:

The states of ${\mathscr{A}}_{l}$ are partitioned into classes of states
having the same projection. Each state of ${\mathscr{A}}_{m}$ represents one
of such classes, and is defined as the union of the LR(1)-items in the states
of ${\mathscr{A}}_{l}$ belonging to the corresponding class.

Transitions:

If the state $M$ of ${\mathscr{A}}_{m}$ is such that
$\mbox{${\rm{prj}}(M)$}=\mbox{${\rm{prj}}(L)$}$, where $L$ is a state of
${\mathscr{A}}_{l}$, and if $L$ has a $Y$-transition to $L^{\prime}$, then $M$
has a $Y$-transition to the state $M^{\prime}$ such that
$\mbox{${\rm{prj}}(M^{\prime})$}=\mbox{${\rm{prj}}(L^{\prime})$}$. We observe
here that the transitions of the states of ${\mathscr{A}}_{l}$ only depend on
their projections. Hence, if a state $L$ of ${\mathscr{A}}_{l}$ has a
$Y$-transition to $L^{\prime}$, then all the states in the same class as $L$
have $Y$-transitions to states in the same class as $L^{\prime}$.

The LALR(1) parsing table for $\mathcal{G}$ is constructed from the
LRm(1)-automaton, and instantiating function ${\mathcal{L}\mathcal{A}_{i}}$ as
follows.

> For every final state $P$ of the LRm(1)-automaton and for every
> ${\\{\mbox{$[A\rightarrow\beta\cdot,\Delta_{j}]$}\\}_{j}}\subseteq{P}$,
> ${\mathcal{L}\mathcal{A}_{LRm}}(P,A\rightarrow\beta)=\bigcup_{j}\Delta_{j}$.

### From smaller automata

The algorithm described in Sec. 4.7.5 of the international edition of [1] is
the so-called Yacc algorithm [8]. It uses LR(0)-automata as underlying
characteristic automata for the contruction of LALR(1) parsing tables. The
computation of the lookahead function is then based on a post-processing phase
carried on that automaton. The post-processing phase of the Yacc algorithm
consists in performing closure1-operations that allow the identification of
_generated_ lookaheads. In various passes, the generated lookaheads are then
propagated, along the edges of the LR(0)-automaton, to the appropriate
reducing items.

Bison, a well-known parser generator [6], applies an algorithm designed by
DeRemer and Pennello [5]. Like the Yacc algorithm, the algorithm by DeRemer
and Pennello is organized as a post-processing of LR(0)-automata. In a
nutshell, starting from the state $P$ where the reducing item
${A\rightarrow\beta\cdot}$ is located, the algorithm by DeRemer and Pennello
traverses the automaton to infer which precise subset of the productions of
the grammar should be considered when computing the follow-set of $A$ for the
item ${A\rightarrow\beta\cdot}$ in $P$.

$x_{0}\longleftarrow\mbox{${\rm{newVar}}()$}$;

$V\\!ar\\!s\longleftarrow\mbox{$\\{x_{0}\\}$}$;

$P_{0}\longleftarrow\mbox{${\rm{closure}}_{1}(\mbox{$\\{\mbox{$[S^{\prime}\rightarrow\cdot
S,\mbox{$\\{x_{0}\\}$}]$}\\}$})$}$;

initialize $Eqs$ to contain the equation
$x_{0}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{\$\\}$}$;

initialize $\mathcal{Q}$ to contain $P_{0}$;

tag $P_{0}$ as unmarked;

while  _there is an unmarked state $P$ in $\mathcal{Q}$ _ do

mark $P$ ;

foreach  _grammar symbol $Y$ _ do

/* Compute the kernel-set of the $Y$-target of $P$. */

$\mbox{$T\\!mp$}\longleftarrow\emptyset$;

foreach  _ $[A\rightarrow\alpha\cdot{Y}\beta,\Delta]$ in $P$ _ do

add $[A\rightarrow\alpha{Y}\cdot\beta,\Delta]$ to $T\\!mp$;

if  _$\mbox{$T\\!mp$}\neq\emptyset$ _ then

if
_$\mbox{${\rm{prj}}(\mbox{$T\\!mp$})$}=\mbox{${\rm{prj}}(\mbox{${\rm{kernel}}(Q)$})$}$
for some $Q$ in $\mathcal{Q}$ _ then

/* $Q$ is the $Y$-target of $P$. Refine $Eqs$ to propagate lookaheads from $P$
to $Q$. */

foreach  _
$(\mbox{$[A\rightarrow\alpha{Y}\cdot\beta,\Delta]$}\in\mbox{$T\\!mp$}\mathrel{,}\mbox{$[A\rightarrow\alpha{Y}\cdot\beta,\mbox{$\\{x\\}$}]$}\in\mbox{${\rm{kernel}}(Q)$})$
_ do

update $(\mbox{$x\stackrel{{\scriptstyle.}}{{=}}\Gamma$})$ to
$(\mbox{$x\stackrel{{\scriptstyle.}}{{=}}\Gamma\cup\Delta$})$ in $Eqs$;

$\mbox{$\tau$}(P,Y)\longleftarrow{Q}$;

else

/* Generate the $Y$-target of $P$. */

foreach  _
$\mbox{$[A\rightarrow\alpha{Y}\cdot\beta,\Delta]$}\in\mbox{$T\\!mp$}$ _ do

$x\longleftarrow\mbox{${\rm{newVar}}()$}$;

$V\\!ar\\!s\longleftarrow V\\!ar\\!s\cup\mbox{$\\{x\\}$}$;

enqueue $(\mbox{$x\stackrel{{\scriptstyle.}}{{=}}\Delta$})$ into ${Eqs}$;

replace $[A\rightarrow\alpha{Y}\cdot\beta,\Delta]$ by
$[A\rightarrow\alpha{Y}\cdot\beta,\mbox{$\\{x\\}$}]$ in $T\\!mp$;

$\mbox{$\tau$}(P,Y)\longleftarrow\mbox{${\rm{closure}}_{1}(\mbox{$T\\!mp$})$}$;

add $\mbox{$\tau$}(P,Y)$ as an unmarked state to $\mathcal{Q}$ ;

Algorithm 4 Construction of the symbolic automaton

Below, we describe an algorithm based on the construction of specialized
_symbolic characteristic automata_ [10]. The states of these automata are sets
of _symbolic items_ , which have the same structure as LR(1)-items. The
lookahead-sets of symbolic items, however, can also contain elements from a
set $\,\mathbb{V}$ which is disjoint from $V^{\prime}\cup\mbox{$\\{\$\\}$}$.
Elements of $\,\mathbb{V}$ are called _variables_ and are ranged over by
$x,x^{\prime},\ldots$. In what follows, we use
$\Delta,\Delta^{\prime},\ldots,\Gamma,\Gamma^{\prime},\ldots$ to denote
subsets of $\mbox{$\,\mathbb{V}$}\cup T\cup\mbox{$\\{\$\\}$}$. Also, we let
$\mbox{${\rm{ground}}(\Delta)$}=\Delta\cap(T\cup\mbox{$\\{\$\\}$})$. Moreover,
we assume the existence of a function ${\rm{newVar}}()$ which returns a fresh
symbol of $\,\mathbb{V}$ at any invocation. The definitions of initial,
accepting, kernel, closure, and reducing items are extended to symbolic items
in the natural way. Also, functions ${\rm{prj}}(\\_)$ and ${\rm{kernel}}(\\_)$
are overloaded to be applied to sets of symbolic items.

Variables are used to construct on-the-fly a symbolic version of the
LRm(1)-automaton. In every state $P$ of the symbolic automaton, the lookahead-
set of kernel items is a singleton set containing a distinguished variable,
like, e.g. $[A\rightarrow\alpha{Y}\cdot\beta,\mbox{$\\{x\\}$}]$. On the side,
an equation for $x$ collects all the contributions to the lookahead-set of
${A\rightarrow\alpha{Y}\cdot\beta}$ coming from the items with projection
${A\rightarrow\alpha\cdot{Y}\beta}$ which are located in the states $Q_{i}$
with a $Y$-transition to $P$. When a new state $P$ is generated and added to
the current collection, ${\rm{closure}}_{1}(\\_)$ symbolically propagates to
the closure items the lookaheads encoded by the variables associated with the
kernel items of $P$. When the construction of the symbolic automaton is over,
the associated system of equations over variables is resolved to compute, for
every variable $x$, the subset of $T\cup\mbox{$\\{\$\\}$}$ that is the actual
value of $x$, denoted by $val(x)$. The evaluation of variables, in turn, is
used to actualize lookahead-sets. In particular, function
${\mathcal{L}\mathcal{A}_{i}}$ is instantiated as follows.

> For every final state $P$ of the symbolic automaton and for every
> $\mbox{$[A\rightarrow\beta\cdot,\Delta]$}\in P$,
>
> ${\mathcal{L}\mathcal{A}_{LALR}}(P,A\rightarrow\beta)=\mbox{${\rm{ground}}(\Delta)$}\cup\bigcup_{x\in\Delta}val(x)$.

$\begin{array}[]{ll@{\hspace{14ex}}l}\mbox{{\em State}}&\mbox{{\em Items
(kernel in purple)}}\hfil\hskip 60.27759pt&Eqs\\\\[4.30554pt]
P_{0}:&\color[rgb]{0.4,0,0.4}{\mbox{$[S^{\prime}\rightarrow\cdot
S,\mbox{$\\{x_{0}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{0}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{\$\\}$}$}\\\
&\mbox{$[S\rightarrow\cdot L=R,\mbox{$\\{x_{0}\\}$}]$}\hfil\hskip
60.27759pt\\\ &\mbox{$[S\rightarrow\cdot R,\mbox{$\\{x_{0}\\}$}]$}\hfil\hskip
60.27759pt\\\
&\mbox{$[L\rightarrow\cdot*R,\mbox{$\\{=,x_{0}\\}$}]$}\hfil\hskip
60.27759pt\\\
&\mbox{$[L\rightarrow\cdot\mbox{${\rm{id}}$},\mbox{$\\{=,x_{0}\\}$}]$}\hfil\hskip
60.27759pt\\\ &\mbox{$[R\rightarrow\cdot L,\mbox{$\\{x_{0}\\}$}]$}\hfil\hskip
60.27759pt\\\\[4.30554pt]
P_{1}:&\color[rgb]{0.4,0,0.4}{\mbox{$[S^{\prime}\rightarrow
S\cdot,\mbox{$\\{x_{1}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{1}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{0}\\}$}$}\\\\[4.30554pt]
P_{2}:&\color[rgb]{0.4,0,0.4}{\mbox{$[S\rightarrow
L\cdot=R,\mbox{$\\{x_{2}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{2}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{0}\\}$}$}\\\
&\color[rgb]{0.4,0,0.4}{\mbox{$[R\rightarrow
L\cdot,\mbox{$\\{x_{3}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{3}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{0}\\}$}$}\\\\[4.30554pt]
P_{3}:&\color[rgb]{0.4,0,0.4}{\mbox{$[S\rightarrow
R\cdot,\mbox{$\\{x_{4}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{4}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{0}\\}$}$}\\\\[4.30554pt]
P_{4}:&\color[rgb]{0.4,0,0.4}{\mbox{$[L\rightarrow*\cdot
R,\mbox{$\\{x_{5}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{5}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{=,x_{0}\\}$}\cup\mbox{$\\{x_{5}\\}$}\cup\mbox{$\\{x_{7}\\}$}$}\\\
&\mbox{$[R\rightarrow\cdot L,\mbox{$\\{x_{5}\\}$}]$}\hfil\hskip 60.27759pt\\\
&\mbox{$[L\rightarrow\cdot*R,\mbox{$\\{x_{5}\\}$}]$}\hfil\hskip 60.27759pt\\\
&\mbox{$[L\rightarrow\cdot\mbox{${\rm{id}}$},\mbox{$\\{x_{5}\\}$}]$}\hfil\hskip
60.27759pt\\\\[4.30554pt]
P_{5}:&\color[rgb]{0.4,0,0.4}{\mbox{$[L\rightarrow\mbox{${\rm{id}}$}\cdot,\mbox{$\\{x_{6}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{6}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{=,x_{0}\\}$}\cup\mbox{$\\{x_{5}\\}$}\cup\mbox{$\\{x_{7}\\}$}$}\\\\[4.30554pt]
P_{6}:&\color[rgb]{0.4,0,0.4}{\mbox{$[S\rightarrow L=\cdot
R,\mbox{$\\{x_{7}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{7}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{2}\\}$}$}\\\
&\mbox{$[R\rightarrow\cdot L,\mbox{$\\{x_{7}\\}$}]$}\hfil\hskip 60.27759pt\\\
&\mbox{$[L\rightarrow\cdot*R,\mbox{$\\{x_{7}\\}$}]$}\hfil\hskip 60.27759pt\\\
&\mbox{$[L\rightarrow\cdot\mbox{${\rm{id}}$},\mbox{$\\{x_{7}\\}$}]$}\hfil\hskip
60.27759pt\\\\[4.30554pt]
P_{7}:&\color[rgb]{0.4,0,0.4}{\mbox{$[L\rightarrow*R\cdot,\mbox{$\\{x_{8}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{8}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{5}\\}$}$}\\\\[4.30554pt]
P_{8}:&\color[rgb]{0.4,0,0.4}{\mbox{$[R\rightarrow
L\cdot,\mbox{$\\{x_{9}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{9}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{5}\\}$}\cup\mbox{$\\{x_{7}\\}$}$}\\\\[4.30554pt]
P_{9}:&\color[rgb]{0.4,0,0.4}{\mbox{$[S\rightarrow
L=R\cdot,\mbox{$\\{x_{10}\\}$}]$}}\hfil\hskip
60.27759pt&\mbox{$x_{10}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{7}\\}$}$}\\\\[4.30554pt]
\end{array}$

Figure 3:  Symbolic automaton for $\mathcal{G}_{1}$: content of states, and of
$Eqs$

inizialize $RV\\!ar\\!s$ and $R\\!Eqs$ to $\emptyset$ ;

while  _ $Eqs_{b}$ not empty _ do

$\mbox{$x\stackrel{{\scriptstyle.}}{{=}}\Delta$}\longleftarrow\mbox{${\rm{dequeue}}(Eqs_{b})$}$
;

/* For $j>i$, if $x_{j}\stackrel{{\scriptstyle.}}{{=}}\\{x_{i}\\}$ then
$x_{j}$ is in the same class as $x_{i}$. The same holds of
$x_{j}\stackrel{{\scriptstyle.}}{{=}}\\{x_{i},x_{j}\\}$, i.e. up to self-
reference. */

if  _ $\Delta\setminus\mbox{$\\{x\\}$}=\mbox{$\\{x^{\prime}\\}$}$ _ then

$class(x)\longleftarrow class(x^{\prime})$ ;

else

$class(x)\longleftarrow x$ ;

add ${x}$ to $RV\\!ar\\!s$ ;

/* Clean up the defining equations of the variables in $RV\\!ar\\!s$. Use only
representative variables on right-sides, and remove self-references. */

foreach  _ $x\in RV\\!ar\\!s\mbox{ such that
}\mbox{$x\stackrel{{\scriptstyle.}}{{=}}\Delta$}\in Eqs_{b}$ _ do

update each $x^{\prime}$ in $\Delta$ to $class(x^{\prime})$ ;

add $x\stackrel{{\scriptstyle.}}{{=}}\Delta\setminus\mbox{$\\{x\\}$}$ to
$R\\!Eqs$ ;

Algorithm 5 Reduced system of equations $R\\!Eqs$ for the variables in
$RV\\!ar\\!s$ Figure 4:  Dependency graph for the reduced system of equations
obtained from $Eqs$ in Fig. 3

foreach  _$x$ represented by a vertex of $DG$ _ do

/* Variable to be used as index for strongly connected components (SCC). */

$scc(x)\longleftarrow 0$ ;

foreach  _$x$ in represented by a vertex of $DG$ _ do

if  _$scc(x)=0$ _ then

${\rm{search}}(x)$ ;

where

function  _${\rm{search}}(x)$ _

push $x$ onto stack $S$ ;

$depth\longleftarrow$ number of elements in $S$ ;

$scc(x)\longleftarrow depth$ ;

$val(x)\longleftarrow init(x)$ ;

foreach  _$x^{\prime}$ such that there is an edge in $DG$ from ${x}$ to
${x^{\prime}}$ _ do

if  _$scc(x^{\prime})=0$ _ then

${\rm{search}}(x^{\prime})$

/* When the entry vertex of an SCC is found backwards, all the vertices in the
SCC take the same index as the index of the entry vertex. */

$scc(x)\longleftarrow min(scc(x),scc(x^{\prime}))$ ;

$val(x)\longleftarrow val(x)\cup val(x^{\prime})$ ;

/* The entry vertex of an SCC finds all the vertices of the SCC on top of the
stack (the entry vertex is the deepest), it assigns its value to all the
vertices in the SCC and cleans the stack up. (Note: Any leaf of a tree is an
SCC.) */

if  _ $scc(x)=depth$ _ then

repeat

$scc(top(S))\longleftarrow\infty$ ;

$val(top(S))\longleftarrow val(x)$ ;

until  _ $pop(S)=x$ _;

Algorithm 6 Computation of the values for the variables in the dependency
graph $DG$

The procedure for collecting all the elements needed to set up the LALR(1)
parsing table consists in the following steps.

  1. 1.

Construct the symbolic automaton by applying Alg. 4, and get the set
$V\\!ar\\!s$ of variables generated for the construction, and the list $Eqs$
of equations installed for those variables.

The application of Alg. 4 to $\mathcal{G}_{1}$ results in a symbolic automaton
with the same layout as that of its LR(0)-automaton (Fig. 1). The content of
the states of the symbolic automaton, and the associated system of equations
$Eqs$ are both reported in Fig. 3.

  2. 2.

Set up a graph $DG$ for the computation of the actual values of variables.

$DG$ is the dependency graph of the reachability relation embedded by the
definining equations. Each vertex of $DG$ represents one of the variables
occurring as left-side of an equation. If the equation to be represented for
$x$ is $x\stackrel{{\scriptstyle.}}{{=}}\Delta$, then the vertex for variable
$x$ has an outgoing edge to each of the vertices for the variables in
$\Delta$. Also, the vertex for $x$ is associated with the inital value
$init(x)=\mbox{${\rm{ground}}(\Delta)$}$.

Computational efficiency can be gained by operating on a dependency graph
smaller than that induced by $Eqs$. This can be achieved after the following
observations.

Let $V\\!ar\\!s_{r}\subseteq V\\!ar\\!s$ be the set of variables associated
with reducing items, and let $V\\!ar\\!s_{b}=V\\!ar\\!s\setminus
V\\!ar\\!s_{r}$. By construction, all the variables in $V\\!ar\\!s_{r}$ cannot
propagate any further, and rather act as accumulators. In fact, each of the
variables in $V\\!ar\\!s_{r}$ occurs in $Eqs$ only once, as left-side of its
defining equation. Then, to solve the system of equations, it is sufficient to
compute the values of the variables in $V\\!ar\\!s_{b}$. Once these values are
known, for each $x_{i}\in V\\!ar\\!s_{r}$ such that
$x_{i}\stackrel{{\scriptstyle.}}{{=}}\Delta_{i}$ is in $Eqs$, we can set

$val(x_{i})=\mbox{${\rm{ground}}(\Delta_{i})$}\cup\bigcup_{x\in\Delta_{i}}val(x).$
(2)

The second observation is that the variables in $V\\!ar\\!s_{b}$ can be
partitioned into equivalence classes, so that it is enough to evaluate one
variable per class. Let $Eqs_{b}$ be obtained from $Eqs$ by removing the
equations for the variables in $V\\!ar\\!s_{r}$. To get the partition of the
variables in $V\\!ar\\!s_{b}$, we run Alg. 5 over $Eqs_{b}$. Alg. 5 returns a
reduced system of equations $R\\!Eqs$ which define the variables in
$RV\\!ar\\!s\subseteq V\\!ar\\!s_{b}$. Also, every variable $x\in
V\\!ar\\!s_{b}$ is associated with a class representative, denoted by
$class(x)$.

As for the running example, the set $V\\!ar\\!s_{b}$ for the symbolic
automaton of $\mathcal{G}_{1}$ is given by
$\\{x_{0},x_{1},x_{2},x_{5},x_{7}\\}$. The application of Alg. 5 to the
corresponding set of equations $Eqs_{b}$ results in the reduced system
$R\\!Eqs$ shown below, and the induced dependency graph is drawn in Fig. 4.

$\begin{array}[]{l@{\hspace{7ex}}l@{\hspace{7ex}}l@{\hspace{7ex}}l}Eqs_{b}\hfil\hskip
30.1388pt&class(x)\hfil\hskip 30.1388pt&RV\\!ar\\!s\hfil\hskip
30.1388pt&R\\!Eqs\\\
\mbox{$x_{0}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{\$\\}$}$}\hfil\hskip
30.1388pt&x_{0}\hfil\hskip 30.1388pt&x_{0}\hfil\hskip
30.1388pt&\mbox{$x_{0}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{\$\\}$}$}\\\
\mbox{$x_{1}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{0}\\}$}$}\hfil\hskip
30.1388pt&x_{0}\hfil\hskip 30.1388pt&\hfil\hskip 30.1388pt\\\
\mbox{$x_{2}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{0}\\}$}$}\hfil\hskip
30.1388pt&x_{0}\hfil\hskip 30.1388pt&\hfil\hskip 30.1388pt\\\
\mbox{$x_{5}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{=,x_{0},x_{5},x_{7}\\}$}$}\hfil\hskip
30.1388pt&x_{5}\hfil\hskip 30.1388pt&x_{5}\hfil\hskip
30.1388pt&\mbox{$x_{5}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{=,x_{0}\\}$}$}\\\
\mbox{$x_{7}\stackrel{{\scriptstyle.}}{{=}}\mbox{$\\{x_{2}\\}$}$}\hfil\hskip
30.1388pt&x_{0}\hfil\hskip 30.1388pt&\hfil\hskip 30.1388pt\\\ \end{array}$

  3. 3.

Compute the values of the variables in $RV\\!ar\\!s$.

This is obtained by running Alg. 6 on $DG$. Alg. 6, by DeRemer and Pennello
[5], is an adaptation of a depth-first visit for finding strongly connected
components [11]. In particular, Alg. 6 specializes an algorithm presented in
[7] for the efficient computation of the reflexive and transitive closure of
arbitrary relations. Briefly, the values associated with the farthest nodes
are accumulated with the values of the nodes found along the way back to the
origin of the path. The visit of the graph is organized in such a way that
strongly connected components are recognized on-the-fly, and, as due, each
vertex in the connected component is associated with the same value.

Running Alg. 6 on the graph in Fig. 4, we get $val(x_{0})=\mbox{$\\{\$\\}$}$,
and $val(x_{5})=\mbox{$\\{=,\$\\}$}$.

  4. 4.

Compute the values of the variables in $V\\!ar\\!s\setminus RV\\!ar\\!s$.

First, actualize the values of the variables in $x\in V\\!ar\\!s_{b}\setminus
RV\\!ar\\!s$ using equation (3) below.

$val(x)=val(class(x)).$ (3)

Then compute the values of the variables in $x\in V\\!ar\\!s_{r}$ by using
equation (2).

In the case of the symbolic automaton of $\mathcal{G}_{1}$, given the values
computed for ${x_{0}}$ and for ${x_{5}}$, we get
$val(x_{1})=val(x_{2})=val(x_{3})=val(x_{4})=val(x_{7})=val(x_{10})=\mbox{$\\{\$\\}$}$,
and $val(x_{6})=val(x_{8})=val(x_{9})=\mbox{$\\{=,\$\\}$}$.

## References

  * [1] Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman.  Compilers: Principles, Techniques, and Tools (2nd Edition).  Prentice Hall, 2006.
  * [2] Alfred V. Aho and Jeffrey D. Ullman.  Principles of Compiler Design.  Addison-Wesley, 1977.
  * [3] Frank DeRemer.  Practical Translators for LR(k) Languages. PhD thesis, MIT, Cambridge, Mass., 1969.
  * [4] Frank DeRemer.  Simple LR(k) Grammars.  Commun. ACM, 14(7):453–460, 1971.  URL: http://doi.acm.org/10.1145/362619.362625.
  * [5] Frank DeRemer and Thomas J. Pennello.  Efficient Computation of LALR(1) Look-Ahead Sets.  ACM Trans. Program. Lang. Syst., 4(4):615–649, 1982.  URL: http://doi.acm.org/10.1145/69622.357187.
  * [6] Charles Donnelly and Richard Stallman.  Bison: The Yacc-compatible Parser Generator (Ver. 3.0.4).  2015\.  URL: {http://www.gnu.org/software/bison/manual/bison.pdf}.
  * [7] J. Eve and Reino Kurki-Suonio.  On Computing the Transitive Closure of a Relation.  Acta Inf., 8:303–314, 1977.  URL: http://dx.doi.org/10.1007/BF00271339.
  * [8] Stephen C. Johnson.  Yacc: Yet Another Compiler-Compiler.  Tech. Rep. CSTR 32, Bell Laboratories, Murray Hill, N.J., 1974.  URL: {http://dinosaur.compilertools.net/}.
  * [9] Donald E. Knuth.  On the Translation of Languages from Left to Rigth.  Information and Control, 8(6):607–639, 1965.  URL: http://dx.doi.org/10.1016/S0019-9958(65)90426-2.
  * [10] Paola Quaglia.  Symbolic Lookaheads for Bottom-up Parsing.  In Proc. 41st Int. Symposium on Mathematical Foundations of Computer Science, MFCS 2016, volume 58 of LIPIcs, pages 79:1–79:13, 2016.  URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.79.
  * [11] Robert Endre Tarjan.  Depth-First Search and Linear Graph Algorithms.  SIAM J. Comput., 1(2):146–160, 1972.  URL: http://dx.doi.org/10.1137/0201010.