1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

/* SI 413 Fall 2012
 * This is a table-driven top-down parser for the calculator language.
 *
 * Here is the grammar:
        stmt -> exp STOP
         exp -> term exptail
     exptail -> OPA term exptail| e
        term -> factor termtail
    termtail -> OPM factor termtail | e
      factor -> NUM | LP exp RP
 */
#include <iostream>
#include <cstdlib>
#include <string>
#include <stack>
#include "bisoncalc.tab.hpp"
using namespace std;
 
 
/**************************************
 * Non-terminals are 
 * numbered consecutively from startSym
 * up, where startSym is some number
 * greater than any token number.
 **************************************/
enum NonTerminal {
  stmt=500,
  exp,
  exptail,
  term,
  termtail,
  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)
  { factor, termtail, -1 },      // Rule 4  (term)
  { OPM, factor, termtail, -1 }, // Rule 5  (termtail)
  { -1 },                        // Rule 6  (termtail)
  { NUM, -1 },                   // Rule 7  (factor)
  { LP, exp, RP, -1 }            // Rule 8  (factor)
};
 
//-- parseTable[symbol][token] = 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 },
  /* factor   */ {   7, -1, -1,  8, -1, -1 }
};
 
int next = -1;
 
//-- Helper functions
 
int yylex();
 
void perror(const char* msg) { 
  cerr << "Parse error: " << msg << endl; 
  exit(1); 
}
 
int peek() { 
  if (next == -1) 
    next = yylex(); 
  return next; 
}
 
void match(int tok) { 
  if (tok == peek()) 
    next = -1; 
  else 
    perror("match");
}
 
//-- 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()-NUM];
      if (action == error) perror("Non-terminal expansion");
      int k = 0; 
      while(rule[action][k] != -1) ++k;
      while(--k >= 0) S.push(rule[action][k]); 
    }
  }
}
 
int main() { 
  while (true) {
    cout << "> " << flush;
    if (peek() == 0) break;
    parse(); 
  }
  cout << endl;
  return 0;
}