Recursive Descent Parsing 101

• I show the steps I've followed to write a recursive descent parser in C for expressions in the simple arithmetic language defined by this grammar:

  Exp     ::= Term {("+"|"-") Term}
  Term    ::= Factor {("*"|"/") Factor}
  Factor  ::= ("+"|"-") Factor
            | Primary
  Primary ::= "(" Exp ")"
            | NumLiteral
  

• The code is here: https://codeberg.org/pietroiusti/arit-parser/commits/branch/blog_post.

(6b0e9a55bd)

• Let's start with a simpler grammar: let our language be made of the three a, b, c variables and the multiplication operator only.

• The following is a natural way to write the grammar for such a language in BNF:

  Exp ::= Exp * Exp | Id
  Id  ::= "a" | "b" | "c"
  

• This grammar, though, is ambiguous.

• We could rewrite it thus (Cf. Dragon Book p. 199):

  Exp  ::= Exp * Id | Id
  Id   ::= "a" | "b" | "c"
  

• This grammar is not ambiguous. But there's still a problem: it is left recursive. Since it is left recursive, we cannot use a top-down parsing in general and recursive descent in particular.

• We can get rid of the left-recursion by translating the grammar into a right-recursive one (The Dragon Book, among others, explains how):

  Exp  ::= Id Exp'
  Exp' ::= "*" Id Exp' | Eps
  Id   ::= "a" | "b" | "c"
  

• Eps here stands for "Epsilon" which means "nothing".
• Okay. Let's see some code.
• parser.c is our main file.
• main takes the user input, initializes the scanner, and starts the parsing by calling parse.
• I'm not going to explain how the scanner works. It is based on the scanner shown in Crafting Interpreters. Check that out. The parser uses next_token to pull tokens from scanner until the input is entirely consumed.
• Each rule in the grammar has a corresponding function in parser.c:
  • parse_exp;
  • parse_exp_prime;
  • parse_id.
• parse pulls the first token and expects it to be an Exp. Accordingly, it calls parse_exp in the attempt to match an Exp. After an Exp is successfully parsed, the input is expected to have been entirely consumed, so parse returns parse_exp's return value — which contains the parse tree.
• If something goes wrong during the parsing process, then an error is printed and exit is called.
• parse_exp corresponds to the first rule in our grammar (Exp ::= Id Exp').
  • The code is self-explanatory:
    • i) we parse an Id,
    • ii) we parse an Exp',
    • we return a node which represents the Exp whose two only children are the nodes returned in i) and ii).
• The other parsing functions work analogously.

(1acb41c037)

• Let's replace the construction of a parse tree with the construction of an AST.

• Currently, parsing a * b constructs this tree:

      exp
      /\
    Id  Exp'
    /   / | \
   /   /  |  \
  a  "*"  Id  Exp'
          |    |
          b   Eps
  

• The printer prints this (the * node is implicit):

  EXP
    ID: a
    EXP_PRIME
      ID: b
      (Epsilon)
  

• We want the parser to construct the following, simpler, tree:

    mul
    /\
   /  \
  Id  Id
  |   |
  a   b
  

• Accordingly, we want the printer to print this:

  MUL
    ID: a
    ID: b
  

