Categorial Dependency Grammars (CDG) are classical categorial grammars adapted to surface syntactic dependencies. They generate unlimited projective and non-projective dependency structures, are completely lexicalized and analysed in polynomial time. We present an extension of the CDG, designed for elaboration of wide coverage hand-crafted grammars also analysed in polynomial time. Besides this, for the extended CDG, we introduce a specific method of “Structural Bootstrapping” consisting in incremental construction of extended CDG from representative samples of dependency structures. This method is supported by efficient algorithmic tools. We also outline a wide coverage dependency grammar of French developed by structural bootstrapping using these tools.