You can try and add a new run configuration: Run -> Run Configurations ... -> Select "Java Appliction" and click "New".
Alternatively use the shortcut: place the cursor in the class, then press Alt + Shift + X to open up a context menu, then press J.
I had this same problem. For me, the reason turned out to be that I had a mismatch in the name of the class and the name of the file. I declared class "GenSig" in a file called "SignatureTester.java".
I changed the name of the class to "SignatureTester", and the "Run as Java Application" option showed up immediately.
Had the same problem. I apparently wrote the Main wrong:
public static void main(String[] args){
I missed the [] and that was the whole problem.
Check and recheck the Main function!
Run As > Java Application wont show up if the class that you want to run does not contain the main method. Make sure that the class you trying to run has main defined in it.
Source: Stackoverflow.com