Deterministic grammars and grammar morphisms
type: Item
instance of: scholarly article
title: Deterministic grammars and grammar morphisms
zbMATH Open document ID: 0599.68058
DOI: 10.1007/BF00288470
author: Johannes Reichardt
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: The paper deals (in a categorical approach) with the invariance problem of a given parsing property with respect to a given grammar transformation. For this purpose, a deterministic bottom-up parse step is characterized as categorical limit, which allows ''both, systematic grammar type definition and largely strategy-independent invariance proofs. The resulting abstract parsing property BU (Bottom Up), compared to the \(LR^ k\)-type, are the invariants studied in this paper.'' Results: a hierarchy of deterministic grammar classes, invariance conditions for transformations (language preserving grammar morphisms) and their inverses, the difference between BU- and \(LR^ k\)-grammars, etc.
reviewed by: Gheorghe Păun
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68N20
Mathematics Subject Classification ID: 18B99
zbMATH DE Number: 3967933
zbMATH Keywords: invariance problem of a given parsing property
zbMATH Keywords: grammar transformation
zbMATH Keywords: deterministic bottom-up parse step
zbMATH Keywords: categorical limit
zbMATH Keywords: abstract parsing property
zbMATH Keywords: hierarchy of deterministic grammar classes
zbMATH Keywords: language preserving grammar morphisms
MaRDI profile type: Publication
cites work: Q4162623
cites work: Some Preservation Properties of Normal Form Grammars
cites work: On the Covering and Reduction Problems for Context-Free Grammars
cites work: Q5569110
cites work: Q3862443
cites work: On the translation of languages from left to right
cites work: A Formalization of Transition Diagram Systems
cites work: Context-free grammars: covers, normal forms, and parsing
cites work: Q3911427
cites work: Q3756543
cites work: Noncanonical Extensions of Bottom-Up Parsing Techniques
full work available at URL: https://doi.org/10.1007/bf00288470
OpenAlex ID: W2043398957
description: scientific article; zbMATH DE number 3967933