Earley-style parsing for relational grammars
Kent B. Wittenburg · 2003
Predictive, Earley-style parsing for unrestricted relational grammars faces a number of problems not present in a context-free string grammar counterpart. Here a subclass of unrestricted relational grammars called fringe relational grammars is proposed along with an Earley-style recognition algorithm. The grammar makes use of fringe elements (the minimal and maximal elements of partially ordered sets) in defining its productions. The parsing algorithm uses indexing methods based on fringe elements in order to take advantage of equivalence relations on parse table entries, thus avoiding redundant processing.>