Algorithm for Writing a Command Interpreter

Question

I am writing a shell that needs a command interpreter. The current pattern I am using is as follows:

if(strcmp(command, "my_cmd_keyword1") == 0) {
  ...
}
else if(strcmp(command, "my_cmd_keyword2") == 0) {
  ..
}
...

However, the number of predefined command keywords might be very huge. The if-else branching turns out to be inefficient since it has to compare with every keyword (in the worst case). Is there any more efficient way to handle this? I am using C/C++ languages for my applications.

And, yes, there is, but your question is far too broad. You might want to read about compiler constuction. — too honest for this site, Sep 03 '15 at 21:12
Take a look at my answer to a similar question here: http://stackoverflow.com/questions/32320837/converting-input-from-stdcin-to-runnable-code-c/32320872#32320872 — mattnewport, Sep 03 '15 at 21:16
@Olaf Well, _compiler construction_ is a bit overshoot may be. _Interpreter building_, or something like that might fit better. — πάντα ῥεῖ, Sep 03 '15 at 21:21
@πάνταῥεῖ: That is mostly the same for the scanner/parser and symbol management part. Code generation is replaced by calling the execution functions instead of the code-generator functions, then executing Not sure if there is actually literature about interpreter construction. — too honest for this site, Sep 03 '15 at 21:23
@Olaf That many interpreted languages around I'm pretty sure there is ;-) ... — πάντα ῥεῖ, Sep 03 '15 at 21:26
@πάνταῥεῖ: No, I mean **specific** for interpreters and not for both. I never found such necessary, but YMMV. — too honest for this site, Sep 03 '15 at 21:29

JCx · Accepted Answer · 2015-09-03T21:59:05.017

You want function pointers and some kind of lookup table. Consider

std::unordered_map<String, std::function<void(std::string)>>

or a pair of sorted

std::vector<>'s

which might be faster.

Using C++11, and ignoring the string parsing issue for now, here's how the unordered_map and std::function work together:

#include <string>
#include <functional>
#include <unordered_map>

std::unordered_map<std::string, std::function<void(const std::string &)>> functions;

void xyz_function(const std::string & commandLine)
{
   // this will be called
}

void register_functions()
{
    functions["xyz"] = xyz_function;
}


int main()
{
    register_functions();

    std::string completeCommandLine = "xyz parameter parameter";
    std::string exampleCommand = "xyz";

    // now look up the command, and run the function registered
    functions[exampleCommand](completeCommandLine);

}

score 2 · Answer 2 · answered Sep 03 '15 at 21:52

A common solution to this problem is a hash table which maps command names to function pointers. (All the functions have to have to same signature; commonly, that would consist of a pointer to the remaining command line arguments.)

C++ conveniently has std::unordered_map (since C++11, or check in boost), which will save you a lot of implementation effort. Posix (since 2001, at least) defines the <search.h> header, which includes a simple hash map implementation. (As usual with C datastructure libraries, the associated value type is void*, so you need to cast to the desired datatype.) If neither of those works out for you, it's not hard to find open source hash table implementations, or even write one.

Algorithm for Writing a Command Interpreter

2 Answers2