Transforming LR( <i>k</i> ) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars

Abstract

A method is presented for directly transforming an arbitrary LR( k ) grammar to an equivalent LR(1) grammar. It is further shown that the method transforms an arbitrary prefix-free LR( k ) grammar to an equivalent LR(0) grammar. It is argued that the method is efficient and offers some advantages over traditional “look-ahead” parsing methods. Finally, it is demonstrated that the method can be used to transform an LR(1) grammar to an equivalent SLR(1) grammar, which in turn can be easily transformed to an equivalent (1, 1) bounded right-context grammar.