Bitstream parsing is a basic task in video decoding systems. With the development of video compression standards, the trend of the VLSI architecture for bitstream parser is toward programmable. Due to the strong data-dependency and bit-level sequential operations, bitstream parsing is unsuitable to accelerate by general architectures, such as RISC, SIMD and VLIW processors. This paper proposes a programmable bitstream parser for multiple video coding standards on embedded RISC processors. The proposed design presents an extension instruction set to accelerate some kernel functions of bitstream parsing. As a result, the proposed bitstream parser can decode every syntax element per cycle. The synthesis result shows that at the clock constraint of 150MHz, the hardware cost is about 7K gates of logic and 2k byte RAM under a 0.18um CMOS technology.