https://rentry.org/PPP2_p192

// Code derived from Stroustrup's PPP2 book
// § 6.4 Grammars
//  -and beginning on p 192

//------------------------------------------------------------------------------
/*
                                      Parsing the expression 45 + 11.5 * 7
                                           (read from bottom up):

                                                 Expression
                                                      ^
  A simple expression grammar                         |
                                             ---------+---------------
                                             |        |              |
Expression:                              Expression   |              |
    Term                                     ^        |              |
    Expression "+" Term  // addition         |        |              |
    Expression "–" Term  // subtraction      |        |       -------+-------
                                             |        |       |      |      |
Term:                                      Term       |     Term     |      |
    Primary                                  ^        |       ^      |      |
    Term "*" Primary     // multiplication   |        |       |      |      |
    Term "/" Primary     // division         |        |       |      |      |
    Term "%" Primary     // remainder        |        |       |      |      |
                                             |        |       |      |      |
Primary:                                  Primary     |    Primary   |   Primary
    Number                                   ^        |       ^      |      ^
    "(" Expression ")"   // grouping         |        |       |      |      |
                                             |        |       |      |      |
Number:                                      |        |       |      |      |
    floating-point-literal                   |        |       |      |      |

                                             45       +      11.5    *      7

*/
//------------------------------------------------------------------------------

#include <iostream>

using std::cin;
using std::cout;

// a simple user-defined type
class Token {
 public:
  Token(char ch) : kind{ch} {}

  Token(char ch, double val) : kind{ch}, value{val} {}

  char   kind  = '0';
  double value = 0.0;
};

//------------------------------------------------------------------------------

// Note: we now need a Token 'putback' functionality, so we're introducing the
// Token_stream class to provide this capability.

class Token_stream {
 public:
  Token_stream();  // make a Token_stream that reads from cin

  Token get();             // get a Token
  void  putback(Token t);  // put a Token back

 private:
  bool  full;    // is there a Token in the buffer?
  Token buffer;  // here is where we keep a Token put back using putback()
};

// The constructor just sets full to indicate that the buffer is empty:
Token_stream::Token_stream() : full{false}, buffer{0}  // no Token in buffer
{
}

Token Token_stream::get()
{
  if (full) {  // do we already have a Token ready?
    // remove token from buffer:
    full = false;
    return buffer;
  }

  char ch;
  cin >> ch;  // note that >> skips whitespace (space, newline, tab, etc.)

  // clang-format off
  switch (ch) {
    case ';':    // for "print"
    case '+':
    case '*':
      return Token(ch);        // let each character represent itself
    case '.':
    case '1': case '4': case '5': case '7': {
      cin.putback(ch);  // put digit back into the input stream
      double val;
      cin >> val;              // read a floating-point number
      return Token('8', val);  // let '8' represent "a number"
    }
    default:
      return Token{'K'};  // 'K' is invalid
  }
  // clang-format on
}

// The putback() member function puts its argument back into the Token_stream's
// buffer:
void Token_stream::putback(Token t)
{
  buffer = t;     // copy t to buffer
  full   = true;  // buffer is now full
}

//------------------------------------------------------------------------------

double expression();  // addition only
double term();        // multiplication only
double primary();     // number only

Token_stream ts;  // provides get() and putback()

//------------------------------------------------------------------------------

// Note: this is a simplified (but working) example, to demonstrate the grammar
// call-chain involved in parsing the expression of these six tokens:
//
//     45 + 11.5 * 7 ;
//
// -the idea being to simplify function internals enough for comprehensibility

int main()
{
  cout << "enter:  45+11.5*7;  \n";

  cout << expression() << '\n';
}

double expression()
{
  double left = term();  // read and evaluate a Term

  Token t = ts.get();  // get the next Token from the Token stream

  while (true) {
    switch (t.kind) {  // see which kind of token that is
      case '+':
        left += term();  // evaluate a Term and add
        t = ts.get();
        break;
      default:
        ts.putback(t);  // put t back into the token stream
        return left;    // finally: no more +; return the answer
    }
  }
}

double term()
{
  double left = primary();  // read and evaluate a Primary

  Token t = ts.get();  // get the next Token from the Token stream

  while (true) {
    switch (t.kind) {  // see which kind of token that is
      case '*':
        left *= primary();  // evaluate a Primary and multiply
        t = ts.get();
        break;
      default:
        ts.putback(t);  // put t back into the Token stream
        return left;    // finally: no more *; return the answer
    }
  }
}

double primary()
{
  Token t = ts.get();  // get the next Token from the Token stream

  switch (t.kind) {
    case '8':          // we use '8' to represent a number
      return t.value;  // return the number's value
    default: return 0.0;
  }
}

build & run:

g++ -std=c++20 -O2 -Wall -pedantic ./ch_06/main_p192.cpp && ./a.out

PrevUpNext

Edit
Pub: 15 Mar 2023 20:37 UTC
Edit: 02 May 2023 20:48 UTC
Views: 1048