We present an integrated planning framework for quadrupedal locomotion over discrete, unforeseen terrain configurations revealed at runtime. Existing methods often depend on heuristics for real-time foothold selection—limiting robustness and adaptability—or rely on computationally intensive trajectory optimization across complex terrains and long horizons. In contrast, our approach combines reactive synthesis for generating correct-by-construction symbolic-level controllers with mixed-integer convex programming (MICP) that checks the feasibility of footstep and gait plans under a reduced-order dynamics model during each symbolic transition. For each transition, the framework uses the first feasible gait it finds and does not rank feasible gaits by motion quality. To reduce the reliance on costly MICP solves and handle specifications that become unrealizable when transitions are infeasible under this model, we adopt a symbolic repair mechanism that selectively generates only the required symbolic transitions. During execution, online MICP replanning based on actual terrain data, runtime symbolic repair, kinematic-feasibility re-targeting, and a delay-aware coordination scheme enable seamless bridging between offline synthesis and online operation. Through extensive simulation and hardware experiments, with terrain geometry obtained from motion capture on hardware, we validate the framework's ability to identify missing locomotion skills and respond effectively in safety-critical environments, including scattered stepping stones and rebar scenarios.