On LR(k)-parsers of polynomial size

Norbert Blum

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)$.…