• In parser.c:
  • Get rid of make_exp, make_exp_prime, and make_eps. We don't need those kinds of nodes anymore.

  • Modify make_id so that it simply takes a char now:

    static ASTNode *make_id(char id) {
        ASTNode *node = malloc(sizeof(ASTNode));
        node->type = NODE_ID;
        node->data.id = id;
        return node;
    }
    

  • Add a make_mul function:

    static ASTNode *make_mul(ASTNode *left, ASTNode *right) {
        ASTNode *node = malloc(sizeof(ASTNode));
        node->type = NODE_MUL;
        node->data.binary.left = left;
        node->data.binary.right = right;
        return node;
    }
    

  • modify parse_exp so that it now returns either an Id node or a Mul node::

    static ASTNode *parse_exp(Scanner *scanner) {
        ASTNode *id = parse_id(scanner);
        ASTNode *ep = parse_exp_prime(scanner);
    
        if (!ep) return make_id(id->data.id);
    
        if (ep->type == NODE_ID || ep->type == NODE_MUL) {
            return make_mul(id, ep);
        }
    
        fprintf(stderr, "unrecognized type\n");
        exit(1);
    }
    

  • modify parse_id. It has to pass a char to make_id:

    static ASTNode *parse_id(Scanner *scanner) {
        if (parser.current.type == TOKEN_ID) {
            Token id_token = parser.current;
            parser.current = next_token(scanner);
            return make_id(*id_token.start);
        } else {
            fprintf(stderr, "parse_id failed\n");
            exit(1);
        }
    }
    

  • modify parse_exp_prime so that it returns either an Id node, or a Mul node, or NULL.

    static ASTNode *parse_exp_prime(Scanner *scanner) {
        if (parser.current.type == TOKEN_STAR) {
            parser.current = next_token(scanner); // consume star
            ASTNode *id = parse_id(scanner);
            ASTNode *ep = parse_exp_prime(scanner);
            if (!ep) return make_id(id->data.id);
            return make_mul(id, ep);
        } else {
            return NULL;
        }
    }
    

• In parser.h:

  • in NodeType get rid of NODE_EXP, NODE_EXPPRIME, NODE_EPS, and add NODE_MUL :

    typedef enum {
        NODE_ID,
        NODE_MUL,
    } NodeType;
    

• In printer.c:

  • modify node_type_to_str and print_ast accordingly:

    static const char* node_type_to_str(NodeType type) {
        switch (type) {
        case NODE_ID:          return "ID";
        case NODE_MUL:         return "MUL";
        default:               return "UNKNOWN";
        }
    }
    

    void print_ast(ASTNode *node, int indent) {
        print_indent(indent);
        printf("%s", node_type_to_str(node->type));
    
        switch (node->type) {
        case NODE_ID:
            printf(": %c\n", node->data.id);
            break;
        case NODE_MUL:
            printf("\n");
            print_ast(node->data.binary.left, indent + 1);
            print_ast(node->data.binary.right, indent + 1);
            break;
        default:
            printf("\n");
            break;
        }
    }
    

(b5cb41230)

• Let's now replace the right recursion with a loop in order to construct the tree in a way such that the multiplication operator is left associative as opposed to right associative.
• Using EBNF is more natural than BNF now that we use iteration as opposed to recursion:

  • Instead of:

    Exp  ::= Id Exp'
    Exp' ::= "*" Id Exp' | Eps
    

  • Simply:

    Exp  ::= Id {"*" Id}
    

    where the braces stands for the the Kleene closure.

• The printed tree for a*b*c is currently this:

  MUL
    ID: a
    MUL
      ID: b
      ID: c
  

• We want this:

  MUL
    MUL
      ID: a
      ID: b
    ID: c
  

• In parser.c:
  • get rid of parse_exp_prime.

  • Modify parse_exp by introducing a loop that allows us to build the tree in the direction we want:

    static ASTNode *parse_exp(Scanner *scanner) {
        // Ret val is either an id node or a mul node
        ASTNode *ret = parse_id(scanner);
    
        while (parser.current.type == TOKEN_STAR) {
            parser.current = next_token(scanner); // consume star
            ASTNode *id = parse_id(scanner);
            ret = make_mul(ret, id);
        }
    
        return ret;
    }
    

• We should have a parser working the intended way now.

(0a139718b3)

• Let's handle addition.

• The new grammar:

  Exp  ::= Term {"+" Term}
  Term ::= Id {"*" Id}
  

