[C++] 계산기 만들기 (1) parser

부동 소수점 숫자에 대한 중위 연산자로 네 가지 표준 산술 연산을 제공하는 간단한 탁상용 계산기 프로그램을 만들어보자. 사용자는 변수를 정의할 수도 있다. 예를 들어 주어진 입력

r = 2.5
area = pi ∗ r ∗ r

(pi는 미리 정의됨) 계산기 프로그램은 다음과 같은 결과를 보여 줍니다.

2.5
19.635

여기서 2.5는 첫 번째 입력 라인의 결과이고 19.635는 두 번째 라인의 결과다.

 

이 계산기는 네 개의 메인 파트로 구성된다. (parser, 입력 함수, 기호 테이블, driver). 실제로 이것은 구문 분석기가 구문 분석을 수행하고 입력 기능이 입력 및 어휘 분석을 처리하며 기호 테이블이 영구 정보를 보유하고 driver가 초기화, 출력 및 오류를 처리하는 소형 컴파일러다. 더 유용하게 만들기 위해 계산기에 많은 기능을 추가할 수 있지만 코드는 그대로 충분히 길며 대부분의 기능은 C++ 사용에 대한 추가 통찰력을 제공하지 않는 코드를 추가할 것이다.

The Parser

다음은 계산기에 허용되는 언어의 문법이다.

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
	− primar y
	( expression )

즉, 프로그램은 세미콜론으로 구분된 일련의 표현식이다. 표현식의 기본 단위는 숫자, 이름 및 연산자 *, /, +, -(단항 및 이진 모두) 및 =(할당)이다. 이름은 사용 전에 선언할 필요가 없다.

재귀 하강(recursive descent)이라는 구문 분석 스타일을 사용하자. 대중적이고 직접적인 하향식 기술이다. 함수 호출이 상대적으로 간단한 C++와 같은 언어에서 효율적이다. 문법의 각 생성에 대해 다른 함수를 호출하는 함수가 있다. 터미널 기호 (예:end, number, + 및 -)는 어휘 분석기에 의해 인식되고 non-터미널 기호는 구문 분석기 함수인 expr(), term() 및 print()에 의해 인식된다. (하위) 표현식의 두 피연산자가 모두 알려지자마자 표현식은 분석된다. 실제 컴파일러에서는 이 시점에서 코드가 생성될 수 있다.

입력의 경우 parser는 문자 읽기 및 해당 구성을 토큰으로 캡슐화하는 Token_stream을 사용한다. 즉, Token_stream은 "토큰화" : 123.45와 같은 문자 스트림을 토큰으로 바꾼다. 토큰은 123.45가 부동 소수점 값으로 변환된 {숫자, 123.45}와 같은 {토큰 종류, 값} 쌍이다. parser의 주요 부분은 다음만 알아두면 된다. Token_stream의 이름, ts 및 토큰을 얻는 방법. 다음 토큰을 읽기 위해 ts.get()을 호출한다. 가장 최근에 읽은 토큰("현재 토큰")을 가져오기 위해 ts.current()를 호출한다. 토큰화를 제공하는 것 외에도 Token_stream은 문자의 실제 소스를 숨긴다. cin에 입력하는 사용자, 프로그램 명령줄 또는 다른 입력 스트림에서 직업 올 수 있음을 알 수 있다.

토큰의 정의는 다음과 같다.

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;
};

각 토큰을 해당 문자의 정수 값으로 나타내는 것은 편리하고 효율적이며 디버거를 사용하는 사람들에게 도움이 될 수 있다. 이것은 입력으로 사용된 문자에 열거자로 사용된 값이 없고 내가 아는 현재 문자 집합에 한 자리 정수 값이 있는 인쇄 문자가 없는 한 작동한다.

Token_stream에 대한 인터페이스는 다음과 같다.

class Token_stream {
public:
	Token get(); // read and return next token
	const Token& current(); // most recently read token
	// ...
};

각 parser 함수는 다음 토큰을 가져오기 위해 함수가 Token_stream:get()을 호출해야 하는지 여부를 나타내는 get이라는 bool 인수를 사용한다. 각 parser 함수는 '그것의' 표현식을 평가하고 값을 반환한다. expr() 함수는 덧셈과 뺄셈을 처리한다. 더하거나 뺄 용어를 찾는 단일 루프로 구성된다.

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;
		}
	}
}

이 기능은 실제로 자체적으로 많은 작업을 수행하지 않는다. 큰 프로그램의 고수준 함수의 일반적인 방식으로 작업을 수행하기 위해 다른 함수를 호출한다.

2-3+4와 같은 표현식은 문법에 지정된 대로 (2-3)+4로 평가된다.

for(;;)는 무한 루프를 지정하는 방법이며 while(true)의 대안이다. switch문은 + 및 -와 다른 것을 찾을 대까지 반복적으로 실행된 다음 default case의 return문이 실행된다.

 

함수 term()은 곱셈과 나눗셈을 expr()이 덧셈과 뺄셈을 처리하는 것과 같은 방식으로 처리한다.

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;
		}
	}
}

0으로 나눈 결과는 예외 처리를 해주어야 한다. 따라서 나누기 전에 0을 확인하고 0이 감지되면 error()를 호출해야 한다.  호출 계층 구조에서 점점 낮아지고 있기 때문에 약간의 실제 작업이 수행되고 있고 루프가 필요하지 않다는 점을 제외하면 prim() 함수는 expr() 및 term()과 매우 유사하다. 

double prim(bool get) // handle primar ies
{
	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");
	}
}

숫자(즉, 정수 또는 부동 소수점 리터럴)인 토큰이 표시되면 해당 값은 number_value에 배치된다. 마찬가지로 이름인 토콘이 표시되면 해당 값은 string_value에 배치된다. prim()은 항상 기본 표현식을 분석하는 데 사용하는 것보다 하나 더 많은 토큰을 읽는다. 그 이유는 어떤 경우에는 그렇게 해야 하기 때문에 (예:이름이 할당되었는지 확인하기 위해) 일관성을 위해 모든 경우에 수행해야 한다. parser 함수가 단순히 다음 토큰으로 이동하려는 경우 ts.get()의 반환 값을 사용하지 않는다. ts.current()에서 결과를 얻을 수 있기 때문이다. 

이름에 어떤 작업을 수행하기 전에 계산기는 먼저 이름이 지정되어 있는지 또는 단순히 읽히는지 확인해야 한다. 두 경우 모두 기호 테이블을 참조한다. 

map<string,double> table;

즉, 테이블이 문자열로 인덱싱 될 때 결과 값은 문자열에 해당하는 double이다. 예를 들어 사용자가 다음을 입력하면,

radius = 6378.388;

계산기는 case Kind::name에 도달하고 실행한다.

double& v = table["radius"];
// ... expr() calculates the value to be assigned ...
v = 6378.388;

참조 v는 radius와 관련된 double을 유지하는 데 사용되는 반명 expr()은 입력 문자에 값 6378.388을 계산한다.