Context-free Grammar, Part I Top-down Parsing

//摘自《编译原理及实践》4.1.2节。
//Simple intger arithmetic calculator according to the EBNF:
//  <exp>-><term>{<addop><term>}
//  <addop>->+|-
//  <term>-><factor>{<mulop><factor>}
//  <mulop>->*
//  <factor>->(<exp>)|Number
//
//  Inputs a line of text from stdin
//  Outputs "ERROR" or the result.

#include <stdio.h>
#include <stdlib.h>

char token; //global token variable
//function prototypes for recursive call;
int exp(void);
int term(void);
int factor(void);

void error(void) {
    fprintf(stderr, "Error\n");
    exit(1);
}

void match(char expectedToken) {
    if(token == expectedToken)
        token = getchar();
    else
        error();
}

int main() {
    int result;
    token = getchar(); //load token with first character for lookahead
    result = exp();
    if(token == '\n') //check for end of line
        printf("Result = %d\n", result);
    else
        error(); //extraneous chars on line
    return 0;
}

int exp(void) {
    int temp = term();
    while((token == '+')||(token == '-')) {
        switch(token) {
            case '+':
                match('+');
                temp += term();
                break;
            case '-':
                match('-');
                temp -= term();
                break;
        }
    }
    return temp;
}

int term(void) {
    int temp = factor();
    while(token == '*') {
        match('*');
        temp *= factor();
    }
    return temp;
}

int factor(void) {
    int temp;
    if(token == '(') {
        match('(');
        temp = exp();
        match(')');
    } else if(isdigit(token)) {
        ungetc(token, stdin);
        scanf("%d", &temp);
        token = getchar();
    } else
        error();
    return temp;
}

//摘自：http://en.wikipedia.org/wiki/LL_parser
//关于parser table如何产生，请参考上面链接。
// parser table: (表中1,2,3为rule的编号)
// |---+---+---+---+---+---|
// |   | ( | ) | a | + | $ |
// |---+---+---+---+---+---|
// | S | 2 | - | 1 | - | - |
// | F | - | - | 3 | - | - |
// |---+---+---+---+---+---|
#include <iostream>
#include <stack>

/* List of tokens (terminals), begins with 1 */
enum {
  T_OP  = 1,  /* ( */
  T_CP,       /* ) */
  T_A,        /* a */
  T_PLUS,     /* + */
  T_EOF,      /* $ */
  T_ERROR     /* Just for errors */
};

/* Non-terminals names */
enum {
  N_S   = 1,
  N_F
};

/* Array of terminals/non-terminals to be pushed into the stack. Notes:
    * Terminals are negative.
    * First element is the number of elements in the array.
 */
/* S ->F */
static const int rule_s1[] = {1, N_F};
/* S ->'('S '+'F ')'*/
static const int rule_s2[] = {5, -T_OP, N_S, -T_PLUS, N_F, -T_CP};
/* F ->'a'*/
static const int rule_f1[] = {1, -T_A};

/* The parse table, the order of the rows and columns */
static const int * parse_table[][T_EOF] = {
         /*  (       )       a       +     $ */
  /* S */ {rule_s2, NULL, rule_s1, NULL, NULL},
  /* F */ {NULL   , NULL, rule_f1, NULL, NULL},
};

/*********************************************************************/

/* Simple tokenizer */
class Tokenizer {
  std::string src;
  size_t i;
  int current;

  int CheckNext(bool increment)
  {
    for(;;) {
      switch(src[i]) {
        case '': i++; break;
        case '(': current = T_OP; goto done;
        case ')': current = T_CP; goto done;
        case 'a': current = T_A;  goto done;
        case '+': current = T_PLUS; goto done;
        case '\0': current = T_EOF; return T_EOF;
        default  : return T_ERROR;
      }
    }

  done:
    if(increment) i++;
    return current;
  }

public:
  Tokenizer(const std::string&src) : src(src), i(0)
  { current = CheckNext(false); }

  int GetNext()
  { return CheckNext(true); }

  int PeekNext()
  { return CheckNext(false); }
};

/*********************************************************************/

int
main(void)
{
  Tokenizer tokenizer("(a + a)");
  std::stack<int>stack;

  /* Initialize the stack with the start symbol and EOF */
  stack.push(-T_EOF);
  stack.push(N_S);

  /* While there is something on the stack */
  while(!stack.empty()) {

    /* Check if the top is a terminal, negative value */
    if(stack.top() <0) {
      /* Get the top value, negate it! */
      int terminal = -stack.top();
      int token = tokenizer.GetNext();

      /* Tokenizer error? */
      if(token == T_ERROR) {
        std::cerr <<"Error (1): Unrecognised token.\n";
        return -1;
      }
      /* The terminal matches the input token? */
      else if(terminal != token) {
        std::cerr <<"Error (2): Unexpected token.\n";
        return -1;
      }
      /* Remove it from the stack */
      stack.pop();
    }

    else {
      /* Fetch the rule */
      const int *rule = parse_table[stack.top()-1][tokenizer.PeekNext()-1];

      /* Invalid rule */
      if(rule == NULL) {
        std::cerr <<"Error (3): No matching grammar for this token.\n";
        return -1;
      }

      /* Log the rule */
      if(rule == rule_s1) { std::cerr <<"S ->F\n"; }
      else if(rule == rule_s2) { std::cerr <<"S ->'('S '+'F ')'\n"; }
      else if(rule == rule_f1) { std::cerr <<"F ->'a'\n"; }

      /* Remove the symbol from the stack */
      stack.pop();

      /* Push the grammar to the stack in reverse order! */
      for(size_t i = rule[0]; i >0 ; i--) {
        stack.push(rule[i]);
      }
    }
  }

  /* Input is valid */
  std::cerr <<"OK!\n";

  return 0;
}