1. A computer program product for translating natural language input to a machine-readable format for processing by a knowledge base, the computer program product comprising one or more non-transitory computer-readable media having computer program instructions stored therein, the computer program instructions being configured such that, when executed, the computer program instructions cause one or more computing devices to: receive a text string derived from natural language input; generate an input graph for the text string, the input graph representing a plurality of different subsets of words in the text string; retrieve a template graph representing a plurality of translation templates associated with the knowledge base, each translation template being for translating matching natural language input to the machine-readable format, and each translation template corresponding to at least one of a plurality of terminal nodes in the template graph, wherein each terminal node of the template graph has an associated template priority that is based on the corresponding translation template, and wherein each internal node of the template graph is labeled with an identifier of a highest priority template that can be reached from that point in the template graph; generate an intersection graph from the input graph and the template graph, each node in the intersection graph representing a tuple of corresponding nodes in the input and template graphs; process the intersection graph to identify one or more candidate terminal nodes of the intersection graph, the template priorities associated with the terminal nodes of the template graph causing processing of the intersection graph to proceed preferentially along edges of the intersection graph leading to terminal nodes of the intersection graph that represent terminal nodes of the template graph that correspond to the highest priority templates; generate a score for each terminal node of the template graph that corresponds to one of the candidate terminal nodes of the intersection graph, each score based at least in part on a probability that the text string corresponds to an intended meaning of the natural language input, and a translation template corresponding to the terminal node of the template graph; select a first terminal node of the template graph based on the one or more scores, a first translation template corresponding to the first terminal node of the template graph; translate the text string using the first translation template thereby generating a machine-readable translation that accurately represents a semantic meaning of the natural language input; process the machine-readable translation using structured data to generate a result; generate a natural language response using the result; and present the natural language response to a user on a client device.