Skip to main content

A Short Proof of a Conjecture of DeRemer and Pennello

Thomas J. Sager

PDF DOI 10.1145/5397.30850 dblp BibTeX

Abstract

In this paper we offer a short proof of the DeRemer-Pennello conjecture that if the LR(0) automaton for a grammar G contains a state p and a nonterminal A such that ( p , A ) is a nonterminal transition, ( p , A ) includes + ( p , A ) and Read ( p , A ) is not empty, then grammar G is not LR( k ) for any k .

Related papers

On the (non-) Relationship between SLR(1) and NQLALR(1) Grammars TOPLAS 1988
Unifying view of recent LALR(1) lookahead set algorithms PLDI 1986
Towards Verifying Nonlinear Integer Arithmetic CAV 2017
Efficient Computation of LALR(1) Look-Ahead Sets TOPLAS 1982
Global context recovery: A new strategy for parser recovery from syntax errors PLDI 1979
Formalizing Giles Gardam's Disproof of Kaplansky's Unit Conjecture CPP 2024
A Formal Disproof of Hirsch Conjecture CPP 2023
A Formalized Reduction of Keller's Conjecture CPP 2023