C++ Expressions :: سیاوش نامه

I like to analyze the calculator in Expressions chapter of C++ Programming Language. The calculator is a tiny compiler actually so I think it is worth digging the idea behind its implementation. Here is the grammar for the input language like "10*2+3":

program:
	end //end is end-of-input
	expr_list end
expr_list:
	expression print // print is newline or semicolon
	expression print expr_list
expression:
	expression + term
	expression − term
	term
term:
	term / primary
	term ∗ primary
	primary
primary:
	number //number is a floating-point literal
	name //name is an identifier
	name = expression
	−primary
	( expression )

What is says is that we call whole input string a program. The program is consisting of end and expression_list. Now what is that: expression print [expression_list] in which the print is a character to mark the end of an expression like new line or semicolon. It says till now that a program may look like this:

"expression;expression;expression;"

It continues with defining what an expression is: a term or a term + or - an expression. A term is a primary or a primary + or - a term. What a primary is? It can be one of four things: a number, a name, a name=expression(and we know what an expression is already), -primary(negative of a primary) and an expression between parenthesis. According to this a number is a primary is a term and also an expression. If we add a semicolon it will be expr_list if our string is consisting of only this expr_list it is also a program.

So we give a string with this syntax to our program and the program calculates the results. Here is the implementation in C++:

#include
#include  // strings
#include  // map
#include  // isalpha(), etc.
#include 
#include 
using namespace std;
int no_of_errors;
map table;

double error(const string& s)
{
	no_of_errors++;
	cerr << "error: " << s << '\n';
	return 1;
}
enum class Kind : char {
	name, number, end,
	plus = '+', minus = '-', mul = '*', div = '/', print = ';', assign = '=', lp = '(', rp = ')'
};

struct Token {
	Kind kind;
	string string_value;
	double number_value;
};

class Token_stream {
public:
	Token_stream(istream& s) : ip{ &s }, owns{ false } { }
	Token_stream(istream* p) : ip{ p }, owns{ true } { }
	~Token_stream() { close(); }
	Token get(); // read and return next token
	Token& current() {		return ct;	}; // most recently read token
	void set_input(istream& s) { close(); ip = &s; owns = false; }
	void set_input(istream* p) { close(); ip = p; owns = true; }
private:
	void close() { if (owns) delete ip; }
	istream *ip; //pointer to an input stream
	bool owns; // does the Token_stream own the istream?
	Token ct{ Kind::end }; // current token
};

Token Token_stream::get()
{
	char ch = 0;
	*ip >> ch;
	switch (ch) {
	case 0:
		return ct = { Kind::end }; // assign and return
	case ';': // end of expression; print
	case '∗':
	case '/':
	case '+':
	case '-':
	case '(':
	case ')':
	case '=':
		return ct = {static_cast(ch)};
	case '0': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9':
	case '.':
		ip->putback(ch); //put the first digit (or .) back into the input stream
		*ip >> ct.number_value; // read number into ct
		ct.kind = Kind::number;
		return ct;
	default: //name, name =, or error
		if (isalpha(ch)) {
			ip->putback(ch); //put the first character back into the input stream
			*ip >> ct.string_value; // read string into ct
			ct.kind = Kind::name;
			return ct;
		}
		error("bad token");
		return ct = { Kind::print };
	}
}


Token_stream ts{ cin };

double expr(bool get);


double prim(bool get) // handle primaries
{
	if (get) ts.get(); // read next token
	switch (ts.current().kind) {
	case Kind::number: // floating-point constant
	{ 
		double v = ts.current().number_value;
		ts.get();
		return v;
	}
	case Kind::name:
	{ 
		double& v = table[ts.current().string_value]; // find the corresponding
		if (ts.get().kind == Kind::assign) v = expr(true); // ’=’ seen: assignment
		return v;
	}
	case Kind::minus: // unar y minus
		return -prim(true);
	case Kind::lp:
	{
		auto e = expr(true);
		if (ts.current().kind != Kind::rp) return error("')' expected");
		ts.get(); // eat ’)’
		return e;
	}
	default:
		return error("primary expected");
	}
}
double term(bool get) // multiply and divide
{
	double left = prim(get);
	for (;;) {
		switch (ts.current().kind) {
		case Kind::mul:
			left *= prim(true);
			break;
		case Kind::div:
			if (auto d = prim(true)) {
				left /= d;
				break;
			}
			return error("divide by 0");
		default:
			return left;
		}
	}
}

