  Usually, a parser for an $LR(k)$-grammar $G$ is a deterministic pushdown
transducer which produces backwards the unique rightmost derivation for a given
input string $x \in L(G)$. The best known upper bound for the size of such a
parser is $O(2^{|G||\Sigma|^k+k\log |\Sigma| + \log |G|})$ where $|G|$ and
$|\Sigma|$ are the sizes of the grammar $G$ and the terminal alphabet $\Sigma$,
respectively. If we add to a parser the possibility to manipulate a directed
graph of size $O(|G|n)$ where $n$ is the length of the input then we obtain an
extended parser. The graph is used for an efficient parallel simulation of all
potential leftmost derivations of the current right sentential form such that
the unique rightmost derivation of the input can be computed. Given an
arbitrary $LR(k)$-grammar $G$, we show how to construct an extended parser of
$O(|G| + \#LA |N|2^k k \log k)$ size where $|N|$ is the number of nonterminal
symbols and $\#LA$ is the number of relevant lookaheads with respect to the
grammar $G$. As the usual parser, this extended parser uses only tables as data
structure. Using some ingenious data structures and increasing the parsing time
by a small constant factor, the size of the extended parser can be reduced to
$O(|G| + \#LA|N|k^2)$. The parsing time is $O(ld(input) + k|G|n)$ where
$ld(input)$ is the length of the derivation of the input. Moreover, we have
constructed a one pass parser.
