# 微型计算器 项目

## 语言设计

• C像浮点数（常数）
• C像标识符（变量）
• 一元运算符 `+``-`
• 二元运算符 `+``-``*``/`
• 括号 `()`
• 分号 `;` （标记表达式的结尾，强制性）。

OP的具体示例将适用于此语言并添加分号：

``a*(b+3);``

## 抽象语法树

``````// storage of variables

class Var {
private:
double _value;
public:
Var(): _value() { }
~Var() = default;
double get() const { return _value; }
void set(double value) { _value = value; }
};``````

``typedef std::map<std::string, Var> VarTable;``

``````// abstract syntax tree -> storage of "executable"

namespace AST {

class Expr {
protected:
Expr() = default;
public:
virtual ~Expr() = default;
public:
virtual double solve() const = 0;
};

class ExprConst: public Expr {
private:
double _value;
public:
ExprConst(double value): Expr(), _value(value) { }
virtual ~ExprConst() = default;
virtual double solve() const { return _value; }
};

class ExprVar: public Expr {
private:
Var *_pVar;
public:
ExprVar(Var *pVar): Expr(), _pVar(pVar) { }
virtual ~ExprVar() = default;
virtual double solve() const { return _pVar->get(); }
};

class ExprUnOp: public Expr {
protected:
Expr *_pArg1;
protected:
ExprUnOp(Expr *pArg1): Expr(), _pArg1(pArg1) { }
virtual ~ExprUnOp() { delete _pArg1; }
};

class ExprUnOpNeg: public ExprUnOp {
public:
ExprUnOpNeg(Expr *pArg1): ExprUnOp(pArg1) { }
virtual ~ExprUnOpNeg() = default;
virtual double solve() const
{
return -_pArg1->solve();
}
};

class ExprBinOp: public Expr {
protected:
Expr *_pArg1, *_pArg2;
protected:
ExprBinOp(Expr *pArg1, Expr *pArg2):
Expr(), _pArg1(pArg1), _pArg2(pArg2)
{ }
virtual ~ExprBinOp() { delete _pArg1; delete _pArg2; }
};

public:
ExprBinOpAdd(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
virtual double solve() const
{
return _pArg1->solve() + _pArg2->solve();
}
};

class ExprBinOpSub: public ExprBinOp {
public:
ExprBinOpSub(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
virtual ~ExprBinOpSub() = default;
virtual double solve() const
{
return _pArg1->solve() - _pArg2->solve();
}
};

class ExprBinOpMul: public ExprBinOp {
public:
ExprBinOpMul(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
virtual ~ExprBinOpMul() = default;
virtual double solve() const
{
return _pArg1->solve() * _pArg2->solve();
}
};

class ExprBinOpDiv: public ExprBinOp {
public:
ExprBinOpDiv(Expr *pArg1, Expr *pArg2): ExprBinOp(pArg1, pArg2) { }
virtual ~ExprBinOpDiv() = default;
virtual double solve() const
{
return _pArg1->solve() / _pArg2->solve();
}
};``````

``````VarTable varTable;
Expr *pExpr
= new ExprBinOpMul(
new ExprVar(&varTable["a"]),
new ExprVar(&varTable["b"]),
new ExprConst(3)));``````

``double result = pExpr->solve();``

## 语法

``````program
: expr Semicolon program
| <empty>
;

expr
;

;

| <empty>
;

: Plus | Minus
;

mulExpr
: unaryExpr mulExprRest
;

mulExprRest
: mulOp unaryExpr mulExprRest
| <empty>
;

mulOp
: Star | Slash
;

unaryExpr
: unOp unaryExpr
| primExpr
;

unOp
: Plus | Minus
;

primExpr
: Number
| Id
| LParen expr RParen
;``````

• 终端符号（以大写字母开头）和
• 非终端符号（以小写字母开头）
• 冒号（:)将左侧与右侧分开（左侧的非终端可以扩展到右侧的符号）。
• 垂直条（ `|` ）来分隔替代品
• 一个 `<empty>` 符号，用于扩展为 `<empty>` （用于终止递归）。

`addExpr``mulExpr` 的分离是故意完成的。 因此，乘法运算符优先于加法运算符将会“烧毁”语法本身。 显然，括号中的浮点常量，变量标识符或表达式（在 `primExpr` 中接受）将具有最高优先级。

## 扫描仪

``````// token class - produced in scanner, consumed in parser
struct Token {
// tokens
enum Tk {
Plus, Minus, Star, Slash, LParen, RParen, Semicolon,
Number, Id,
EOT, Error
};
// token number
Tk tk;
// lexem as floating point number
double number;
// lexem as identifier
std::string id;

// constructors.
explicit Token(Tk tk): tk(tk), number() { }
explicit Token(double number): tk(Number), number(number) { }
explicit Token(const std::string &id): tk(Id), number(), id(id) { }
};``````

• `EOT` ...文本结束（注释输入结束）
• `Error` ...为任何不适合任何其他令牌的字符生成。

``````// the scanner - groups characters to tokens
class Scanner {
private:
std::istream &_in;
public:
// constructor.
Scanner(std::istream &in): _in(in) { }
/* groups characters to next token until the first character
* which does not match (or end-of-file is reached).
*/
Token scan()
{
char c;
// skip white space
do {
} while (isspace(c));
// classify character and build token
switch (c) {
default:
if (isdigit(c)) {
_in.unget(); double value; _in >> value;
} else if (isalpha(c) || c == '_') {
std::string id(1, c);
while (_in >> c) {
if (isalnum(c) || c == '_') id += c;
else { _in.unget(); break; }
}
} else {
_in.unget();
}
}
}
};``````

## 解析器

``````class Parser {
private:
Scanner _scanner;
VarTable &_varTable;

private:
// constructor.
Parser(std::istream &in, VarTable &varTable):
{
}

void scan() { _lookAhead = _scanner.scan(); }

// consumes a specific token.
bool match(Token::Tk tk)
{
std::cerr << "SYNTAX ERROR! Unexpected token!" << std::endl;
return false;
}
scan();
return true;
}

// the rules:

std::vector<AST::Expr*> parseProgram()
{
// right recursive rule
// -> can be done as iteration
std::vector<AST::Expr*> pExprs;
for (;;) {
if (AST::Expr *pExpr = parseExpr()) {
pExprs.push_back(pExpr);
} else break;
// special error checking for missing ';' (usual error)
std::cerr << "SYNTAX ERROR: Semicolon expected!" << std::endl;
break;
}
scan(); // consume semicolon
if (_lookAhead.tk == Token::EOT) return pExprs;
}
// error handling
for (AST::Expr *pExpr : pExprs) delete pExpr;
pExprs.clear();
return pExprs;
}

