// g++ --std=c++11 expParser.cpp
#include <iostream>
#include <string>
#include <vector>
#include <memory>
using namespace std;
// Utility stuff
// Haskell's Maybe
template<typename T>
class Optional {
bool b;
T val;
public:
Optional() : b(false) {}
Optional(T v) : val(v), b(true) {}
bool isJust() { return b; }
bool isNothing() { return !b; }
T fromJust() { return val; }
};
template<typename T>
Optional<T> nothing() {
return Optional<T>();
}
template<typename T>
Optional<T> just(T v) {
return Optional<T>(v);
}
typedef enum {
EOS, // End of string
ZERO,
ONE,
TWO,
OPEN,
CLOSE,
PLUS,
MULT
} Token_t;
string showTok(Token_t t) {
switch(t) {
case EOS: return "EOS";
case ZERO: return "ZERO";
case ONE: return "ONE";
case TWO: return "TWO";
case OPEN: return "OPEN";
case CLOSE: return "CLOSE";
case PLUS: return "PLUS";
case MULT: return "MULT";
}
// NOTE: The (clang) compiler is able to figure out that
// along all control-flow paths, a return statement will be reached.
}
class Tokenize {
string s;
int pos;
public:
Tokenize(string s) {
this->s = s;
pos = 0;
}
// Scan throuh string, letter (symbol) by letter.
Token_t next() {
if(s.length() <= pos)
return EOS;
while(1) {
if(s.length() <= pos)
return EOS;
switch(s[pos]) {
case '0': pos++;
return ZERO;
case '1': pos++;
return ONE;
case '2': pos++;
return TWO;
case '(': pos++;
return OPEN;
case ')': pos++;
return CLOSE;
case '+': pos++;
return PLUS;
case '*': pos++;
return MULT;
default: // we simply skip all other symbols !
pos++;
break;
}
}
} // next
vector<Token_t> scan() {
vector<Token_t> v;
Token_t t;
do {
t = next();
v.push_back(t);
}
while(t != EOS);
return v;
} // scan
string show() {
vector<Token_t> v = this->scan();
string s;
for(int i=0; i < v.size(); i++) {
s += showTok(v[i]);
if(i+1 < v.size())
s += ";" ; // Add delimiter
}
return s;
} // show
};
// Wrapper class, provide the (current) token.
class Tokenizer : Tokenize {
public:
Token_t token;
Tokenizer(string s) : Tokenize(s) { token = next(); }
void nextToken() {
token = next();
}
};
void testTokenize() {
// Tokenize t1("1 + (3 * 4)");
{
Tokenize t1(" 1 + (0 * 1)");
cout << t1.show() << endl;
}
{
Tokenize t1("");
cout << t1.show() << endl;
}
}
// Exp AST
class Exp {
public:
virtual int eval() = 0;
virtual string pretty() = 0;
};
class IntExp : public Exp {
int val;
public:
IntExp(int _val) { val = _val; }
int eval() { return val;}
string pretty() {
return to_string(val);
}
};
class PlusExp : public Exp {
std::shared_ptr<Exp> e1;
std::shared_ptr<Exp> e2;
public:
PlusExp(std::shared_ptr<Exp> _e1, std::shared_ptr<Exp> _e2) {
e1 = _e1; e2 = _e2;
}
int eval() { return e1->eval() + e2->eval(); }
string pretty() {
string s("(");
s.append(e1->pretty());
s.append("+");
s.append(e2->pretty());
s.append(")");
return s;
}
};
class MultExp : public Exp {
std::shared_ptr<Exp> e1;
std::shared_ptr<Exp> e2;
public:
MultExp(std::shared_ptr <Exp> _e1, std::shared_ptr<Exp> _e2) {
e1 = _e1; e2 = _e2;
}
int eval() { return e1->eval() * e2->eval(); }
string pretty() {
string s("(");
s.append(e1->pretty());
s.append("*");
s.append(e2->pretty());
s.append(")");
return s;
}
};
// Short-hands
typedef std::shared_ptr<Exp> EXP;
EXP newInt(int i) {
return std::make_shared<IntExp>(i);
}
EXP newPlus(EXP l, EXP r) {
return std::make_shared<PlusExp>(l,r);
}
EXP newMult(EXP l, EXP r) {
return std::make_shared<MultExp>(l,r);
}
// Now comes the parser (OO-style)
class Parser {
Tokenizer t;
// E ::= T E'
Optional<EXP> parseE() {
Optional<EXP> t = parseT();
if(t.isNothing())
return t;
return parseE2(t.fromJust());
}
// E' ::= + T E' |
Optional<EXP> parseE2(EXP left) {
if(t.token == PLUS) {
t.nextToken();
Optional<EXP> right = parseT();
if(right.isNothing())
return right;
return parseE2(newPlus(left, right.fromJust()));
}
return just<EXP>(left);
}
// T ::= F T'
Optional<EXP> parseT() {
Optional<EXP> f = parseF();
if(f.isNothing())
return f;
return parseT2(f.fromJust());
}
// T' ::= * F T' |
Optional<EXP> parseT2(EXP left) {
if(t.token == MULT) {
t.nextToken();
Optional<EXP> right = parseF();
if(right.isNothing())
return right;
return parseT2(newMult(left, right.fromJust()));
}
return just<EXP>(left);
}
// F ::= N | (E)
Optional<EXP> parseF() {
switch(t.token) {
case ZERO:
t.nextToken();
return just<EXP>(newInt(0));
case ONE:
t.nextToken();
return just<EXP>(newInt(1));
case TWO:
t.nextToken();
return just<EXP>(newInt(2));
case OPEN: { // introduce new scope
t.nextToken();
Optional<EXP> e = parseE();
if(e.isNothing())
return e;
if(t.token != CLOSE)
return nothing<EXP>();
t.nextToken();
return e; }
default: return nothing<EXP>();
}
}
public:
Parser(string s) : t(Tokenizer(s)) { }
Optional<EXP> parse() {
Optional<EXP> e= parseE();
return e;
}
};
void display(Optional<EXP> e) {
if(e.isNothing()) {
cout << "nothing \n";
} else {
cout << (e.fromJust())->pretty() << "\n";
}
return;
}
void testParserGood() {
/*
display(Parser("1").parse());
display(Parser("1 + 0 ").parse());
display(Parser("1 + (0) ").parse());
display(Parser("1 + 2 * 0 ").parse());
display(Parser("1 * 2 + 0 ").parse());
*/
display(Parser("(1 + 2) * 0 ").parse());
display(Parser("(1 + 2) * 0 + 2").parse());
display(Parser("(1 + 2) * 0 + 2").parse());
}
void testParser() {
testParserGood();
}
int main() {
std::shared_ptr<Exp> e = std::make_shared<IntExp>(5);
testParser();
return 1;
}
// g++ --std=c++11 expParser.cpp
#include <iostream>
#include <string>
#include <vector>
#include <memory>
using namespace std;
// Utility stuff
// Haskell's Maybe
template<typename T>
class Optional {
bool b;
T val;
public:
Optional() : b(false) {}
Optional(T v) : val(v), b(true) {}
bool isJust() { return b; }
bool isNothing() { return !b; }
T fromJust() { return val; }
};
template<typename T>
Optional<T> nothing() {
return Optional<T>();
}
template<typename T>
Optional<T> just(T v) {
return Optional<T>(v);
}
typedef enum {
EOS, // End of string
ZERO,
ONE,
TWO,
OPEN,
CLOSE,
PLUS,
MULT
} Token_t;
string showTok(Token_t t) {
switch(t) {
case EOS: return "EOS";
case ZERO: return "ZERO";
case ONE: return "ONE";
case TWO: return "TWO";
case OPEN: return "OPEN";
case CLOSE: return "CLOSE";
case PLUS: return "PLUS";
case MULT: return "MULT";
}
// NOTE: The (clang) compiler is able to figure out that
// along all control-flow paths, a return statement will be reached.
}
class Tokenize {
string s;
int pos;
public:
Tokenize(string s) {
this->s = s;
pos = 0;
}
// Scan throuh string, letter (symbol) by letter.
Token_t next() {
if(s.length() <= pos)
return EOS;
while(1) {
if(s.length() <= pos)
return EOS;
switch(s[pos]) {
case '0': pos++;
return ZERO;
case '1': pos++;
return ONE;
case '2': pos++;
return TWO;
case '(': pos++;
return OPEN;
case ')': pos++;
return CLOSE;
case '+': pos++;
return PLUS;
case '*': pos++;
return MULT;
default: // we simply skip all other symbols !
pos++;
break;
}
}
} // next
vector<Token_t> scan() {
vector<Token_t> v;
Token_t t;
do {
t = next();
v.push_back(t);
}
while(t != EOS);
return v;
} // scan
string show() {
vector<Token_t> v = this->scan();
string s;
for(int i=0; i < v.size(); i++) {
s += showTok(v[i]);
if(i+1 < v.size())
s += ";" ; // Add delimiter
}
return s;
} // show
};
// Wrapper class, provide the (current) token.
class Tokenizer : Tokenize {
public:
Token_t token;
Tokenizer(string s) : Tokenize(s) { token = next(); }
void nextToken() {
token = next();
}
};
void testTokenize() {
// Tokenize t1("1 + (3 * 4)");
{
Tokenize t1(" 1 + (0 * 1)");
cout << t1.show() << endl;
}
{
Tokenize t1("");
cout << t1.show() << endl;
}
}
// Exp AST
class Exp {
public:
virtual int eval() = 0;
virtual string pretty() = 0;
};
class IntExp : public Exp {
int val;
public:
IntExp(int _val) { val = _val; }
int eval() { return val;}
string pretty() {
return to_string(val);
}
};
class PlusExp : public Exp {
std::shared_ptr<Exp> e1;
std::shared_ptr<Exp> e2;
public:
PlusExp(std::shared_ptr<Exp> _e1, std::shared_ptr<Exp> _e2) {
e1 = _e1; e2 = _e2;
}
int eval() { return e1->eval() + e2->eval(); }
string pretty() {
string s("(");
s.append(e1->pretty());
s.append("+");
s.append(e2->pretty());
s.append(")");
return s;
}
};
class MultExp : public Exp {
std::shared_ptr<Exp> e1;
std::shared_ptr<Exp> e2;
public:
MultExp(std::shared_ptr <Exp> _e1, std::shared_ptr<Exp> _e2) {
e1 = _e1; e2 = _e2;
}
int eval() { return e1->eval() * e2->eval(); }
string pretty() {
string s("(");
s.append(e1->pretty());
s.append("*");
s.append(e2->pretty());
s.append(")");
return s;
}
};
// Short-hands
typedef std::shared_ptr<Exp> EXP;
EXP newInt(int i) {
return std::make_shared<IntExp>(i);
}
EXP newPlus(EXP l, EXP r) {
return std::make_shared<PlusExp>(l,r);
}
EXP newMult(EXP l, EXP r) {
return std::make_shared<MultExp>(l,r);
}
// Syntax Analyse
/*
"1 + 2" ===Parsing==> als Object vom Typ "Exp"
Grammatikregeln zur Beschreibung
der syntaktisch wohlgeformten Ausdruecke.
In Mathe Notation. Grammatikregeln = Ersetzungsregeln.
E -> 1
E -> 2
E -> E + E
1, 2, + sind Terminalsymbole (atomaren Konstrukte der Programmiersprache)
E ist ein Nichtterminalsymbol.
In Informatiknotation, wir verwenden EBNF.
E := 1 | 2 | E + E | E * E
Ziel:
Aus obigen Regeln generiere ein Problem,
welches ueberpruft ob eine Sequenz bestend aus 1,2 und +
ein gueltiger Ausdruck ist, d.h. ableitbar aus E.
1 + 2 * 2 ist dies gueltig?
Wir versuchen eine Ableitung zu konstruieren.
1 + 2 * 2
<- E + 2 * 2
<- E + E * 2
(a)
<- E * 2
<- E * E
<- E
(b)
<- E + E * E
<- E + E
< E
Interpretation (a) entspricht (1+2)*2
Interpretation (b) entspricht 1 + (2*2)
Wir entscheiden uns fuer (b).
*/
// Now comes the parser (OO-style)
//
// Top-down parser.
// Kann automatisiert werden siehe https://www.antlr.org/
class Parser {
Tokenizer t;
// E ::= T E'
Optional<EXP> parseE() {
Optional<EXP> t = parseT();
if(t.isNothing())
return t;
return parseE2(t.fromJust());
}
// E' ::= + T E' |
Optional<EXP> parseE2(EXP left) {
if(t.token == PLUS) {
t.nextToken();
Optional<EXP> right = parseT();
if(right.isNothing())
return right;
return parseE2(newPlus(left, right.fromJust()));
}
return just<EXP>(left);
}
// T ::= F T'
Optional<EXP> parseT() {
Optional<EXP> f = parseF();
if(f.isNothing())
return f;
return parseT2(f.fromJust());
}
// T' ::= * F T' |
Optional<EXP> parseT2(EXP left) {
if(t.token == MULT) {
t.nextToken();
Optional<EXP> right = parseF();
if(right.isNothing())
return right;
return parseT2(newMult(left, right.fromJust()));
}
return just<EXP>(left);
}
// F ::= N | (E)
Optional<EXP> parseF() {
switch(t.token) {
case ZERO:
t.nextToken();
return just<EXP>(newInt(0));
case ONE:
t.nextToken();
return just<EXP>(newInt(1));
case TWO:
t.nextToken();
return just<EXP>(newInt(2));
case OPEN: { // introduce new scope
t.nextToken();
Optional<EXP> e = parseE();
if(e.isNothing())
return e;
if(t.token != CLOSE)
return nothing<EXP>();
t.nextToken();
return e; }
default: return nothing<EXP>();
}
}
public:
Parser(string s) : t(Tokenizer(s)) { }
Optional<EXP> parse() {
Optional<EXP> e= parseE();
return e;
}
};
void display(Optional<EXP> e) {
if(e.isNothing()) {
cout << "nothing \n";
} else {
cout << (e.fromJust())->pretty() << "\n";
}
return;
}
void testParserGood() {
/*
display(Parser("1").parse());
display(Parser("1 + 0 ").parse());
display(Parser("1 + (0) ").parse());
display(Parser("1 + 2 * 0 ").parse());
display(Parser("1 * 2 + 0 ").parse());
*/
display(Parser("(1 + 2) * 0 ").parse());
display(Parser("(1 + 2) * 0 + 2").parse());
display(Parser("(1 + 2) * 0 + 2").parse());
}
void testParser() {
testParserGood();
}
int main() {
std::shared_ptr<Exp> e = std::make_shared<IntExp>(5);
testParser();
return 1;
}
