  Parsing is a fundamental building block in modern compilers, and for
industrial programming languages, it is a surprisingly involved task. There are
known approaches to generate parsers automatically, but the prevailing
consensus is that automatic parser generation is not practical for real
programming languages: LR/LALR parsers are considered to be far too restrictive
in the grammars they support, and LR parsers are often considered too
inefficient in practice. As a result, virtually all modern languages use
recursive-descent parsers written by hand, a lengthy and error-prone process
that dramatically increases the barrier to new programming language
development.
  In this work we demonstrate that, contrary to the prevailing consensus, we
can have the best of both worlds: for a very general, practical class of
grammars -- a strict superset of Knuth's canonical LR -- we can generate
parsers automatically, and the resulting parser code, as well as the generation
procedure itself, is highly efficient. This advance relies on several new
ideas, including novel automata optimization procedures; a new grammar
transformation ("CPS"); per-symbol attributes; recursive-descent actions; and
an extension of canonical LR parsing, which we refer to as XLR, which endows
shift/reduce parsers with the power of bounded nondeterministic choice.
  With these ingredients, we can automatically generate efficient parsers for
virtually all programming languages that are intuitively easy to parse -- a
claim we support experimentally, by implementing the new algorithms in a new
software tool called langcc, and running them on syntax specifications for
Golang 1.17.8 and Python 3.9.12. The tool handles both languages automatically,
and the generated code, when run on standard codebases, is 1.2x faster than the
corresponding hand-written parser for Golang, and 4.3x faster than the CPython
parser, respectively.