AST::Expr* parseExpr()
{
}

{
if (AST::Expr *pExpr1 = parseMulExpr()) {
} else return nullptr; // ERROR!
}

{
// right recursive rule for left associative operators
// -> can be done as iteration
for (;;) {
case Token::Plus:
scan(); // consume token
if (AST::Expr *pExpr2 = parseMulExpr()) {
} else {
delete pExpr1;
return nullptr; // ERROR!
}
break;
case Token::Minus:
scan(); // consume token
if (AST::Expr *pExpr2 = parseMulExpr()) {
pExpr1 = new AST::ExprBinOpSub(pExpr1, pExpr2);
} else {
delete pExpr1;
return nullptr; // ERROR!
}
break;
case Token::Error:
std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
delete pExpr1;
return nullptr;
default: return pExpr1;
}
}
}

AST::Expr* parseMulExpr()
{
if (AST::Expr *pExpr1 = parseUnExpr()) {
return parseMulExprRest(pExpr1);
} else return nullptr; // ERROR!
}

AST::Expr* parseMulExprRest(AST::Expr *pExpr1)
{
// right recursive rule for left associative operators
// -> can be done as iteration
for (;;) {
case Token::Star:
scan(); // consume token
if (AST::Expr *pExpr2 = parseUnExpr()) {
pExpr1 = new AST::ExprBinOpMul(pExpr1, pExpr2);
} else {
delete pExpr1;
return nullptr; // ERROR!
}
break;
case Token::Slash:
scan(); // consume token
if (AST::Expr *pExpr2 = parseUnExpr()) {
pExpr1 = new AST::ExprBinOpDiv(pExpr1, pExpr2);
} else {
delete pExpr1;
return nullptr; // ERROR!
}
break;
case Token::Error:
std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
delete pExpr1;
return nullptr;
default: return pExpr1;
}
}
}

AST::Expr* parseUnExpr()
{
// right recursive rule for right associative operators
// -> must be done as recursion
case Token::Plus:
scan(); // consume token
// as a unary plus has no effect it is simply ignored
return parseUnExpr();
case Token::Minus:
scan();
if (AST::Expr *pExpr = parseUnExpr()) {
return new AST::ExprUnOpNeg(pExpr);
} else return nullptr; // ERROR!
default:
return parsePrimExpr();
}
}

