What is the best way to determine all commands that would be executed by a shell script?

Question

I'd like to be able to parse a shell script and return the set of commands (excluding shell keywords like if and for) that it could possibly execute, including all commands fed by pipes and all commands included in backticks.

What would be an appropriate way to approach this? I'm thinking regular expressions but it may not be sufficient. But I don't know enough parsing theory to figure this out properly.

Edit: Thanks for the responses so far. I see how external input would be a problem in determining this. How about if we exclude this from analysis, would it be a reasonable task in this case?

Answer 1

You can't, or put differently: Every command could be potentially executed.

Here's an example script.

$(cat somerandomfile)

What will it do? The answer is dependent on what is inside somerandomfile. To determine the set of potentially executed commands, you'd have to evalute the whole environment (which changes basically with every clock tick).

Answer 2

Let's assume that you have program X that answers the question that shell script Y uses command Z. Then we can construct shell script Y' that executes any program and after it finishes it calls command Z. So the hypothetical program X, that you ask for, solves the Halting Problem which is undecidable.