• In parser.c:

  • Instead of adding a make_add function (which would look almost the same as make_mul), get rid of make_mul and create a higher abstraction to make binary nodes of any type — it'll come handy later:

    static ASTNode *make_binary(NodeType type, ASTNode *left, ASTNode *right) {
        ASTNode *node = malloc(sizeof(ASTNode));
        node->type = type;
        node->data.binary.left = left;
        node->data.binary.right = right;
        return node;
    }
    

  • Since the Exp rule changed, modify parse_exp accordingly:

    static ASTNode *parse_exp(Scanner *scanner) {
        // Ret val is either an id node or an add node
        ASTNode *ret = parse_term(scanner);
    
        while (parser.current.type == TOKEN_PLUS) {
            parser.current = next_token(scanner); // consume plus
            ASTNode *term = parse_term(scanner);
            ret = make_binary(NODE_ADD, ret, term);
        }
    
        return ret;
    }
    

  • Add a parse_term function (the body is the same as the old parse_exp's body, except that now we use make_binary instead of make_mul):

    static ASTNode *parse_term(Scanner *scanner) {
        // Ret val is either an id node or a mul node
        ASTNode *ret = parse_id(scanner);
    
        while (parser.current.type == TOKEN_STAR) {
            parser.current = next_token(scanner); // consume star
            ASTNode *id = parse_id(scanner);
            ret = make_binary(NODE_MUL, ret, id);
        }
    
        return ret;
    }
    

• In parser.h:

  • add NODE_ADD to NodeType:

  typedef enum {
      NODE_ID,
      NODE_MUL,
      NODE_ADD,
  } NodeType;
  

• In scanner.h:

  • Add TOKEN_PLUS to TokenType:

  typedef enum {
      TOKEN_PLUS,
      TOKEN_STAR,
      TOKEN_ID,
      TOKEN_ERROR,
      TOKEN_EOF,
  } TokenType;
  

• in scanner.c:

  • Add a case '+' in the switch in next_token:

    Token next_token(Scanner *scanner) {
        //...
        case '+':
            return make_token(scanner, TOKEN_PLUS);
        //...
    }
    

• In printer.c:

  • add a case NODE_ADD in node_type_to_str and print_ast:

    static const char* node_type_to_str(NodeType type) {
        switch (type) {
        case NODE_ID:          return "ID";
        case NODE_ADD:         return "ADD";
        case NODE_MUL:         return "MUL";
        default:               return "UNKNOWN";
        }
    }
    

    void print_ast(ASTNode *node, int indent) {
        print_indent(indent);
        printf("%s", node_type_to_str(node->type));
    
        switch (node->type) {
        case NODE_ID:
            printf(": %c\n", node->data.id);
            break;
        case NODE_ADD:
        case NODE_MUL:
            printf("\n");
            print_ast(node->data.binary.left, indent + 1);
            print_ast(node->data.binary.right, indent + 1);
            break;
        default:
            printf("\n");
            break;
        }
    }
    

(4a48fe4ad9)

• Let's handle subtraction.
• In parser.c:

  • Modify the Exp rule in the grammar:

    Exp ::= Term {("+"|"-") Term}
    

  • modify parse_exp:

    static ASTNode *parse_exp(Scanner *scanner) {
        // Ret val is either an id node or an add node
        ASTNode *ret = parse_term(scanner);
    
        TokenType op;
        while (parser.current.type == TOKEN_PLUS || parser.current.type == TOKEN_MINUS) {
            op = parser.current.type; // store op before consuming it
            parser.current = next_token(scanner); // consume the (plus|minus)
            ASTNode *term = parse_term(scanner);
            ret = make_binary(op == TOKEN_PLUS ? NODE_ADD : NODE_SUB, ret, term);
        }
    
        return ret;
    }
    

• In parser.h:

  • add NODE_SUB to NodeType:

    typedef enum {
        // ...
        NODE_SUB,
    } NodeType;
    

• In scanner.c:

  • Handle the '-' in scan_token:

    Token next_token(Scanner *scanner) {
        //...
        case '-':
            return make_token(scanner, TOKEN_MINUS);
        //...
    }
    

• In scanner.h:

  • Add TOKEN_MINUS:

    typedef enum {
        // ...
        TOKEN_MINUS,
        // ...
    } TokenType;
    

• In printer.c:

  • Handle NODE_SUB in node_type_to_str and print_ast:

    static const char* node_type_to_str(NodeType type) {
        switch (type) {
        // ...
        case NODE_SUB:         return "SUB";
        // ...
        }
    }
    

    void print_ast(ASTNode *node, int indent) {
        // ...
        case NODE_ADD:
        case NODE_SUB:
        case NODE_MUL:
            printf("\n");
            print_ast(node->data.binary.left, indent + 1);
            print_ast(node->data.binary.right, indent + 1);
            break;
        // ...
    }
    

(ab74ea004e)

• Let's now handle division.
• In parser.c:

  • Update the Term rule in the grammar:

    Term ::= Id {("*"|"/") Id}
    

  • Modify parse_term:

    static ASTNode *parse_term(Scanner *scanner) {
        // Ret val is either an id node or a mul node
        ASTNode *ret = parse_id(scanner);
    
        TokenType op;
        while (parser.current.type == TOKEN_STAR || parser.current.type == TOKEN_SLASH) {
            op = parser.current.type; // store op before consuming it
            parser.current = next_token(scanner); // consume the (star|slash)
            ASTNode *id = parse_id(scanner);
            ret = make_binary(op == TOKEN_STAR ? NODE_MUL : NODE_DIV, ret, id);
        }
    
        return ret;
    }
    

• In parser.h:

  • Add a NODE_DIV:

    typedef enum {
        // ...
        NODE_DIV,
        // ...
    } NodeType;
    

• In scanner.c:

  • Handle '/':

    Token scan_token() {
        // ...
        case '/':
            return make_token(TOKEN_SLASH);
        // ...
    }
    

• In scanner.h:

  • Add a TOKEN_SLASH:

    typedef enum {
        // ...
        TOKEN_SLASH,
        // ...
    } TokenType;
    

• In printer.c:

  • Handle NODE_DIV in node_type_to_str and print_ast:

    static const char* node_type_to_str(NodeType type) {
        switch (type) {
        // ...
        case NODE_DIV:         return "DIV";
        // ...
        default:               return "UNKNOWN";
        }
    }
    

    void print_ast(ASTNode *node, int indent) {
        // ...
        case NODE_ADD:
        case NODE_SUB:
        case NODE_MUL:
        case NODE_DIV:
            printf("\n");
            print_ast(node->data.binary.left, indent + 1);
            print_ast(node->data.binary.right, indent + 1);
            break;
        // ....
        }
    }
    

