C 인터프리터 만들기 (2) - Lexer를 만들어보자

구현의 첫 단계로 Lexer를 만들어 볼 것이다.

 

참고로 C 인터프리터를 만들기에는 아직 불가능할 것 같으니, C의 교육용 언어인 C-- 언어를 기준으로 만들 것이며, 그 중에서도 간단한 문법만 지원하는 언어를 만들 것이다.

 

만들고자 하는 어휘 문법은 다음과 같다.

 

Lexical Rules

letter ::= a | b | … | z | A | B | … | Z (오직 알파벳만)

digit ::= 0 | 1 | …| 9 (정수형)

id ::= letter{ letter } (오직 알파벳만)

intcon ::= digit{digit}

 

(참고 : https://www2.cs.arizona.edu/~debray/Teaching/CSc453/DOCS/cminusminusspec.html )

 

• id는 1개 이상의 알파벳이 온다.
• intcon은 1개 이상의 정수형이 온다.

 

이것만 보면 어떻게 만들지 막막하니 좀 더 구현 내용을 구체화 해보겠다.

 

Lexer 구현 

목표 : Token 단위로 자를 수 있어야 한다.

Lexical Rules

letter ::= a | b | … | z | A | B | … | Z (오직 알파벳만)

digit ::= 0 | 1 | …| 9 (정수형)

id ::= letter{ letter } (오직 알파벳만)

intcon ::= digit{digit}

 

토큰 타입

• Identifier
• Int

id 확인

• ‘A’ ~ ‘z’ 사이인지 확인
• 문자끝날 때까지 확인
• TokenType = Indentifier, literal = “apple”

int 확인

• ‘0’ ~ ‘9’ 사이인지 확인
• 숫자 끝날 때까지 확인
• TokenType = Int, literal = “123”

 

C++로 구현하기

이렇게 해도 막막해서 "밑바닥부터 만드는 인터프리터 in Go"책을 참고했다. 책에 구현 내용 그대로 나와있어서 쉬울 줄 알았는데 C++과 Go 언어가 다소 달라서 꽤 어려웠다...

 

먼저 Lexer의 목표는 소스소드를 가지고 토큰 리스트를 만들어내는 것이다. 

소스코드 -> 토큰들

 

Token과 TokenType을 정의한다.

 

Token.h

#pragma once

#include "TokenType.h"
#include <iostream>
#include <string>

using namespace std;

struct Token {
	TokenType type = TokenType::NOTHING;
	string literal = "NOTHING";

	Token() = default;
	Token(TokenType t, string val) : type(t), literal(val) {}

	std::string toString() const {
		return "{Type: " + tokenTypeToString(type) + ", Literal: '" + literal + "'}";
	}
};

• 본인이 무슨 토큰인지 나타낼 수 있도록 TokenType을 멤버변수로 갖는다.
• 디버깅용, 테스트 용으로 내용 확인이 쉽도록 literal, toString() 을 구현한다.
  • tokenTypeToString()은 TokenType에서 구현

TokenType.h

#pragma once
#include <string>
#include <ostream>
#include <map>
using namespace std;
enum class TokenType {
	IDENT,
	INTCON,
	INT_TYPE,
	VOID,
	EOFILE,
	RETURN,

	// Operators
	ASSIGN,		// '-'
	PLUS,		// '+'
	MINUS,		// '-'
	ASTERISK,	// '*'
	SLASH,		// '/'

	// Delimiters
	SEMICOLON,	// ';'
	COMMA,		// ','

	LPAREN,	// '('
	RPAREN, // ')'
	LBRACK, // '['
	RBRACK, // ']'
	LBRACE,	// '{'
	RBRACE,	// '}'

	UNKNOWN,
	NOTHING,
};

inline std::string tokenTypeToString(TokenType type) {
	switch (type) {
	case TokenType::INT_TYPE:  return "INT_TYPE";
	case TokenType::VOID:      return "VOID";
	case TokenType::RETURN:    return "RETURN";
	case TokenType::ASSIGN:    return "ASSIGN";
	case TokenType::PLUS:      return "PLUS";
	case TokenType::MINUS:     return "MINUS";
	case TokenType::ASTERISK:  return "ASTERISK";
	case TokenType::SLASH:     return "SLASH";
	case TokenType::SEMICOLON: return "SEMICOLON";
	case TokenType::COMMA:     return "COMMA";
	case TokenType::LPAREN:    return "LPAREN";
	case TokenType::RPAREN:    return "RPAREN";
	case TokenType::LBRACK:    return "LBRACK";
	case TokenType::RBRACK:    return "RBRACK";
	case TokenType::LBRACE:    return "LBRACE";
	case TokenType::RBRACE:    return "RBRACE";
	case TokenType::IDENT:     return "IDENT";
	case TokenType::INTCON:    return "INTCON";
	case TokenType::EOFILE:    return "EOFILE";
	case TokenType::UNKNOWN:   return "UNKNOWN";
	default:                   return "UNKNOWN";
	}
}

• 사용할 토큰 타입들을 enum 클래스로 정의한다. 위는 최종 버전. 처음에는 토큰 5개 정도만 있어도 됨

이제 필요한 자료 타입들은 다 만들어졌다. 이제부터 본격적으로 lexer를 구현해보자

 

Lexer.h

#pragma once
#include "Token.h"
#include <unordered_map>
using namespace std;

class Lexer {
private:
	string input;
	int position;	
	int readPosition;
	char ch;		

	
public:
	Lexer(string input);
	virtual ~Lexer();
	Token nextToken();
	std::string getChar();
	std::vector<Token> tokenizeAll();
	
private:
	void readChar();
	char peekChar();
	string readIdentifier();
	string readNumber();
	TokenType LookupIdent(const string& ident);
	void skipWithSpace();

	bool isDigit(char ch);
	bool isLetter(char ch);

	static const unordered_map<string, TokenType> keywords;
	
};

• 전체 lexer.h이다.

 

멤버 변수

private:
	string input;
	int position;	
	int readPosition;	
	char ch;

• input : 전체 소스코드 문자열
• position : 현재 문자를 가리키는 인덱스
• readPosition : 다음 문자를 가리키는 인덱스
• ch : 현재 문자

함수들은 lexer.cpp를 보면서 하나하나 알아보자

 

lexer.cpp

#include "Lexer.h"
#include "TokenType.h"
#include <iostream>

using namespace std;
Lexer::Lexer(string input)
	: input(input), position(0), readPosition(0), ch(input[0]) {
	readChar();
}

Lexer::~Lexer() = default;

const unordered_map<string, TokenType> Lexer::keywords = {
	{"int", TokenType::INT_TYPE},
	{"void", TokenType::VOID},
	{"return", TokenType::RETURN},
};

string Lexer::getChar() {
	if (readPosition >= input.length()) {
		return ""; // 'NUL' - 아무것도 읽지 않은 상태, EOF 의미
	}
	else {
		return input.substr(readPosition, 1);
	}
}

void Lexer::readChar() {
	if (readPosition >= input.length()) {
		ch = 0; // 'NUL' - 아무것도 읽지 않은 상태, EOF 의미
	}
	else {
		ch = input[readPosition];
	}
	position = readPosition;
	readPosition += 1;
	//cout << "readChar() : " << ch << std::endl;
}

char Lexer::peekChar() {
	if (readPosition + 1 >= input.length()) {
		return 0; // 'NUL' - 아무것도 읽지 않은 상태, EOF 의미
	}
	return input[readPosition + 1];

}

std::vector<Token> Lexer::tokenizeAll() {
	std::vector<Token> tokens;

	while (true) {
		Token tok = nextToken();
		tokens.push_back(tok);
		if (tok.type == TokenType::UNKNOWN || tok.type == TokenType::EOFILE) {
			break;
		}
	}
	return tokens;
}
Token Lexer::nextToken() {
	Token token;

	skipWithSpace();
	switch (this->ch) {
	case 0:
		token = Token(TokenType::EOFILE, "");
		break;
	case '=':
		token = Token(TokenType::ASSIGN, "=");
		break;
	case '+':
		token = Token(TokenType::PLUS, "+");
		break;
	case '-':
		token = Token(TokenType::MINUS, "-");
		break;
	case '*':
		token = Token(TokenType::ASTERISK, "*");
		break;
	case '/':
		if (peekChar() != '/' && peekChar() != '\n') {
			while (ch != '\n' && ch != EOF && ch != NULL) {
				readChar();
			}
			token = nextToken();
		}
		else {
			token = Token(TokenType::SLASH, "/");
		}
		break;
	case ';':
		token = Token(TokenType::SEMICOLON, ";");
		break;
	case ',':
		token = Token(TokenType::COMMA, ",");
		break;
	case '(':
		token = Token(TokenType::LPAREN, "(");
		break;
	case ')':
		token = Token(TokenType::RPAREN, ")");
		break;
	case '[':
		token = Token(TokenType::LBRACK, "[");
		break;
	case ']':
		token = Token(TokenType::RBRACK, "]");
		break;
	case '{':
		token = Token(TokenType::LBRACE, "{");
		break;
	case '}':
		token = Token(TokenType::RBRACE, "}");
		break;
	default:
		if (isLetter(ch)) {
			string literal = readIdentifier();
			token = Token(LookupIdent(literal), literal);
		}
		else if(isDigit(ch)){
			token = Token(TokenType::INTCON, readNumber());
		}
		else {
			token = Token(TokenType::UNKNOWN, getChar());
		}
		return token;
	}

	readChar();
	return token;
}

void Lexer::skipWithSpace() {
	while (ch == ' ' || ch == '\t' || ch == '\n' || ch == '\r') {
		readChar();
	}
}

string Lexer::readIdentifier() {
	int position = this->position;
	while (isLetter(ch)) {
		readChar();
	}
	return input.substr(position, this->position - position);
}

string Lexer::readNumber() {
	int position = this->position;
	while (isDigit(ch)) {
		readChar();
	}
	return input.substr(position, this->position - position);
}

TokenType Lexer::LookupIdent(const string& ident) {
	auto it = keywords.find(ident);
	if (it != keywords.end()) {
		return it->second;
	}
	return TokenType::IDENT;
}

bool Lexer::isDigit(char ch) {
	return (ch >= '0' && ch <= '9');
}

bool Lexer::isLetter(char ch) {
	return (ch >= 'A' && ch <= 'Z') || ( ch >= 'a' && ch <= 'z');
}

최종 lexer.cpp이다.

 

nextToken()

lexer에서 가장 중요한 함수이다. 외부에서는 오직 nexetToken()만 호출하며, 토큰화를 진행한다.

Token Lexer::nextToken() {
	Token token;

	skipWithSpace();
	switch (this->ch) {
	case 0:
		token = Token(TokenType::EOFILE, "");
		break;
	case '=':
		token = Token(TokenType::ASSIGN, "=");
		break;
        
      ....
      default:
		if (isLetter(ch)) {
			string literal = readIdentifier();
			token = Token(LookupIdent(literal), literal);
		}
		else if(isDigit(ch)){
			token = Token(TokenType::INTCON, readNumber());
		}
		else {
			token = Token(TokenType::UNKNOWN, getChar());
		}
		return token;
    } // end of switch...
    
    readChar();
	return token;
      
}

수행 로직

• 현재 문자를 확인하고, 적합한 Token을 만들어서 반환한다. Token을 만들고나면 다음 문자를 가리키도록 한다.

로직자체는 간단하지만, 까다로운 부분들이 있다. 바로 토큰을 구성하는 문자가 1개가 아닐 때이다. '+', '=', '{' 같은 기호들은 토큰을 구성하는 문자가 오직 1개이니깐 현재 문자만 확인하면 된다.

 

하지만 'apple' ,' 1993' 와 같은 id와 정수들은 끝이나는 부분까지 적절하게 잘라야 한다. 구현은 간단하다. 알파벳일 경우 현재 문자가 알파벳일 때까지 전진시키면되고, 숫자일 경우 현재 문자가 숫자일 때까지 전진 시키면 된다.

 

lexer.cpp 일부

string Lexer::readIdentifier() {
	int position = this->position;
	while (isLetter(ch)) {
		readChar();
	}
	return input.substr(position, this->position - position);
}

string Lexer::readNumber() {
	int position = this->position;
	while (isDigit(ch)) {
		readChar();
	}
	return input.substr(position, this->position - position);
}

bool Lexer::isDigit(char ch) {
	return (ch >= '0' && ch <= '9');
}

bool Lexer::isLetter(char ch) {
	return (ch >= 'A' && ch <= 'Z') || ( ch >= 'a' && ch <= 'z');
}

 

사실 이 로직은 identity의 어휘 규칙이 오로직 문자로만 이루졌기에 가능하긴 하다. 

 

 

```int main() { return 42; }```

소스코드를 토큰화 시키면 아래와 같이 토큰으로 잘라진다. 

 

 

 

 

전체 코드는 git 참고!

https://github.com/ujkkk/Interpreter

GitHub - ujkkk/Interpreter