How do I check whether all code paths return a value

Question

I am writing a compiler for an embedded scripting language that will run in my application. I am currently working on the semantic analysis portion of the compiler. I would like to know, in theory, how to check that all code paths in a given script will return a value. Doing a Google search yields only results about people seeing the error in their own code when not all code paths return a value (mostly SO questions), so I have been unable to find sources that explain how the actual checking can be done. Can anyone point me in the right direction?

NOTE: I am specifically looking for an authoritative source outlining a rigorous algorithm, if at all possible.

Answer 1

You can do this with a recursive walk over the AST. For example:

• A sequence of statements returns on all control paths if either the first statement returns on all control paths or the second statement returns on all control paths.

• An if statement returns on all control paths if both the "if" and "else" branches return on all control paths or the "if" statement is always true.

• A while loop returns on all control paths only if the "while" condition is always true.

• A return statement returns on all control paths.

Hope this helps!