Introduction to Parsing - 3

Published Tuesday, Dec 2, 2014 - 1374 words, 7 minutes
Tagged:

This post is part of the Introduction to parsing series.

In the last part we have continued working on our little parser. Specifically, we have improved the lexer and started creating the parser, so that it is now able to handle simple numbers. Let’s teach it some arithmetic now!

Grammars

A common tool when discussing parsing are grammars. Grammars are a code-like representation of how the parser works. There are quite a few tools, such as the lex/yacc duo and Antlr, that can generate a lexer and a parser automatically from a grammar descrition, but we won’t cover that now.

Anyway, let’s see a simple example:

expression : NUMBER;

This roughly means that an expression is made of a single NUMBER token, which is what we have implemented last time:

int Parser::evalNextExpression()
{
    Token t = lexer_.nextToken();
    if (t.getTokenType() == TokenType::NUMBER) {
        return atoi(t.getContent().c_str());
    }
    throw InvalidInputException("Found an unexpected token: " + t.getContent());
}

Additions and subtractions

Let’s now improve our parser so that it can handle additions and subtractions. To do that, we’ll start by rewriting the grammar, and then adapting the code. As we’ll see, writing the code after we have written the grammar will turn out to be quite simpler - in fact, as we have mentioned, thre are quite a few tool that automate this. So, here’s the updated grammar:

expression: term [ ('+'|'-') term ]*;

term : NUMBER;

This roughly reads:

  • an expression is made of a term, followed by zero or more repetitions of + or - symbols and a term;
  • a term is a NUMBER token.

In code:

int Parser::evalNextExpression()
{
    // First handle multiplication and parenthesis
    int value = evalNextTerm();

    // Next handle additions and subtractions.
    while (lexer_.hasNextToken()) {
       value = handleAdditionSubtraction(value);
    }
    return value;
}

int Parser::evalNextTerm()
{
    Token t = lexer_.nextToken();
    if (t.getTokenType() == TokenType::NUMBER) {
        return atoi(t.getContent().c_str());
    }
    throw InvalidInputException("Found an unexpected token: " + t.getContent());
}

int Parser::handleAdditionSubtraction(int currValue)
{
    Token t = lexer_.nextToken();
    if (t.getTokenType() == TokenType::OPERATOR) {
        if (t.getContent() == "+") {
            return currValue + evalNextTerm();
        } else if (t.getContent() == "-") {
            return currValue - evalNextTerm();
        } else {
            throw InvalidInputException("Found an invalid operator: " + t.getContent());
        }
    } else {
        throw InvalidInputException("Found an unexpected token: " + t.getContent());
    }
}

With this code, we pass the first tests about additions and subtractions! Woo!

Multiplications and divisions

The code above is a good start. However, it has a subtle issue that will become apparent when we’ll try to implement multiplications and divisions.

Let’s try to design the grammar first: we have to write it in a way so that * has a higher precedence than +, since 1+2*3 means 1+(2*3). The way to do it looks very simple, but it’s actually rather deep:

expression: term [ ('+'|'-') term ]*;

term : factor [ ('*'|'/') factor]*;

factor : NUMBER;

The change from the previous time is that the term is now defined as a sequence of multiplications or divisions of factors. This gives us implicitely the precedence: before parsing an addition we’ll have parsed all the multiplications! If we try to represent the behaviour of a parser when handling 1+2*3, we can see it has to follow roughly this sequence:

Stack           To parse   Parsed     Comment
expression      1+2*3                 start parsing the term
  term                                start parsing the factor
    factor                            parse a NUMBER
    factor      +2*3       1          return
  term                                we don't have a * or /: return
expression      2*3        1+         parse the + and start parsing a term
  term                                start parsing a factor
    factor                            parse a NUMBER
    factor      *3         1+2        return
  term          3          1+2*       match the * and parse a factor
    factor                            parse a NUMBER
    factor                 1+2*3      return
  term                                no more * or /: return
expression                            no more + or -: return

First implementation

If we try to implement our new grammar in a similar way as before, we’ll hit a problem, as we can see in this commit:

int Parser::evalNextTerm()
{
    // First handle numbers and parenthesis
    int value = evalNextFactor();

    // Next handle multiplications and divisions.
    while (lexer_.hasNextToken()) {
        value = handleMultiplicationDivision(value);
    }
    return value;
}

