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

DOI10.1016/0304-3975(91)90205-GMaRDI QIDQ802880zbMATH OpenFDO

Authors Stephan Heilbrunner, Lothar Schmitz

Publication date 1991

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(91)90205-G

zbMATH Keywords

contextfree languagesEarley's algorithm

Mathematics Subject Classification ID

Theory of compilers and interpreters (68N20) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Review text

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.

Recommendations

• Developments in Language Theory
• The Boolean closure of linear context-free languages
• Developments in Language Theory
• Boolean grammars
• Recursive descent parsing for Boolean grammars

Cites work

• An efficient context-free parsing algorithm
• An Improved Context-Free Recognizer
• General context-free recognition in less than cubic time
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3251424 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)

Cited in

(7)

• Boolean kernels of context-free languages
• Fast nondeterministic recognition of context-free languages using two queues
• Conjunctive and Boolean grammars: the true general case of the context-free grammars
• Developments in Language Theory
• Bounded fixed-point definability and tabular recognition of languages
• Kernels of context-free languages
• The Boolean closure of linear context-free languages

This page was built for publication: An efficient recognizer for the Boolean closure of context-free languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q802880)