The x86 decoder is both simpler and more complex than it appears. I've played with the idea of creating the "worst" x86 decoder, which I classify as worst because its goal would not be to reproduce an assembly string but instead represent an oversimplified view of the instruction that makes sense semantically.
So the simple part of the decoding is that x86 instructions generally consist of an "opcode", a register number, and a third parameter which is either a register number, immediate, or memory operand. Occasionally, there is also another immediate operand tacked onto the instruction, based on the opcode. The REX prefix tacks on extra bits for the register number, the VEX prefix adds a third register number and provides a way to add some opcode bytes without spending extra bytes to do so, and the EVEX prefix has a few more extra operand types.
It's worth noting that if you're mapping semantics, some opcodes have the Mod/RM byte, but use fields in this parameter to add more bits to the opcode instead of as register numbers. If your semantics is prepared to handle per-register special cases (which it probably should, since x86 has per-register semantics in some cases), this isn't actually an issue.
The really difficult part, though, is managing prefixes. The new REX, VEX, and EVEX prefixes all have much tighter requirements on how they interact with each other: you can use exactly one of these prefixes, and the functionality in the older ones is completely subsumed by the newer ones. But the legacy prefixes don't have any such restrictions, and thus you can do annoying things like specify several of them at once or tack them on to instructions that don't need them.
The sanest way to handle prefixes, especially F0, F2, F3, 66, and 67, is to treat them instead as part of the opcode rather than an optional prefix, albeit ones that can float around a bit (although 66 is required to be the last prefix in a few cases). This also handles issues where the operand size override prefix doesn't actually override operand size. libbfd's hilariously bad results seem almost entirely due to doing the exact opposite of this rule, and not realizing that 66 and F0 actually create illegal instructions if not used correctly.
(Another thing you can do with weird prefixes is to just flag the result as "probably attempting to break a disassembler").
Unless you're interested in playing around with writing x86 decoders yourself, just use XED. It's maintained by Intel, and is up-to-date with all known instructions, and it should be capable of handling even most of the weirdest edge cases in handling unusual prefix combinations correctly. That said, it doesn't warn you of the few cases where the AMD x86 decoder and the Intel x86 decoder give inconsistent results.