int Parser::evalNextFactor()
{
    Token t = lexer_.nextToken();
    if (t.getTokenType() == TokenType::NUMBER) {
        return atoi(t.getContent().c_str());
    }
    throw InvalidInputException("Found an unexpected token: " + t.getContent());
}

int Parser::handleMultiplicationDivision(int currValue)
{
    Token t = lexer_.nextToken();
    if (t.getTokenType() == TokenType::OPERATOR) {
        if (t.getContent() == "*") {
            return currValue + evalNextTerm();
        }
        else if (t.getContent() == "/") {
            return currValue - evalNextTerm();
        }
        else {
            throw InvalidInputException("Found an invalid operator: " + t.getContent());
        }
    }
    else {
        throw InvalidInputException("Found an unexpected token: " + t.getContent());
    }
}

The problem appears when parsing expressions like 3*2+1: the term will have attempted to match the + and given us an error! What we need is for the term to handle an operator only if it’s of a correct type (* and /). How can we implement it?

Lookahead token

What we need, similarly to what we did for our lexer, is to have a lookahead token: a reference to the next available token. This makes sense, because actually our lexer, if we ignore whitespaces, can be thought of as a simple parser following this grammar:

token : number | OPERATOR;

number : DIGIT [DIGIT]*;

OPERATOR: '+' | '-' | '*' | '/' | '(' | ')';

DIGIT: '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9';

So, let’s add a lookahead token and fix our parser:

class Parser
{
    // as before
private:
    Token nextToken_{TokenType::END_OF_INPUT, ""};
    bool hasNextToken_{false};
};

Again, we’ll mantain the invariant “nextToken always refers to the next token”. We’ll also add a special token type, END_OF_INPUT, to represent “no more data available”.

Armed with this, we can write our simple advance method:

void Parser::advance()
{
    if (lexer_.hasNextToken()) {
        nextToken_ = lexer_.nextToken();
        hasNextToken_ = true;
    } else {
        nextToken_ = Token(TokenType::END_OF_INPUT, "");
        hasNextToken_ = false;
    }
}

Now we are ready to adapt the parsing of expressions and factors. The new version, which works correctly and passes our unit tests, is:

int Parser::evalNextExpression()
{
    // First handle multiplication and parenthesis
    int value = evalNextTerm();

    // Next handle additions and subtractions. They have lower precedences, so they are handled AFTER.
    while (hasNextToken_ && nextToken_.getTokenType() == TokenType::OPERATOR) {
        if (nextToken_.getContent() == "+") {
            advance();
            value += evalNextTerm();
        } else if (nextToken_.getContent() == "-") {
            advance();
            value -= evalNextTerm();
        } else {
            // An operator, but not '+' or '-': let the caller handle it.
            break;
        }
    }

    return value;
}

int Parser::evalNextTerm()
{
    // First handle numbers and parenthesis
    int value = evalNextFactor();

    // Next handle multiplications and divisions
    while (hasNextToken_ && nextToken_.getTokenType() == TokenType::OPERATOR) {
        if (nextToken_.getContent() == "*") {
            advance();
            value *= evalNextFactor();
        } else if (nextToken_.getContent() == "/") {
            advance();
            value /= evalNextFactor();
        } else {
            // An operator, but not '*' or '/': let the caller handle it.
            break;
        }
    }

    return value;
}

int Parser::evalNextFactor()
{
    Token currToken = nextToken_;
    if (currToken.getTokenType() == TokenType::NUMBER) {
        advance();
        return atoi(currToken.getContent().c_str());
    }
    throw InvalidInputException("Found an unexpected token: " + currToken.getContent());
}

If you try to match the code with the grammar, you’ll see they follow the exact same structure: when parsing an expresison we start by handling a term. Then, if we can, we match a + or - and another term, and so on. When we find something which is not a + or -, we stop parsing the expression. Parsing terms follows more or less the same structure.

Next time…

In the next time, we’ll extend our parser to handle parenthesis. If you wanna try to write the code for yourself, think about how you’d express in the grammar the fact that parenthesis have an higher precedence than the other operators…

Post scriptum

The kind of parser we’re writing is called a recursive descent parser. Our grammar is LL(1), meaning it can be parsed by one lookahead token and so our parser does not require backtracking. Wikipedia has a good, if a bit complex, introduction.

Antlr is an excellent recursive descent parser generator, used for real-world languages such as Groovy. Here’s an excellent example of an ANTLR grammar just slightly more powerful than ours (which can handle parenthsis too ;-)). Here’s a very long list of example ANTLR grammars.