We present a semiclassical theory for the excitation spectrum of a ballistic quantum dot weakly coupled to a superconductor, for the generic situation that the classical motion gives rise to a phase space containing islands of regularity in a chaotic sea. The density of low-energy excitations is determined by quantum energy scales that are related in a simple way to the morphology of the mixed phase space. An exact quantum mechanical computation for the annular billiard shows good agreement with the semiclassical predictions, in particular for the reduction of the excitation gap when the coupling to the regular regions is maximal.