SLR(1) and LALR(1) parsing for unrestricted grammars (Q1097044)

The paper extends the SLR(1) and LALR(1) methods of deterministic parsing to unrestricted grammars (Chomsky type 0 grammars). In this aim, SLR(1) and LALR(1) phrase structure grammars are defined and corresponding deterministic two-pushdown automata are introduced in a similar manner with the context-free grammars case. Unfortunately, there is no algorithm which produces the SLR(1) or LALR(1) parse table for a given unrestricted grammar. However, the author presents a technique for parse table constructing. It can be applied in many cases as the chosen examples for several well-known non context-free languages show. The method could be also useful for converting LALR(k) grammars to equivalent unrestricted SLR(1) or LALR(1) grammars which could then be parsed efficiently.