The connection of a superconductor to a chaotic ballistic quantum dot leads to interesting phenomena, most notably the appearance of a hard gap in its excitation spectrum. Here we treat such an Andreev billiard semiclassically where the density of states is expressed in terms of the classical trajectories of electrons (and holes) that leave and return to the superconductor. We show how classical orbit correlations lead to the formation of the hard gap, as predicted by random matrix theory in the limit of negligible Ehrenfest time tau(E), and how the influence of a finite tau(E) causes the gap to shrink. Furthermore, for intermediate tau(E) we predict a second gap below E = pi h/2 tau(E) which would presumably be the clearest signature yet of tau(E) effects.