double expr(bool get) // add and subtract
{
	double left = term(get);
	for (;;) { // ‘‘forever’’
		switch (ts.current().kind) {
		case Kind::plus:
			left += term(true);
			break;
		case Kind::minus:
			left -= term(true);
			break;
		default:
			return left;
		}
	}
}

void calculate()
{
	for (;;) {
		ts.get();
		if (ts.current().kind == Kind::end) break;
		if (ts.current().kind == Kind::print) continue;
		cout << expr(false) << '\n';
	}
}

int main(int argc, char* argv[])
{
	switch (argc) {
	case 1: // read from standard input
		break;
	case 2: // read from argument string
		ts.set_input(new istringstream{ argv[1] });
		break;
	default:
		error("too many arguments");
		return 1;
	}
	table["pi"] = 3.1415926535897932385; // insert predefined names
	table["e"] = 2.7182818284590452354;
	calculate();
	return no_of_errors;
}

So lets look how it works. It simply has a function for each expression and breaks them down as grammar dictates. Real work starts in calculate(). It ts.get() to get the first token and calls expr(false) on it. false says don't read another token and handle the current one (as one is already read). expr() calls term on current token and term calls prim on it. This way expr() breaks down all strings to primary tokens. expr() goes ahead for all + and -s term() goes ahead for all * and /s and prim() goes ahead for numbers and names. expr() calls term(), term calls prim(). prim() handles neg, parenthesis numbers, and names. It calls expr() for whatever between the parenthesis. Term handles multiplications and divisions and returns the result to expr(). Look what happens for a string like this: 10+8/4-14.

Reads 10 and calls expr(). Our program knows the type of read token. In this case it is a number. expr() puts 10 in left an reads next token to see the next token is + or - by calling term() which consequently calls prim(). It calls term for the remaining part and adds or subtracts whatever is returned by term(). term returns numbers immediately after reading them.
term() is called when expr() says case Kind::plus: left += term(true);
term() reads the next token and sees it as a division so it calculates 8/4 and gives it to expr();
expr() adds it to the previous value. So now we have 12 - 14.
When expr() calls term() again in its loop it will get 14 and subtracts it from 12
This time the next token is not + nor - so expr() finishes by returning the result.

Now to see it graphically we have:

exp-------term-------prim

|>---------->---------->|

|<----10---<---10----<|

10+|>------>--------->|

|<---8---<|

8/|>------->|

8/|<---4---<|

10+|<--2--<|

12-|>------->--------->|

12-|<--14-<----14---<|

-2

۱ نظر

سیاوش کسروی

سیاوش نامه

سیاوش نامه

توضیحات در مورد موضوعات گسسته‌ای که من باهاشون سر و کار دارم از قبیل موسیقی، حسابداری، برنامه‌نویسی و اجتماع

مدیریت

فاویسم

ERP

موسیقی

برنامه نویسی

حسابداری

قوانین

مباحث نظری (تئوری)

۱ مطلب با کلمه‌ی کلیدی «C++ Expressions» ثبت شده است

Chapter 10 Expressions of C++ Programming Language of Stroustrap book

سیاوش نامه

سیاوش نامه

توضیحات در مورد موضوعات گسسته‌ای که من باهاشون سر و کار دارم از قبیل موسیقی، حسابداری، برنامه‌نویسی و اجتماع

مدیریت

فاویسم

ERP

موسیقی

برنامه نویسی

حسابداری

قوانین

مباحث نظری (تئوری)

programming

compiler

Stroustrap

C++ Expressions

C++

۱ مطلب با کلمه‌ی کلیدی «C++ Expressions» ثبت شده است

Chapter 10 Expressions of C++ Programming Language of Stroustrap book