Click here to download c09/tablecalc.cpp.

/****************************************
Table-driven top-down parser for a simple
language.

Grammar for simple arithmetic.  Notice
the odd form of exp and term rules: We
had to write them without "left-recursion"
so that we could parse top-down:

stmt -> exp STOP
exp -> term exptail
exptail -> OPA term exptail| e
term -> sfactor termtail
termtail -> OPM factor termtail | e
sfactor -> OPA factor | factor
factor -> NUM | LP exp RP
*****************************************/
#include "calc.h"
#include <iostream>
#include <cstdlib>
#include <string>
#include <stack>
using namespace std;


/**************************************
 * Non-terminals are 
 * numbered consecutively from startSym
 * up, where startSym is some number
 * greater than any token number.
 **************************************/
enum NonTerminal {
  stmt=10,
  exp,
  exptail,
  term,
  termtail,
  sfactor,
  factor
};
const NonTerminal startSym = stmt;
const int error = -1;

//-- These are the grammar rules. -----------------//
const int rule[][10] = {
  { exp, STOP, -1 },             // Rule 0  (stmt)
  { term, exptail, -1 },         // Rule 1  (exp)
  { OPA, term, exptail, -1 },    // Rule 2  (exptail)
  { -1 },                        // Rule 3  (exptail)
  { sfactor, termtail, -1 },     // Rule 4  (term)
  { OPM, factor, termtail, -1 }, // Rule 5  (termtail)
  { -1 },                        // Rule 6  (termtail)
  { OPA, factor, -1 },           // Rule 7  (sfactor)
  { factor, -1 },                // Rule 8  (sfactor)
  { NUM, -1 },                   // Rule 9  (factor)
  { LP, exp, RP, -1 }            // Rule 10 (factor)
};

//-- parseTable[symbol][token-1] = predicted rule. --//
const int parseTable[][10] = {
  /*                NUM OPA OPM LP  RP  STOP */
  /* stmt     */ {   0,  0, -1,  0, -1, -1 },
  /* exp      */ {   1,  1, -1,  1, -1, -1 },
  /* exptail  */ {  -1,  2, -1, -1,  3,  3 },
  /* term     */ {   4,  4, -1,  4, -1, -1 },
  /* termtail */ {  -1,  6,  5, -1,  6,  6 },
  /* sfactor  */ {   8,  7, -1,  8, -1, -1 },
  /* factor   */ {   9, -1, -1, 10, -1, -1 }
};

static string toString(int a) {
  switch(a) {
  case NUM: return "NUM";
  case OPA: return "OPA";
  case OPM: return "OPM";
  case LP: return "LP";
  case RP: return "RP";
  case STOP: return "STOP"; }
}

int next = -1;

//-- Helper functions
void pperror(string msg = "Parse error!") { cerr << msg << endl; exit(1); }
int peek() { if (next == -1) next = yylex(); return next; }
void match(int tok) { 
  if (tok == peek()) next = -1; 
  else pperror(string("Error! Expected ") + toString(tok) 
	       + " found " + toString(peek())); 
}

//-- Table-driven parser ... pretty darn simple
void parse()
{
  stack<int> S;
  S.push(startSym);
  while(true)
  {
    int sym = S.top(); S.pop();
    if (sym < startSym)
    {
      match(sym); if (sym == STOP) return;
    }
    else
    {
      int action = parseTable[sym - startSym][peek()-1];
      if (action == error) pperror("Parse error!");
      int k = 0; while(rule[action][k] != -1) ++k;
      while(--k >= 0) S.push(rule[action][k]); 
    }
  }
}

int main() { while(peek()) parse(); }