A Character at a Time

reading with pipe

Reading • A Jolly Good Time (tm).

The way we think about implementing a parser is quite different to the high level abstract view we were given with mpc. Instead of thinking about the language we instead need to think about the process.

Usually this process takes a very simple form - a parser is almost always just a loop, which repeatedly reads a character at a time from the input, and each time decides what to do with it. The challenge is in making this process elegant. It all starts to get a little messy when we think about whitespace, and comments, and everything else.

To give an idea of how it might work - in our Lisp, if we encounter the character d in the input, we can store it in some string, and also we know we must be reading in a symbol, so can enter a state where we look for more letters, each time adding them to the string. Once we’re found no more letters in the input we can return the whole thing as a symbol (for example def) and start again.

The function lval_read_expr is basically going to work like this. We’re going to take as input some string, some position in that string, and decide what to do next. When the next character isn’t the one specified by the argument end we will try to read in whatever thing appears next, create an lval object from it, and append it to the first argument v.

If instead we reach the character specified by end we’re going to return the next position in the string and return to the caller. This return value will help whoever calls lval_read_expr to see how much of the string it has consumed and how much is left.

For now let us assume the next character isn’t the end character. The first thing we need to check is that we’ve not reached the end of the input. If we’ve reached the end of the input without encountering the end character then we can throw a syntax error and jump to the end of the input to ensure no more is consumed.

  1. int lval_read_expr(lval* v, char* s, int i, char end) {
  3.   while (s[i] != end) {
  5.     /* If we reach end of input then there is some syntax error */
  6.     if (s[i] == '\0') {
  7.       lval_add(v, lval_err("Missing %c at end of input", end));
  8.       return strlen(s)+1;
  9.     }

After this we can check if the next character is whitespace. Any whitespace characters we can just skip over as our language is not whitespace sensitive.

  1.     /* Skip all whitespace */
  2.     if (strchr(" \t\v\r\n", s[i])) {
  3.       i++;
  4.       continue;
  5.     }

Another easy case is if the next character is a semi-colon ;. If it is a semi-colon we are starting a comment and we can ignore the rest of the characters until we reach a new line.

  1.     /* If next char is ; then read comment */
  2.     if (s[i] == ';') {
  3.       while (s[i] != '\n' && s[i] != '\0') { i++; }
  4.       i++;
  5.       continue;
  6.     }

If the next character is an open parenthesis ( or a curly bracket { we need to parse either an S-Expression or a Q-Expression. For these we can use lval_read_expr again and just supply it with a different character to end on and a different expression to write the results to.

  1.     /* If next character is ( then read S-Expr */
  2.     if (s[i] == '(') {
  3.       lval* x = lval_sexpr();
  4.       lval_add(v, x);
  5.       i = lval_read_expr(x, s, i+1, ')');
  6.       continue;
  7.     }
  9.     /* If next character is { then read Q-Expr */
  10.     if (s[i] == '{') {
  11.       lval* x = lval_qexpr();
  12.       lval_add(v, x);
  13.       i = lval_read_expr(x, s, i+1, '}');
  14.       continue;
  15.     }

Those are all the easy cases done. Now we need to decide what to do if we encounter some letter or number. In this case we need to parse all of the numbers or letters we can until we reach something that isn’t. For simplicity we’re going to treat numbers like a special case of symbols and if we encounter any of these we’re going to call the function lval_read_sym, which we’ll define later.

  1.     /* If next character is part of a symbol then read symbol */
  2.     if (strchr(
  3.       "abcdefghijklmnopqrstuvwxyz"
  4.       "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
  5.       "0123456789_+-*\\/=<>!&", s[i])) {
  6.       i = lval_read_sym(v, s, i);
  7.       continue;
  8.     }

We also have to deal with strings. If we reach a " character we’re going to have to consume everything we encounter up until the next unescaped ". For this we can call a function lval_read_str, which we’ll define later.

  1.     /* If next character is " then read string */
  2.     if (strchr("\"", s[i])) {
  3.       i = lval_read_str(v, s, i+1);
  4.       continue;
  5.     }

Finally if we somehow encounter something else we better throw an error and skip to the end of the input, and as mentioned before, if we do actually match our end character and the while loop ends, we just need to return the updated position in the input.

  1.     /* Encountered some unknown character */
  2.     lval_add(v, lval_err("Unknown Character %c", s[i]));
  3.     return strlen(s)+1;
  4.   }
  6.   return i+1;
  7. }

That completes the body of our function lval_read_expr. Now we just need to fill in the gaps.