이번에는 수식 파서 트리를 이용한 계산기의 어휘 분석기와 구문 분석기를 구현해 보아요.
먼저 어휘분석기를 구현합시다.
class Lexer
{
어휘분석기에서는 수식을 입력받아 토큰을 생성합니다. 토큰을 보관하는 컬렉션을 멤버 필드로 선언하세요.
Tokens tokens;
수식을 입력받아 토큰을 생성하는 메서드를 추가하세요. 토큰 생성 과정에서 수식에 오류가 없는지 여부를 반환하세요.
public:
bool MakeToken(const char *expr);
생성한 토큰을 보관한 컬렉션을 제공하는 메서드를 추가하세요.
Tokens GetTokens()const;
동적으로 생성한 토큰들을 소멸하기 위해 소멸자가 필요합니다.
~Lexer(); };
수식을 입력받아 토큰을 생성하는 메서드를 구현합시다.
bool Lexer::MakeToken(const char *expr)
{
이전에 생성했던 토큰들을 지우세요.
tokens.clear();
수식 문자열이 종료 문자(‘\0’, 널문자, 아스키 코드 값이 0인 문자)를 만날 때까지 반복합니다.
int i = 0;
while(expr[i])
{
만약 현재 문자가 연산자에 사용하는 문자인지 판별합니다.
if(Operator::IsOperator(expr[i]))
{
연산자에 사용하는 문자면 연산자 토큰을 생성하여 컬렉션에 추가하세요.
tokens.push_back(new Operator(expr[i]));
연산자는 단일 문자가 토큰이므로 다음 토큰 위치는 i를 1 증가한 위치입니다.
i++;
}
만약 현재 문자가 연산자에 사용하는 문자가 아니면 숫자 문자인지 판별합니다.
else
{
if(Operand::IsDigit(expr[i]))
{
숫자 문자일 때는 해당 위치에서의 문자열을 정수로 변환후에 피연산자 토큰 생성 및 컬렉션에 추가하세요.
int value = Operand::ConvertStrToInt(expr,i);
tokens.push_back(new Operand(value));
}
연산자에 사용하는 문자도 숫자 문자도 아니면 잘못 사용한 어휘가 있는 것이므로 거짓을 반환하세요.
else
{
return false;
}
}
}
종료 문자까지 분석하였다면 잘못 사용한 어휘가 없는 것이므로 참을 반환하세요.
return true; }
토큰 컬렉션을 제공하는 접근자 메서드를 구현하세요.
Tokens Lexer::GetTokens()const
{
return tokens;
}
소멸자를 구현합시다.
Lexer::~Lexer()
{
컬렉션의 모든 요소를 반복자를 이용하여 방문하세요.
TIter seek = tokens.begin();
TIter last = tokens.end();
for( ;seek != last; ++seek)
{
반복자가 가리키는 위치의 토큰을 소멸하세요.
delete (*seek);
}
}
구문 분석기를 구현합시다.
class SynAnalyzer
{
구문 분석기에서는 생성한 토큰들이 적절한 순서인지 판별하는 기능만 필요하여 정적 메서드로 추가하세요.
static bool Analyze(Tokens tokens); };
구문 분석기 소스 코드에 토큰의 순서가 적절한지 판별하는 Analyze 메서드를 구현하세요.
bool SynAnalyzer::Analyze(Tokens tokens)
{
먼저 컬렉션에 보관한 토큰 개수를 구하세요.
int tcnt = tokens.size();
여기에서 계산할 수 있는 수식은 언제나 토큰 개수가 홀수여야 합니다.
if(tcnt%2==0)
{
return false;
}
첫 번째 토큰은 언제나 피연산자여야 합니다.
<expr>:= <operand><mid expr>*
if(Operand::IsOperand(tokens[0])==false)
{
return false;
}
그리고 피연산자와 연산자로 구성한 중간 표현이 반복해서 올 수 있습니다.
<expr>:= <operand><mid expr>*
for(int i = 1; i<tcnt; i+=2)
{
중간 표현은 연산자와 피연산자 순으로 와야 합니다.
<mid expr>:=<operator><operand>
if(Operator::IsOperator(tokens[i])==false)
{
return false;
}
if(Operand::IsOperand(tokens[i+1])==false)
{
return false;
}
}
중간에 오류가 없다면 참을 반환하세요.
return true; }