The derivation language of a phrase structure grammar

摘要

This paper studies the problem of representing derivations in general phrasestructuregrammars. By properly sorting the nodes, the syntactical graph of any derivation in a phrase-structure language can be expressed uniquely as a word in a context-sensitive language, just as the derivations in a context-free grammar can be expressed in the prefix form of a derivation tree. The set of all such graph representations is called the “derivation language.” Algorithms are given for obtaining the one-to-one correspondence between the set of syntactical graphs (of a grammar) and the derivation language. In the special case of context-free grammars, the results reduce to well-known properties of context-free derivations.