An instruction-based programmable memory built-in self test (P-MBIST) circuit and an address generator thereof are provided. The P-MBIST circuit generates control signals according to the decoding of compact test instructions provided by an external automatic test equipment (ATE). The address generator generates memory addresses according to the control signals. The control signals and the memory addresses are sent to an embedded memory to perform the MBIST. The algorithm-specific design of the P-MBIST circuit and the address generator enables them to support multiple test algorithms at full clock speed and occupy smaller chip area.