Deterministic grammars and grammar morphisms

DOI10.1007/BF00288470MaRDI QIDQ1080666zbMATH OpenOpenAlexFDO

Authors Johannes Reichardt

Publication date 1986

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf00288470

zbMATH Keywords

abstract parsing propertycategorical limitdeterministic bottom-up parse stepgrammar transformationhierarchy of deterministic grammar classesinvariance problem of a given parsing propertylanguage preserving grammar morphisms

Mathematics Subject Classification ID

Special categories (18B99) Theory of compilers and interpreters (68N20) Formal languages and automata (68Q45)

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.

Recommendations

• scientific article; zbMATH DE number 3846897
• Properties of deterministic top down grammars
• Top-Down Deterministic Parsing of Languages Generated by CD Grammar Systems
• scientific article; zbMATH DE number 3843162
• A hierarchy of uniquely parsable grammar classes and deterministic acceptors

Cites work

• A Formalization of Transition Diagram Systems
• Context-free grammars: covers, normal forms, and parsing
• scientific article; zbMATH DE number 4005643 (Why is no real title available?)
• scientific article; zbMATH DE number 3664399 (Why is no real title available?)
• scientific article; zbMATH DE number 3722135 (Why is no real title available?)
• scientific article; zbMATH DE number 3596212 (Why is no real title available?)
• scientific article; zbMATH DE number 3282607 (Why is no real title available?)
• Noncanonical Extensions of Bottom-Up Parsing Techniques
• On the Covering and Reduction Problems for Context-Free Grammars
• On the translation of languages from left to right
• Some Preservation Properties of Normal Form Grammars

Cited in

(12)

• Decidability problems in grammar systems
• A hierarchy of uniquely parsable grammar classes and deterministic acceptors
• Morphological grammars
• scientific article; zbMATH DE number 3846897 (Why is no real title available?)
• Grammar Analysis and Parsing by Abstract Interpretation
• scientific article; zbMATH DE number 1836407 (Why is no real title available?)
• scientific article; zbMATH DE number 1390059 (Why is no real title available?)
• Transcendental syntax I: deterministic case
• scientific article; zbMATH DE number 5199133 (Why is no real title available?)
• Linguistic invariants and language variation
• scientific article; zbMATH DE number 6606360 (Why is no real title available?)
• Grammar semantics, analysis and parsing by abstract interpretation

This page was built for publication: Deterministic grammars and grammar morphisms

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