This answer will depend on which PKI software you're using and how it's configured to handle revocation information. Certificate errors have a precedence; you want to check the most severe first.
The general procedure for validating a certificate is:
Check that the Root Cert is in your trust store (or some complicated path-building for a big corporate CA, see [**]).
Starting at the root, walk back down the cert chain checking for each one:
- Is it Revoked? -- the certificate will contain information on where and how to check that it's still valid, usually by CRL or OCSP. Follow this link to make sure it hasn't been revoked.
- Can the Signature on it be verified using the previous cert in the chain? -- ie the one right above it that you just finished verifying.
- Is it Expired? -- check the lifetime (aka validity period) of the cert.
* I chose to order the checks this way because I work with big corporate PKIs, and our CAs track expiry and revocation separately since it doesn't make sense to block users from viewing a corporate document just because it's old (think 10+ year-old email). [See the comment thread below with @SteffenUllrich for more on that].
In the web / ssl world you should check revocation and expiry at the same time and treat expired certs as if they were revoked. The reason is that most (all?) public ssl CAs stop tracking revocation when the cert expires. For example, imagine a cert that was revoked because of key compromise, then when it expires it drops from being "Revoked" to simply being "Expired" and the fact that it was revoked is lost.
[**] I'll generalize my answer a bit to include other PKI cases where you have to accept certs from root CAs that are not in your trust store. For corporate PKIs, often the root cert is not embedded in the end-cert, so you have go on a path-building expedition. This gets even worse when your root CA is cross-certified with other CAs, for example, corporate mail servers and ID badge systems when two companies merge, or if each department maintains their own root CA (which is common in government). If you have to support PKIs like this, then you'll have to devise a (probably complicated) online certificate path building scheme.
In response to Steffen Ullrich's comment, I just checked in the CA software that we use for our corporate PKI, the Entrust Authority Security Manager, and it certainly supports this:
and with this turned on you can also revoke certs even after they have expired. Unfortunately for you, the docs I'm looking at are not public, so I can't link them. I think the "partitioned CRL" is an Entrust-proprietary CRL format, so I have no idea if clients from other vendors support it, or if other CA software has similar features.
That said, unless you know (1) which CA software issued the certs you are checking, and (2) that it's configured to keep expired certs in the CRL, it is safer to treat Expired and Revoked as the same level of severity (or even the same error).