Context-free grammars: Covers, normal forms, and parsing | Zendy

Anton Nijholt | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Context-free grammars: Covers, normal forms, and parsing

Author(s) -

Anton Nijholt

Publication year - 1980

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

DOI - 10.1007/3-540-10245-0

Subject(s) - parsing , rule based machine translation , computer science , context free grammar , natural language processing , parsing expression grammar , context (archaeology) , artificial intelligence , extended affix grammar , programming language , l attributed grammar , geography , archaeology

This monograph develops a theory of grammatical covers, normal forms and parsing. Covers, formally defined in 1969, describe a relation between the sets of parses of two context-free grammars. If this relation exists then in a formal model of parsing it is possible to have, except for the output, for both grammars the same parser. Questions concerning the possibility to cover a certain grammar with grammars that conform to some requirements on the productions or the derivations will be raised and answered. Answers to these cover problems will be obtained by introducing algorithms that describe a transformation of an input grammar into an output grammar which satisfies the requirements. The main emphasis in this monograph is on transformations of context-free grammars to context-free grammars in some normal form. However, not only transformations of this kind will be discussed, but also transformations which yield grammars which have useful parsing properties

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research