In accordance with an embodiment, described herein is a system and method for providing a programmable packet classification framework for use in a network device in a high performance network. The packet classification framework can comprise a plurality of hardware-based programmable classification primitives, including a key composition primitive, a key composition rule primitive, a match action logical structure, and a next action primitive. The classification primitives can be logically strung together, with the results from one classification primitive fed into the next one until the processing of a data packet is completed. The classification framework can use a state machine to track states of the data packet processing, and dynamically adjust behaviors of the classification primitives based on the processing states of a data packet. With the programmable classification primitives, the classification framework can recursively parse data packets of a plurality of protocols without requiring any hardware changes.