AST::Expr* parsePrimExpr()
{
AST::Expr *pExpr = nullptr;
case Token::Number:
scan(); // consume token
break;
case Token::Id: {
Var &var = _varTable[_lookAhead.id]; // find or create
pExpr = new AST::ExprVar(&var);
scan(); // consume token
} break;
case Token::LParen:
scan(); // consume token
if (!(pExpr = parseExpr())) return nullptr; // ERROR!
if (!match(Token::RParen)) {
delete pExpr; return nullptr; // ERROR!
}
break;
case Token::EOT:
std::cerr << "SYNTAX ERROR: Premature EOF!" << std::endl;
break;
case Token::Error:
std::cerr << "SYNTAX ERROR: Unexpected character!" << std::endl;
break;
default:
std::cerr << "SYNTAX ERROR: Unexpected token!" << std::endl;
}
return pExpr;
}

public:

// the parser function
static std::vector<AST::Expr*> parse(
std::istream &in, VarTable &varTable)
{
Parser parser(in, varTable);
return parser.parseProgram();
}
};``````

``static std::vector<AST::Expr*> Parser::parse();``

• 左侧的每个非终端变为解析功能。 （仔细观察源代码，你会发现我并没有完全这样做。有些规则已被“内联”了。 - 从我的观点来看，我插入了一些额外的规则来简化我所做的语法。我打算从头开始改造。抱歉。）

• 替代（ `|` ）实现为 `switch (_lookAhead.tk)` 。 因此，每个案例标签对应于最左边的符号可以扩展到的第一终端（令牌）。 （我相信这就是为什么它被称为“前瞻解析器” - 应用规则的决定总是基于前瞻标记完成。）龙书有一个关于FIRST-FOLLOW集的主题，它更详细地解释了这一点。

• 对于终端符号，调用 `Parser::scan()` 。 在特殊情况下，如果只需要一个终端（令牌），它将被 `Parser::match()` 取代。

• 对于非终端符号，完成相应功能的调用。

• 符号序列简单地作为上述调用的序列完成。

## 放在一起

``````// a sample application

using namespace std;

int main()
{
// the program:
const char *sourceCode =
"1 + 2 * 3 / 4 - 5;\n"
"a + b;\n"
"a - b;\n"
"a * b;\n"
"a / b;\n"
"a * (b + 3);\n";
// the variables
const char *vars[] = { "a", "b" };
enum { nVars = sizeof vars / sizeof *vars };
// the data
const double data[][nVars] = {
{ 4.0, 2.0 },
{ 2.0, 4.0 },
{ 10.0, 5.0 },
{ 42, 6 * 7 }
};
// compile program
stringstream in(sourceCode);
VarTable varTable;
vector<AST::Expr*> program = Parser::parse(in, varTable);
if (program.empty()) {
cerr << "ERROR: Compile failed!" << endl;
string line;
if (getline(in, line)) {
cerr << "Text at error: '" << line << "'" << endl;
}
return 1;
}
// apply program to the data
enum { nDataSets = sizeof data / sizeof *data };
for (size_t i = 0; i < nDataSets; ++i) {
const char *sep = "";
cout << "Data Set:" << endl;
for (size_t j = 0; j < nVars; ++j, sep = ", ") {
cout << sep << vars[j] << ": " << data[i][j];
}
cout << endl;
for (size_t j = 0; j < nVars; ++j) varTable[vars[j]].set(data[i][j]);
// perform program
cout << "Compute:" << endl;
istringstream in(sourceCode);
for (const AST::Expr *pExpr : program) {
string line; getline(in, line);
cout << line << ": " << pExpr->solve() << endl;
}
cout << endl;
}
// clear the program
for (AST::Expr *pExpr : program) delete pExpr;
program.clear();
// done
return 0;
}``````

``````Data Set:
a: 4, b: 2
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: 2
a * b;: 8
a / b;: 2
a * (b + 3);: 20

Data Set:
a: 2, b: 4
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 6
a - b;: -2
a * b;: 8
a / b;: 0.5
a * (b + 3);: 14

Data Set:
a: 10, b: 5
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 15
a - b;: 5
a * b;: 50
a / b;: 2
a * (b + 3);: 80

Data Set:
a: 42, b: 42
Compute:
1 + 2 * 3 / 4 - 5;: -2.5
a + b;: 84
a - b;: 0
a * b;: 1764
a / b;: 1
a * (b + 3);: 1890``````

## 完整样本

...可以在 ideone 上找到源代码和测试运行。

``````\$ cd cparse
\$ make release``````