DERIVATION TREES FOR CONTEXT-SENSITIVE GRAMMARS

One of the main reasons that context-free grammars are widely used is the fact that the concept of derivation trees fits to them very well. The left-most derivations play important role both in theory and practice. Unfortunately with left-most derivations only context-free languages can be derived even if the rules of the grammar are not context-free. In this paper we investigate derivation trees for context-sensitive grammars based on Penttonen's one-sided normal form. The concept of the presented derivation graphs are a kind of extension of the well-known context-free derivation-trees. Moreover it allows to define left-most derivations in context-sensitive grammars without loosing the efficiency of the derivations. These left-most derivations are not derivations in the usual sentential form sense. They are the generalizations of the classical (context-free) left-most derivations, in the way of constructing a derivation tree. Some examples and a new type of ambiguity are also shown.