Boolean grammar

Boolean grammar

Boolean grammars are a class of formal grammars studied in formal language theory. They extend the basic type of grammars, the context-free grammars, with conjunction and negation operations. Besides these explicit operations, Boolean grammars allow implicit disjunction represented by multiple rules for a single nonterminal symbol, which is the only logical connective expressible in context-free grammars. Conjunction and negation can be used, in particular, to specify intersection and complement of languages. An intermediate class of grammars known as conjunctive grammars allows conjunction and disjunction, but not negation.

The rules of a Boolean grammar are of the form

A o alpha_1 wedge ldots wedge alpha_m wedgelnoteta_1 wedge ldots wedge lnoteta_n

where A is a nonterminal, m+n ge 1 and alpha_1, ..., alpha_m, eta_1, ..., eta_n are strings formed of symbols in Sigma and N. Informally, such a rule asserts that every string w over Sigma that satisfies each of the syntactical conditions represented by alpha_1, ..., alpha_m and none of the syntactical conditions represented by eta_1, ..., eta_n therefore satisfies the condition defined by A.

There exist several formal definitions of the language generated by a Boolean grammar. They have one thing in common: if the grammar is represented as a system of language equations with union, intersection, complementation and concatenation, the languages generated by the grammar must be the solution of this system. The semantics differ in details, some define the languages using language equations, some draw upon ideas from the field of logic programming. However, these nontrivial issues of formal definition are mostly irrelevant for practical considerations, and one can construct grammars according to the given informal semantics. The practical properties of the model are similar to those of conjunctive grammars, while the descriptional capabilities are further improved. In particular, some practically useful properties inherited from context-free grammars, such as efficient parsing algorithms, are retained.

External links

*A. Okhotin, " [http://dx.doi.org/10.1016/j.ic.2004.03.006 Boolean grammars] ", Inf. Comput. 194 (2004) 19-48.
* [http://www.tucs.fi/publications/insight.php?id=tOkhotin06a Nine open problems for conjunctive and Boolean grammars]
* [http://users.utu.fi/aleokh/boolean/ Okhotin's page on Boolean grammars]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Scannerless Boolean Parser — Infobox Software name = SBP developer = Adam Megacz operating system = Java Virtual Machine genre = Parser generator license = BSD license website = [http://research.cs.berkeley.edu/project/sbp/] The Scannerless Boolean Parser is a free software… …   Wikipedia

  • Conjunctive grammar — Conjunctive grammars are a class of formal grammars studied in formal language theory. They extend the basic type of grammars, the context free grammars, with a conjunction operation. Besides explicit conjunction, conjunctive grammars allow… …   Wikipedia

  • Adaptive grammar — An adaptive grammar is a formal grammar that explicitly provides mechanisms within the formalism to allow its own production rules to be manipulated. Contents 1 Overview 1.1 Early history 1.2 Collaborative efforts …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • SBP — The initials SBP may represent, among other things:* Sekolah Berasrama Penuh, a school system for excellent students in Malaysia * in medicine, ** Spontaneous bacterial peritonitis ** Systolic blood pressure * the New York Stock Exchange ticker… …   Wikipedia

  • Scannerless parsing — (also called lexerless parsing ) refers to the use of a single formalism to express both the lexical and context free syntax used to parse a language.This parsing strategy is suitable when a clear lexer parser distinction is not required.… …   Wikipedia

  • Comparison of parser generators — This is a list of notable lexer generators and parser generators for various language classes. Contents 1 Regular languages 2 Deterministic context free languages 3 Parsing expression grammars, deterministic boolean grammars …   Wikipedia

  • Syntactic predicate — A syntactic predicate specifies the syntactic validity of applying a production in a formal grammar and is analogous to a semantic predicate that specifies the semantic validity of applying a production. It is a simple and effective means of… …   Wikipedia

  • List of algorithms — The following is a list of the algorithms described in Wikipedia. See also the list of data structures, list of algorithm general topics and list of terms relating to algorithms and data structures.If you intend to describe a new algorithm,… …   Wikipedia

  • Propositional calculus — In mathematical logic, a propositional calculus or logic (also called sentential calculus or sentential logic) is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”