Physical Sciences and Mathematics Commons^™

A General Lr(K) Parser Building Algorithm, Thomas Joshua Sager

Mathematics & Statistics ETDs

The problem is to find an efficient algorithm that, given the productions of a context-free grammar G, will discover whether G is LR(k) for given k and if it is build an efficient parser for G . The algorithm is given in Section 8. It is essentially a synthesis of the best parts of Knuth's and DeRemer's algorithms. On simple LR(k) grarranars it yields a result equivalent to DeRemer's algorithm, and like Knuth's algorithm it will work on all LR(k) grammars.