GRAMMATICAL CODES OF TREES AND TERMINALLY CODED GRAMMARS

Article type: Research Article

Authors: Ehrenfeucht, Andrzej | Engelfriet, Joost | Pas, Paulien ten | Rozenberg, Grzegorz^;

Affiliations: Department of Computer Science, University of Colorado at Boulder, Boulder, CO 80309, U.S.A. | Department of Computer Science, Leiden University, P.O.Box 9512, 2300 RA Leiden, The Netherlands, [email protected]

Abstract: We introduce terminally coded (TC) grammars, which generalize parenthesis grammars in the sense that from each word ω generated by a TC grammar we can recover the unlabeled tree t underlying its derivation tree(s). More precisely, there is a length-preserving homomorphism that maps ω to an encoding of t. Basic properties of TC grammars are established. For backwards deterministic TC grammars we give a shift-reduce precedence parsing method without look-ahead, which implies that TC languages can be recognized in linear time. The class of TC languages contains all parenthesis languages, and is contained in the classes of simple precedence languages and NTS languages.

DOI: 10.3233/FI-1995-2311

Journal: Fundamenta Informaticae, vol. 23, no. 1, pp. 1-32, 1995