구현의 첫 단계로 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
Contribute to ujkkk/Interpreter development by creating an account on GitHub.
github.com