(e85ca9a034)

• In parser.c:

  • Modify the Term rule and add a Factor rule:

    Exp    ::= Term {("+"|"-") Term}
    Term   ::= Factor {("*"|"/") Factor}
    Factor ::= "(" Exp ")"
             | Id
    

  • The Term rule has changed. Modify parse_term accordingly:

    static ASTNode *parse_term(Scanner *scanner) {
        // Ret val is either an id node or a mul node
        ASTNode *ret = parse_factor(scanner);
    
        TokenType op;
        while (parser.current.type == TOKEN_STAR || parser.current.type == TOKEN_SLASH) {
            op = parser.current.type; // store op before consuming it
            parser.current = next_token(scanner); // consume the (star|slash)
            ASTNode *factor = parse_factor(scanner);
            ret = make_binary(op == TOKEN_STAR ? NODE_MUL : NODE_DIV, ret, factor);
        }
    
        return ret;
    }
    

  • Add parse_factor:

    static ASTNode *parse_factor(Scanner *scanner) {
        if (parser.current.type == TOKEN_OPEN_PAREN) {
            parser.current = next_token(scanner); // consume '('
            ASTNode *exp = parse_exp(scanner);
            if (parser.current.type != TOKEN_CLOSE_PAREN) {
                fprintf(stderr, "expected ')'\n");
                exit(1);
            }
            parser.current = next_token(scanner); // consume ')'
            return exp;
        }
        return parse_id(scanner);
    }
    

• In scanner.c:

  • handle ( and ) in scanToken:

    Token scan_token() {
        // ...
        case '(':
            return make_token(TOKEN_OPEN_PAREN);
        case ')':
            return make_token(TOKEN_CLOSE_PAREN);
        // ...
    }
    

• In scanner.h:

  • Add TOKEN_OPEN_PAREN and TOKEN_CLOSE_PAREN in TokenType:

    typedef enum {
        // ...
        TOKEN_OPEN_PAREN,
        TOKEN_CLOSE_PAREN,
        // ...
    } TokenType;
    

(719c6f39a1)

• Let's get rid of the a, b, c variables and use numbers instead, so that we can parse expressions like 1+22*333.

