In one embodiment, a method includes accessing a social graph that includes a plurality of nodes and edges, receiving an unstructured text query, identifying nodes and edges that correspond to n-grams of the text query, accessing a context-free grammar model, identifying grammars having query tokens that correspond to the identified nodes and edges, determining a score for each identified grammar, and then generating structured queries based on the identified grammars based on strings generated by the grammars.