1. A method comprising, by one or more processors associated with a mobile client system: receiving, at the mobile client system, an unstructured text query from a first user of an online social network; parsing, by the mobile client system, the unstructured text query into one or more n-grams; accessing, from a data store of the mobile client system, a set of nodes of a social graph of the online social network, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, the nodes comprising: a first node corresponding to the first user; and a plurality of second nodes that each correspond to a concept or a second user associated with the online social network; accessing, from the data store of the mobile client system, a set of grammar templates, each grammar template comprising one or more non-terminal tokens and one or more query tokens, wherein the query tokens comprise references to zero or more second nodes and one or more edges, and wherein each grammar template is based on a natural-language string; generating, by the mobile client system, one or more structured queries by matching the unstructured text query to one or more of the accessed nodes and one or more of the grammar templates having non-terminal tokens corresponding to the matched nodes, each structured query comprising references to one or more of the accessed nodes matched to the one or more non-terminal tokens and the zero or more of the second nodes and the one or more edges referenced in the corresponding grammar template; calculating, by the mobile client system, a cost for each grammar template based at least in part on one or more of the n-grams not corresponding to one of the non-terminal tokens or query tokens; and displaying, at the mobile client system, one or more structured queries to the first user; wherein each non-terminal token and query token has an associated insertion cost; and wherein calculating the cost comprises incurring an insertion cost for each of the non-terminal tokens or query tokens not corresponding to one or more n-grams.
1. A method comprising, by one or more processors associated with a mobile client system: receiving, at the mobile client system, an unstructured text query from a first user of an online social network; parsing, by the mobile client system, the unstructured text query into one or more n-grams; accessing, from a data store of the mobile client system, a set of nodes of a social graph of the online social network, the social graph comprising a plurality of nodes and a plurality of edges connecting the nodes, the nodes comprising: a first node corresponding to the first user; and a plurality of second nodes that each correspond to a concept or a second user associated with the online social network; accessing, from the data store of the mobile client system, a set of grammar templates, each grammar template comprising one or more non-terminal tokens and one or more query tokens, wherein the query tokens comprise references to zero or more second nodes and one or more edges, and wherein each grammar template is based on a natural-language string; generating, by the mobile client system, one or more structured queries by matching the unstructured text query to one or more of the accessed nodes and one or more of the grammar templates having non-terminal tokens corresponding to the matched nodes, each structured query comprising references to one or more of the accessed nodes matched to the one or more non-terminal tokens and the zero or more of the second nodes and the one or more edges referenced in the corresponding grammar template; calculating, by the mobile client system, a cost for each grammar template based at least in part on one or more of the n-grams not corresponding to one of the non-terminal tokens or query tokens; and displaying, at the mobile client system, one or more structured queries to the first user; wherein each non-terminal token and query token has an associated insertion cost; and wherein calculating the cost comprises incurring an insertion cost for each of the non-terminal tokens or query tokens not corresponding to one or more n-grams. 9. The method of claim 1 , wherein the receiving, by the mobile client system, from the first user the unstructured text query comprises receiving one or more characters of a character string as the user enters the character string into a graphical user interface.