• Replace Id with NumLiteral in the Factor rule:

  Factor ::= "(" Exp ")"
           | NumLiteral
  

• In parser.c:
  • Get rid of make_id.

  • Add make_num_literal:

    static ASTNode *make_num_literal(const char *s, int length) {
        ASTNode *node = malloc(sizeof(ASTNode));
        node->type = NODE_NUM_LITERAL;
        node->data.num_literal.s = s;
        node->data.num_literal.length = length;
        return node;
    }
    

  • Adjust the comments in parse_exp and parse_term:

    static ASTNode *parse_exp(Scanner *scanner) {
      // Ret val is either a num literal node or an add node
      // ...
    }
    

    static ASTNode *parse_term(Scanner *scanner) {
      // Ret val is either a num literal node or a mul node
      // ...
    }
    

  • Replace the call to parse_id with a call to parse_num in parse_factor:

    static ASTNode *parse_factor(Scanner *scanner) {
        // ...
        return parse_num_literal(scanner);
    }
    

  • Get rid of parse_id.

  • Add parse_num_literal:

    static ASTNode *parse_num_literal(Scanner *scanner) {
        if (parser.current.type == TOKEN_NUM_LITERAL) {
            Token num_literal_token = parser.current;
            parser.current = next_token(scanner);
            return make_num_literal(num_literal_token.start, num_literal_token.length);
        } else {
            fprintf(stderr, "parse_num_literal failed\n");
            exit(1);
        }
    }
    

• In parser.h:

  • Add a NODE_NUM_LITERAL in ~NodeType~:

    typedef enum {
        NODE_NUM_LITERAL,
        // ...
    } NodeType;
    

  • Update the data union in ASTNode, by getting rid of id and adding num_literal:

    typedef struct ASTNode {
        NodeType type;
        union {
            struct {
                const char *s;
                int length;
            } num_literal;
            struct {
                struct ASTNode *left;
                struct ASTNode *right;
            } binary;
        } data;
    } ASTNode;
    

• In scanner.c:

  • We need to add a notion of NumLiteral in the scanner:

    static bool is_digit(char c) {
        return c >= '0' && c <= '9';
    }
    
    // NumLiteral ::= Digit+
    //              | Digit+ "." Digit+
    static bool match_num_literal(Scanner *scanner) {
        if (match_digit(scanner)) {
            while (match_digit(scanner))
                ;
            if (match(scanner, '.')) {
                if (match_digit(scanner)) {
                    while (match_digit(scanner))
                        ;
                    return true; // <digit>+ . <digit>+
                }
                scanner->current--;
            }
            return true; // <digit>+
        }
        return false;
    }
    
    // Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
    static bool match_digit(Scanner *scanner) {
        if (is_digit(*scanner->current)) {
            advance(scanner);
            return true;
        }
        return false;
    }
    
    static bool match(Scanner *scanner, char expected) {
        if (is_at_end(scanner)) return false;
        if (*scanner->current != expected) return false;
        scanner->current++;
        return true;
    }
    

    • modify next_token by removing the case for 'a', 'b', and 'c' and handling number literals:

      Token next_token(Scanner *scanner) {
          skip_space(scanner);
          scanner->start = scanner->current;
          if (is_at_end(scanner)) return make_token(scanner, TOKEN_EOF);
          if (match_num_literal(scanner)) return make_token(scanner, TOKEN_NUM_LITERAL);
          char c = advance(scanner);
          switch(c) {
          case '+':
              return make_token(scanner, TOKEN_PLUS);
          case '-':
              return make_token(scanner, TOKEN_MINUS);
          case '*':
              return make_token(scanner, TOKEN_STAR);
          case '/':
              return make_token(scanner, TOKEN_SLASH);
          case '(':
              return make_token(scanner, TOKEN_OPEN_PAREN);
          case ')':
              return make_token(scanner, TOKEN_CLOSE_PAREN);
          }
          return make_error_token(scanner, "Unexpected character.");
      }
      

• In scanner.h:

  • Add TOKEN_NUM_LITERAL in TokenType:

    typedef enum {
        // ...
        TOKEN_NUM_LITERAL,
        // ...
    } TokenType;
    

