1. A method, performed by one or more computing devices, for processing queries, comprising: receiving an input query, corresponding to a complete query or a yet-to-be-completed query; matching the input query against query-detection grammars defined by respective rule modules, with reference to a structured knowledge base, to generate a matching result; generating a first set of one or more synthetic query suggestions based on the matching result; presenting the first set of synthetic query suggestions; in response to the input query, or a later modification of the input query, further generating a query refinement tool, the query refinement tool specifying a plurality of refinement options; presenting the query refinement tool; receiving a selection of a refinement option identified by the query refinement tool; and in response to the selection, presenting a second set of one or more synthetic query suggestions, the second set of synthetic query suggestions being more refined compared to the first set of synthetic query suggestions, each synthetic query suggestion in the first set and the second set: being predicated on one or more matching query-expression grammars, being formed as an expressive natural language modification of an input query, and pertaining to at least one information item contained in the structured knowledge base.