Another possibility, somewhere between API and new language: create a domain-specific language on top of a general-purpose language. Think regular expressions: a mini-language, with its own syntax, built for just one purpose (e.g. text processing), which is usable from within another, more flexible language. Then you get the benefits of a language with a close fit to the domain, but also get a full language that you don't have to implement yourself if things start to get complex.
Lisp, Scala, and Ruby are popular choices for DSLs. Because they're so flexible, you can build a DSL directly inside the host language; this is called an embedded DSL. Interesting examples are Clojure's core.match and Midje, Ruby's rspec unit test library, and Scala's Baysick, a DSL that strongly resembles classic BASIC created using just Scala's own facilities. 904
The designs behind embedded DSLs differ by language; in Clojure and other Lisps, they usually use a lot of macros, while Scala gets a ton of mileage from implicits and Ruby gets a lot of use from blocks. Scala's and Ruby's flexible policies on using parentheses around function arguments are also a big help.
You can also create an external DSL by writing a simple parser and a small interpreter. You can use the parser generator libraries that others have suggested, but if the language is simple enough, you don't actually need to create an abstract syntax tree or a symbol table; you can just parse and execute commands one at a time, possibly holding on to some state as you go. If your syntax is constrained enough, you can just tokenize a line with regular expressions, then loop over the tokens. If there are no user-defined commands, you can just have a class or function for each command; you can store them in a table, and use the command name at the front of each line to look up the appropriate command and pass it arguments. The commands can validate that they received the appropriate type and number of arguments.
If you want to take the external DSL approach, you might be interested in the Interpreter Pattern as a way to organize things. 904