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

From MaRDI portal
Revision as of 11:35, 20 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
An efficient recognizer for the Boolean closure of context-free languages
scientific article

    Statements

    An efficient recognizer for the Boolean closure of context-free languages (English)
    0 references
    0 references
    0 references
    1991
    0 references
    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.
    0 references
    Earley's algorithm
    0 references
    contextfree languages
    0 references

    Identifiers