The growing pains of NGEDIT

Unlike other microISV entrepreneurs out there, I’ve started writing the blog a bit late in the development process. Some people start writing the blog as the first action towards building their product. Myself, I started with pure development as I saw that getting the product to exist was the key part in my case. After some hanging around JoS forums, and a suggestion to get the blog running from Ian of StealthPlayer, I actually set up a website and started writing the blog. It’s been very interesting, and the amount of attention brought over by Eric Sink has been a pleasant surprise (thanks Eric!).

Given the interest on the scripting engine side of things, I will do a brief recap of the scripting system. I have, myself, always had a clearly lustful interest in compilers 🙂

I will skip the overview in two or three parts, covering the lexer and parser in the first, and leaving code generation and execution for afterwards.

1. “Lexing”
Formally called lexical analyisis. The first stage is loading the actual text file and breaking it up into tokens. The interface is the typical GetNextToken() or PeekNextToken() (the latter not removing the actual next token). Skipping comments also happens here. Tokens are identified with a token enumerator, and the ones requiring more info (such as TOK_ID which is returned for any non-keyword identifier) point into the raw input buffer. This avoids memory management during the lexing phase.

One common option is to use a tool such as LEX or FLEX (a GNU clone of the former). I chose to implement it by hand, as it is simple enough and has not licensing issues. LEX/FLEX parsers are usually based in regular expressions to detect the tokens – I just wrote specialized code to detect each type of token.

2. “Parsing”
Formally called syntax analysis. I could have also gone with a tool such as YACC or BISON (the GNU clone) to generate a state machine parser, but I implemented a simple recursive descent one myself.

For those of you who haven’t seen a living specimen in the wild, how does a simple recursive descent parser look? Suppose we want to parse a syntax consisting on products and additions with no parentheses, with positive integer numbers as elements. The parser would accept and evaluate expressions such as 5 + 3 * 4, or 10 * 20 * 3 + 2 * 3 + 41 * 5. Suppose the lexer returns TOK_NUM for an integer value, TOK_ADD for the ‘+’ symbol, TOK_MUL for the ‘*’ symbol, and TOK_EOF when the end of file is reached. The value of the TOK_NUM returned can be asked for by calling GetTokenVal(). The lexer is also supposed to skip the whitespace in between the elements.

To write a recursive descent parser, we take into account that the multiply operator has precedence over the addition operator, that is, the previous expressions have to be evaluated as 5 + (3 * 4), or (10 * 20 * 3) + (2 * 3) + (41 * 5). This means that any such expression can be looked at as the addition of a series of products, which are themselves the product of a series of factors.

This is the key to structuring the parser: we will parse the whole expression by getting one product after the other, and adding them together. The products are parsed by getting one factor after the other and multiplying them together. When should the product parser stop? This is another key: when it finds a symbol that it doesn’t recognize as continuing the product (which could be another ‘+’ sign or the end of the sequence).

int TParser::ParseExpression()
{
  int iSum = 0;

  do
  {
    int iVal = ParseProduct();
    if (ErrorFound())
      return -1;

    iSum += iVal;

    TToken tok = m_pLexer->PeekNextToken();
    if (tok = TOK_ADD)
    {
      m_pLexer->EatToken();
    }
  } while (tok == TOK_ADD);

  return -1; // Should never arrive here
}

int TParser::ParseProduct()
{
  int iProduct = 1;

  do
  {
    int iVal = ParseFactor();
    if (ErrorFound())
      return -1;

    iProduct *= iVal;

    TToken tok = m_pLexer->PeekNextToken();
    if (tok == TOK_MUL)
    {
      m_pLexer->EatToken();
    }
  } while (tok == TOK_MUL);

  return -1; // Should never arrive here
}

int TParser::ParseFactor()
{
  TToken tok = m_pLexer->PeekNextToken();

  if (tok == TOK_NUM)
  {
    int iVal = m_pLexer->GetTokenVal();
    m_pLexer->EatToken();
    return iVal;
  }
  else
  {
    Error("Unexpected token");
    return -1;
  }
}

Ok, so now, why is it called a recursive descent parser? Clearly, the one above is not recursive at all. Now, suppose we want to expand the parser above to evaluate expressions with parentheses in them. In any place an integer used to appear, we must now allow a whole ‘nother subexpression, using both ‘*’ and ‘+’, enclosed between parentheses. This is simple enough to do: we only have to modify the ParseFactor function to accept what we just described:

int TParser::ParseFactor()
{
  TToken tok = m_pLexer->PeekNextToken();

  if (tok == TOK_NUM)
  {
    int iVal = m_pLexer->GetTokenVal();
    m_pLexer->EatToken();
    return iVal;
  }
  else if (tok == TOK_OPEN_PAREN)
  {
    m_pLexer->EatToken();
    int iVal = ParseExpression();
    if (m_pLexer->PeekNextToken() != TOK_CLOSE_PAREN)
    {
      Error("Closing parentheses expected");
      return -1;
    }
    m_pLexer->EatToken();
    return iVal;
  }
  else
  {
    Error("Unexpected token");
    return -1;
  }
}

And now, you can see how the parser operates recursively to parse complex expressions such as 3 + 4 * (6 + 1) or (((1 + 3) * 4 + 5) + 2) * 6 up to any nesting depth (or as long as the runtime environment will allow the stack to grow). The fact that the parsing functions stop at any unexpected token without “consuming it” allows them to stop when a closing parenthesis is reached, returning to the calling ParseFactor who “eats it up”.

Usually, parsers are written using other general tools employing algorithms such as LALR, which discard explicit recursion and implement stack based iterative methods. But recursive descent parsers are famed to sport fast execution, and they’re simple enough to write.

Next installment, I will cover how the code generation mechanism fits.

This entry was posted on Sunday, June 5th, 2005 at 11:32 pm and is filed under ngdev. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.