1. A method of performing natural language generation, the method comprising the steps of: selecting a reference grammar; applying an input dependency tree to a tree choosing module for using a stochastic tree model to select syntactic realizations for each node in the derivation tree; producing a word lattice for the stochastically selected syntactic realization comprising all possible word sequences permitted by the input dependency structure, the chosen syntactic realizations, and the reference grammar; and choosing a linear precedence output string of least cost from the word lattice.