An efficient recognizer for the Boolean closure of context-free languages (Q802880): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An efficient context-free parsing algorithm / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An Improved Context-Free Recognizer / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198075 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5536277 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5678435 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: General context-free recognition in less than cubic time / rank | |||
Normal rank |
Latest revision as of 15:54, 21 June 2024
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
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