An efficient recognizer for the Boolean closure of context-free languages (Q802880)

This paper presents a sub-exponential recognizer for a class of formal languages that are not contextfree. It is based on Earley's algorithm that requires cubic time and works for unrestricted contextfree grammars. The main idea is to extend contextfree grammars by allowing complementation and intersection operations on the right-hand side of the production. This means that, at a given position, a string is required that cannot be derived from a nonterminal A or that must be derivable from symbol A as well as from symbol B. This class of grammars generates the Boolean closure of contextfree languages. The parsing algorithm is an intuitive extension of Earley's. E.g., a complete step can be applied if the point is in front of an intersection operation and there are completed productions for both symbols. The formal description of the algorithm uses some operations on sets of parsing predicates and requires a lengthy list of definitions. The correctness is proved inductively. An easy understanding of the paper is possible if the reader is familiar with Earley's algorithm and starts with Fig. 3c.