GRAMMATICAL CODES OF TREES AND TERMINALLY CODED GRAMMARS

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.