License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08271.6
URN: urn:nbn:de:0030-drops-16527
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1652/
Go to the corresponding Portal

Kountouriotis, Vassilis ; Nomikos, Christos ; Rondogiannis, Panos

On the Semantic Approaches to Boolean Grammars

pdf-format:
08271.KountouriotisVassilis.Paper.1652.pdf (0.2 MB)

Abstract

Boolean grammars extend context-free grammars by allowing conjunction and negation in rule bodies. This new formalism appears to be quite expressive and still efficient from a parsing point of view. Therefore, it seems reasonable to hope that boolean grammars can lead to more expressive tools that can facilitate the compilation process of modern programming languages. One important aspect concerning the theory of boolean grammars is their semantics. More specifically, the existence of negation makes it difficult to define a simple derivation-style semantics (such as for example in the case of context-free grammars). There have already been proposed a number of different semantic approaches in the literature. The purpose of this paper is to present the basic ideas behind each method and identify certain interesting problems that can be the object of further study in this area.

BibTeX - Entry

@InProceedings{kountouriotis_et_al:DagSemProc.08271.6,
  author =	{Kountouriotis, Vassilis and Nomikos, Christos and Rondogiannis, Panos},
  title =	{{On the Semantic Approaches to Boolean Grammars}},
  booktitle =	{Topological and Game-Theoretic Aspects of Infinite Computations},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8271},
  editor =	{Peter Hertling and Victor Selivanov and Wolfgang Thomas and William W. Wadge and Klaus Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1652},
  URN =		{urn:nbn:de:0030-drops-16527},
  doi =		{10.4230/DagSemProc.08271.6},
  annote =	{Keywords: Boolean Grammars, Negation in Formal Grammars, Well-Founded Semantics}
}

Keywords: Boolean Grammars, Negation in Formal Grammars, Well-Founded Semantics
Collection: 08271 - Topological and Game-Theoretic Aspects of Infinite Computations
Issue Date: 2008
Date of publication: 05.11.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI