algorithm for shell language interpreter to find if a char is between quotes

Question

Assume we have a string s (a C char *) that is a program in a language L. I want to parse L and know the following from the specification

The following characters must be quoted if they are to represent themselves:

| & ; < > ( ) $ ` \ " '

So let's say I scan and parse the string checking char by char and dynamically building up a structure in-memory for the whole program. The program can be as short as echo foobar but the important is to parse the different meanings of | in a string such as echo foo|cat and echo 'foo|cat' where the first is a pipeline and the second is printing a literal.

Now I have a new token char c that is the current char of s. Now I want to have a function boolean isBetweenQuotes(int position, string s) that returns true iff the character at position position is quoted in the string s - do you agree this is a good way of solving the problem? What should the function isBetweenQuotes look like? The return values should be for example

isBetweenQuotes(6, "echo foobar"); /* returns false */
isBetweenQuotes(6, "echo foobar|less"); /* returns false */
isBetweenQuotes(6, "echo 'foobar'|less"); /* returns true */
isBetweenQuotes(20, "echo "foo bar"|awk '{print $1}'`"); /* returns true */

I was recommended that a could use a finite state machine and/or an abstract syntax tree and do the code either with flex/bison or a custom scanner/tokenizer. I can currently execute trivial pipelines and I'm trying to make the shell code more readable than other current shells. I've studied the source for the following shells: ash, dash, sash, posh and custom shells and the most readable code has been sash, while I understand that posh and dash are more posix compliant.

My goal is to make a shell that can perform infinite pipeline by recursion with fork and exec and solve some signal handling problem that other shells might have if they allocate memory with malloc.

Answer 1

In principle, you could use something like your isBetweenQuotes function, but you're (probably) better served by a more structured way of parsing arguments pipelines.

However, something like the following might work:

int isBetweenQuotes(int pos, char *str) {
  return IBQplain(pos, str, 0);
}

int IBQplain(int pos, char *str, int offset) {      
  char ch;
  if (pos == offset)
    return 0;  /* Not within quotes */
  int escaped = 0;
  for (ch = str[offset]; ch; ch = str[++offset]) {
    if (!escaped) {
      switch (str[offset]) {
        '\'': return IBQsingle(pos, str, offset+1);
        '"':  return IBQdouble(pos, str, offset+1);
        '\\': escaped = 1
      } else {
        escaped = 0;
      }
      if (pos == offset)
        return escaped;  /* Not within quotes, but may be single-escaped */
  }

}

int IBQsingle(int pos, char *str, int offset) {
  int escaped = 0;
  for (; str[offset]; ++offset) {
     if (!escaped) {
        switch (str[offset]) {
           case '\\': escaped = 1;
           case '\'': return IBQplain(pos, str, offset+1);
         } 
      } else {
        escaped = 0;
      }
      if (pos == offset) {
        return 1;
      }
  }

And a similar function (although looking for ") for IBQdouble. This is essentially a simple state machine expressed as functions, with simple steppers to avoid deep recursion for "self-transitions".

Saying that, your best bet is probably to approach this by building up a sequence of structures, mimicking the parse tree.

Answer 2

do you agree this is a good way of solving the problem?

No. When you parse a shell command line, you work your way through the string, and so at any point you should already know whether you are inside quotes. Either because your parsing state machine is in some "between quotes" state, or because your recursive descent parser is in some "parse quoted string" function.

Answering the question in the middle of parsing basically means that you have to re-parse the string from the beginning, which just doesn't make sense.

If you want to know more about parsing, I suggest you look for a compiler/interpreter writing tutorial. A shell is just an interpreter for its particular language after all.