A simpler approach might be to simply assign a CPU and memory cost to each operation, and fail the script if it goes over preset limits. The precise costs and limits would need to be defined at the protocol level to ensure compatibility. The script language could the be opened up to permit arbitrarily complex processing (loops, subroutines, recursion, etc.) without worrying about complexity.
However, that requires actually running the script. This would mean you could just scan and look at the number before the OP_LOOP, so easier.
They already have hard-coded values for all the operations.