1. A computer-implemented method performed by a data processing apparatus, the method comprising: receiving, by a data processing apparatus, lattice parse data describing a lattice parse of a command sentence input at a user device as a voice command input sentence and converted to a plurality of terms, the lattice parse data defining a plurality of N nodes and edges connecting the N nodes, each respective edge corresponding to a respective term in the command sentence and connecting a respective first node to a respective second node, wherein one of the first nodes is a source node having only one edge corresponding to a first term in the command sentence and one of the second nodes is a sink node; annotating each respective term of an edge as one of a terminal or a non-terminal; accessing, by the data processing apparatus, a plurality of parsing rules, each parsing rule defined by one or more constituent parsing rules and each parsing rule associated with a particular action, wherein at least some of the paring rules include constituent parsing rules that include non-terminals, and wherein each particular action is an action to be taken by the user device in response to a successful parse of a command sentence by the parsing rule; for each of the parsing rules, determining lattice spans of two or more nodes that define corresponding term spans in the command sentence that are consumed by one or more constituent parsing rules; for each parsing rule for which the determined lattice spans from the source node to the sink node of the lattice parse, selecting the parsing rule as a candidate parse of the command sentence; determining, from the candidate parses of the command sentence, an action to be performed in response to the command sentence; and causing the determined action to be performed.