• In printer.c:

  • add print_num_literal:

    static void print_num_literal(const char *s, int length) {
        printf(": ");
        for (int i = 0; i < length; i++) {
            printf("%c", *(s+i));
        }
        printf("\n");
    }
    

  • replace the NODE_ID cases in node_type_to_str and print_ast with those for NODE_NUM_LITERAL:

    static const char* node_type_to_str(NodeType type) {
        // ...
        case NODE_NUM_LITERAL:  return "NUM LITERAL";
        // ...
    }
    

    void print_ast(ASTNode *node, int indent) {
        // ...
        case NODE_NUM_LITERAL:
            print_num_literal(node->data.num_literal.s, node->data.num_literal.length);
            break;
        // ...
    }
    

(debf5498c8)

• Update the grammar byt modifying Factor and adding Primary:

  Exp     ::= Term {("+"|"-") Term}
  Term    ::= Factor {("*"|"/") Factor}
  Factor  ::= "-" Factor
            | Primary
  Primary ::= "(" Exp ")"
            | NumLiteral
  

• In parser.c:

  • add make_neg:

    static ASTNode *make_neg(ASTNode *negated_node) {
        ASTNode *node = malloc(sizeof(ASTNode));
        node->type = NODE_NEG;
        node->data.unary.node = negated_node;
        return node;
    }
    

  • modify parse_factor:

    static ASTNode *parse_factor(Scanner *scanner) {
        if (parser.current.type == TOKEN_MINUS) {
            parser.current = next_token(scanner); // consume '-'
            ASTNode *factor = parse_factor(scanner);
            return make_neg(factor);
        }
    
        return parse_primary(scanner);
    }
    

  • add parse_primary (which has the same body of our old parse_factor):

    static ASTNode *parse_primary(Scanner *scanner) {
        if (parser.current.type == TOKEN_OPEN_PAREN) {
            parser.current = next_token(scanner); // consume '('
            ASTNode *exp = parse_exp(scanner);
            if (parser.current.type != TOKEN_CLOSE_PAREN) {
                fprintf(stderr, "expected ')'\n");
                exit(1);
            }
            parser.current = next_token(scanner); // consume ')'
            return exp;
        }
        return parse_num_literal(scanner);
    }
    

• In parser.h:

  • add NODE_NEG in NodeType:

    typedef enum {
        NODE_NEG,
        // ...
    } NodeType;
    

  • add a unary member in the data union in ASTNode:

    typedef struct ASTNode {
        // ...
        union {
            // ...
            struct {
                struct ASTNode *node;
            } unary;
            // ...
        } data;
    } ASTNode;
    

• In printer.c:

  • Add a NODE_NEG case in node_type_to_str and print_ast:

    static const char* node_type_to_str(NodeType type) {
        //...
        case NODE_NEG:  return "NEG";
        // ...
    }
    

    void print_ast(ASTNode *node, int indent) {
        // ...
        case NODE_NEG:
            printf("\n");
            print_ast(node->data.unary.node, indent + 1);
            break;
        // ...
    }
    

(646fd2fce5)

• New Factor rule:

  Factor  ::= ("+"|"-") Factor
            | Primary
  

• Modify parse_factor (we don't need to create POS nodes, since +x == x):

  // Factor  ::= ("+"|"-") Factor
  //           | Primary
  static ASTNode *parse_factor(Scanner *scanner) {
      TokenType curr;
      if (parser.current.type == TOKEN_PLUS || parser.current.type == TOKEN_MINUS) {
          curr = parser.current.type;
          parser.current = next_token(scanner); // consume the (plus|minus)
          ASTNode *factor = parse_factor(scanner);
          return curr == TOKEN_PLUS ? factor : make_neg(factor);
      }
  
      return parse_primary(scanner);
  }
  

• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools. (The Dragon Book)
• Nystrom: Crafting Interpreters.
• Cooper, Torczon: Engineering a Compiler.
• Kay Lack: 0de5.
• Relevant exchange on hn: https://news.ycombinator.com/item?id=39317161
• https://gokcehan.github.io/notes/recursive-descent-parsing.html