How do we build a semantic parser in a new domain starting with zero training examples? We introduce a new methodology for this setting, which first uses a domain-general grammar and a domain-specific seed lexicon to generate logical forms paired with canonical utterances that capture the meaning of the logical forms. By construction, the grammar ensures complete coverage of the desired set of compositional operators. We then use crowdsourcing to paraphrase these canonical utterances into natural utterances. The resulting data is used to train the semantic parser. We further study the role of compositionality in the resulting paraphrases. Finally, we test our methodology on seven domains and show that we can build an adequate semantic parser in just a few hours.