The IELR(1) algorithm for generating minimal LR(1) parser tables for non-LR(1) grammars with conflict resolution

There has been a recent effort in the literature to reconsider grammar-dependent software development from an engineering point of view. As part of that effort, we examine a deficiency in the state of the art of practical LR parser table generation. Specifically, LALR sometimes generates parser tables that do not accept the full language that the grammar developer expects, but canonical LR is too inefficient to be practical particularly during grammar development. In response, many researchers have attempted to develop minimal LR parser table generation algorithms. In this paper, we demonstrate that a well known algorithm described by David Pager and implemented in Menhir, the most robust minimal LR(1) implementation we have discovered, does not always achieve the full power of canonical LR(1) when the given grammar is non-LR(1) coupled with a specification for resolving conflicts. We also detail an original minimal LR(1) algorithm, IELR(1) (Inadequacy Elimination LR(1)), which we have implemented as an extension of GNU Bison and which does not exhibit this deficiency. Using our implementation, we demonstrate the relevance of this deficiency for several real-world parser specifications, and we demonstrate the feasibility of IELR(1). Finally, we demonstrate that, if canonical LR(1) were employed instead, grammar development would be severely impeded regardless of the power of the computer hardware.