Implementation of Deremer's SLR(1) parser.
Lih-Ling Tzuu · 1984
IMPLEMENTATION OF DEREMER'S SLR(1) PARSER by Lih-ling Tzuu A class of context-free grammars, called the simple LR(K) or slr(K) grammar, defined by Franklin L. DeRemer is implemented in this paper. It works on any cycle-free SLR(K) grammar,, thus requiring no other initial transformation of the grammar. Some background on the theory of context-free grammar is given and a detail analysis of the SLR(K) parsing method is also shown. Logically, it ^consists of three parts, namely, the LR(0) sets of items, the set of parse tables and the driver poutine (or simply the parser). The item sets are constructed utilizing a doubly linkedlist structure. For the purpose of direct access to next state, the linked list is arranged into a semi-network linkage. The set of parse tables derived from sets of items is presented as an upper triangular (states) x (grammar symbols) matrix. Each table is a pair of functions , where f is the action part and g is the goto part. The set of tables provides the information for the parser as it generates the rightmost•parse of an input string with respect to the given grammar.