황새: C++로 프로그래밍 언어를 만드는 방법

게시 됨: 2022-03-11

1부: 토큰나이저

이 시리즈에서는 새로운 스크립팅 언어를 개발하고 해당 프로세스를 단계별로 설명합니다.

궁금해하는 독자의 마음에 자연스럽게 떠오르는 첫 번째 질문은 아마도 "우리에게 새로운 프로그래밍 언어가 정말로 필요한가?"일 것입니다.

새로운 프로그래밍 언어가 정말로 필요한가?

이 질문에 답하기 위해 약간의 실례를 허용하겠습니다.

당신이 건축가(소프트웨어가 아닌 실제 벽돌과 박격포 건축가)이고 매우 관료적인 국가에서 태어날 만큼 운이 좋지 않다고 상상해 보십시오. 당신은 개발이 덜 된 고향에 쇼핑몰에 대한 좋은 아이디어가 있어서 프로젝트를 만들고 건축 허가를 신청합니다. 물론 등록된 회사가 없다는 이유로 즉시 거절합니다. 그래서 회사를 등록합니다. 그렇게 하기 위해서는 약간의 돈을 예치해야 합니다. 그런 다음 거부된 회사 이름을 생각해냅니다. 다섯 번째 시도에서 승인되고 애플리케이션이 힙의 맨 아래로 이동합니다. 결국 포기하거나 그 사이에 다른 사람이 쇼핑몰을 만들었다는 사실을 깨닫게 됩니다.

그러나 우리는 진정한 건축가가 아닙니다. 우리는 소프트웨어 엔지니어이며 허가나 관료주의 없이 아이디어를 실현할 수 있는 특권이 있습니다. 우리에게 필요한 유일한 것은 여가 시간과 스도쿠 퍼즐 대신 프로그래밍에 사용할 의지입니다.

프로그래밍에 대한 동기가 순수한 호기심이 아니라고 여전히 주장하신다면, 제가 처음으로 디자인한 프로그래밍 언어는 단순한 호기심이 아니라 필요에 의해 개발되었다는 점을 말씀드리겠습니다. 그러나 이것이 이 블로그를 읽는 첫 번째 동기가 되어서는 안 됩니다. 여기에서 접하게 될 많은 아이디어는 실제로 자신의 프로그래밍 언어를 만들 필요가 없더라도 계속 관심을 가질 수 있도록 상당히 흥미롭고 혁신적이라고 생각합니다.

작은 공간을 차지하는 스크립팅 언어를 개발하려는 우리의 목표는 저에게 영감을 주어 "Stork"라는 이름을 지었습니다. 운 좋게도 우리는 그 이름을 승인하기 위해 어떤 관료도 설득할 필요가 없습니다.

시리즈를 진행하면서 프로그래밍 언어를 개발할 예정이므로 일부 버그도 개발할 가능성이 있습니다. 우리가 시리즈의 끝에 가까워지면 그것들을 다림질해야 합니다.

여기에 설명된 모든 것에 대한 완전한 소스 코드는 GitHub에서 무료로 사용할 수 있습니다.

마지막으로 이 단락 제목의 질문에 답하기 위해 — 아니요, 실제로 새로운 프로그래밍 언어가 필요하지는 않지만 C++로 프로그래밍 언어를 만드는 방법을 보여 주려고 하므로 데모용으로 만들 것입니다. .

Tokenizer의 작은 도우미

다른 프로그래머가 정기적으로 같은 문제에 직면하는지 모르겠지만 저는 이 문제에 매우 자주 직면합니다.

로그 시간에 값을 빠르게 검색해야 하는 키-값 컨테이너가 필요합니다. 그러나 컨테이너를 초기화하면 새 값을 추가하고 싶지 않습니다. 따라서 std::map<Key, Value> (또는 std::unordered_map<Key, Value> )는 빠른 삽입도 허용하므로 과도합니다.

불필요한 최적화에 대해서는 전적으로 반대하지만, 이 경우에는 쓸데없이 많은 메모리가 낭비되는 느낌이 듭니다. 뿐만 아니라 나중에 우리는 그러한 컨테이너 위에 최대 munch 알고리즘을 구현해야 하며 map 은 이에 대한 최상의 컨테이너가 아닙니다.

두 번째 선택은 삽입 후 정렬된 std::vector<std::pair<Key,Value> > 입니다. 이 접근 방식의 유일한 문제는 벡터가 정렬된다는 점을 염두에 두어야 하기 때문에 코드 가독성이 낮다는 것입니다. 그래서 저는 그 제약을 보장하는 작은 클래스를 개발했습니다.

(모든 함수, 클래스 등은 네임스페이스 stork 에 선언되어 있습니다. 가독성을 위해 해당 네임스페이스는 생략하겠습니다.)

 template <typename Key, typename Value> class lookup { public: using value_type = std::pair<Key, Value>; using container_type = std::vector<value_type>; private: container_type _container; public: using iterator = typename container_type::const_iterator; using const_iterator = iterator; lookup(std::initializer_list<value_type> init) : _container(init) { std::sort(_container.begin(), _container.end()); } lookup(container_type container) : _container(std::move(container)) { std::sort(_container.begin(), _container.end()); } const_iterator begin() const { return _container.begin(); } const_iterator end() const { return _container.end(); } template <typename K> const_iterator find(const K& key) const { const_iterator it = std::lower_bound( begin(), end(), key, [](const value_type& p, const K& key) { return p.first < key; } ); return it != end() && it->first == key ? it : end(); } size_t size() const { return _container.size(); } };

보시다시피 이 클래스의 구현은 매우 간단합니다. 가능한 모든 방법을 구현하고 싶지는 않고 필요한 방법만 구현했습니다. 기본 컨테이너는 vector 이므로 미리 채워진 vector 또는 initializer_list 로 초기화할 수 있습니다.

토크나이저는 입력 스트림에서 문자를 읽습니다. 프로젝트의 이 단계에서는 입력 스트림이 무엇인지 결정하기 어렵기 때문에 대신 std::function 을 사용하겠습니다.

 using get_character = std::function<int()>;

파일의 끝을 알리는 음수뿐 아니라 char 대신 int 를 반환하는 getc 와 같은 C 스타일 스트림 함수의 잘 알려진 규칙을 사용할 것입니다.

그러나 토크나이저에서 토큰 유형을 가정하기 전에 몇 개의 문자를 미리 읽는 것이 정말 편리합니다. 이를 위해 일부 문자를 읽지 않을 수 있는 스트림을 구현했습니다.

 class push_back_stream { private: const get_character& _input; std::stack<int> _stack; size_t _line_number; size_t _char_index; public: push_back_stream(const get_character& input); int operator()(); void push_back(int c); size_t line_number() const; size_t char_index() const; };

공간을 절약하기 위해 내 GitHub 페이지에서 찾을 수 있는 구현 세부 정보는 생략하겠습니다.

보시다시피 push_back_stream 은 get_character 함수에서 초기화됩니다. 오버로드된 operator() 는 다음 문자를 검색하는 데 사용되며 push_back 은 문자를 스트림으로 다시 반환하는 데 사용됩니다. line_number 및 char_number 는 오류 보고에 사용되는 편의 메소드입니다.

char_index 는 현재 줄에 있는 문자의 인덱스가 아니라 전체에 대한 인덱스임을 명심하십시오. 그렇지 않으면 push_back 기능을 올바르게 구현하기 위해 일부 컨테이너에 모든 과거 문자를 보관해야 합니다.

예약된 토큰

토크나이저는 가장 낮은 수준의 컴파일러 구성 요소입니다. 입력 및 "spit-out" 토큰을 읽어야 합니다. 우리가 관심을 갖는 토큰에는 네 가지 유형이 있습니다.

예약된 토큰
식별자
숫자
문자열

우리는 댓글에 관심이 없으므로 토크나이저는 아무에게도 알리지 않고 그냥 "먹습니다".

이 언어의 매력과 인기를 보장하기 위해 잘 알려진 C와 유사한 구문을 사용합니다. C, C++, JavaScript, Java, C# 및 Objective-C에서 잘 작동했으므로 Stork에서도 작동해야 합니다. 복습 과정이 필요한 경우 C/C++ 학습 리소스를 다루는 이전 기사 중 하나를 참조할 수 있습니다.

다음은 예약된 토큰 목록입니다.

 enum struct reserved_token { inc, dec, add, sub, concat, mul, div, idiv, mod, bitwise_not, bitwise_and, bitwise_or, bitwise_xor, shiftl, shiftr, assign, add_assign, sub_assign, concat_assign, mul_assign, div_assign, idiv_assign, mod_assign, and_assign, or_assign, xor_assign, shiftl_assign, shiftr_assign, logical_not, logical_and, logical_or, eq, ne, lt, gt, le, ge, question, colon, comma, semicolon, open_round, close_round, open_curly, close_curly, open_square, close_square, kw_if, kw_else, kw_elif, kw_switch, kw_case, kw_default, kw_for, kw_while, kw_do, kw_break, kw_continue, kw_return, kw_var, kw_fun, kw_void, kw_number, kw_string, };

"kw_" 접두사가 붙은 열거형 멤버는 키워드입니다. 일반적으로 C++ 키워드와 동일하므로 접두사를 붙여야 했습니다. 접두사가 없는 것은 연산자입니다.

거의 대부분이 C 규칙을 따릅니다. 그렇지 않은 것은 다음과 같습니다.
- 연결에 사용되는 concat 및 concat_assign ( .. 및 ..= )
- 정수 나누기에 사용되는 idiv 및 idiv_assign ( \ 및 \= )
- 변수 선언을 위한 kw_var
- 함수 선언을 위한 kw_fun
- 숫자 변수의 경우 kw_number
- 문자열 변수의 경우 kw_string

필요에 따라 키워드를 추가할 것입니다.

설명할 가치가 있는 새로운 키워드가 하나 있습니다: kw_elif . 나는 (중괄호가 없는) 단일 문장 블록은 가치가 없다고 굳게 믿습니다. 나는 두 가지 경우를 제외하고는 그것들을 사용하지 않습니다.

for , while , 또는 if 문 바로 뒤에 실수로 세미콜론을 눌렀을 때. 운이 좋다면 컴파일 시간 오류를 반환하지만 때로는 더미 if 문과 항상 실행되는 블록이 발생합니다. 다행스럽게도 몇 년 동안 나는 실수로부터 배웠기 때문에 그런 일은 거의 일어나지 않습니다. 파블로프의 개도 결국 배웠습니다.
if 문을 "연결"하면 if 블록이 있고 그 다음에는 하나 이상의 else-if-블록이 있으며 선택적으로 else 블록이 있습니다. 엄밀히 말하면, 내가 else if 를 작성할 때 그것은 단 하나의 문이 있는 else 블록입니다. 바로 그 if 문입니다.

따라서 elif 를 사용하여 중괄호 없는 문을 완전히 제거할 수 있습니다. 우리가 그것을 허용할지 여부는 지금은 기다릴 수 있는 결정입니다.

예약된 토큰을 반환하는 두 가지 도우미 함수가 있습니다.

 std::optional<reserved_token> get_keyword(std::string_view word); std::optional<reserved_token> get_operator(push_back_stream& stream);

get_keyword 함수는 전달된 단어에서 선택적 키워드를 반환합니다. 해당 "단어"는 문자 또는 밑줄로 시작하는 문자, 숫자 및 밑줄의 시퀀스입니다. 단어가 키워드인 경우 reserved_token 을 반환합니다. 그렇지 않으면 토크나이저는 그것이 식별자라고 가정합니다.

함수 get_operator 는 시퀀스가 유효한 연산자인 한 가능한 한 많은 문자를 읽으려고 합니다. 더 많이 읽으면 가장 오래 인식된 연산자 다음에 읽은 모든 추가 문자를 읽지 않습니다.

이 두 함수를 효과적으로 구현하려면 string_view 와 reserved_keyword 사이에 두 번의 조회가 필요합니다.

 const lookup<std::string_view, reserved_token> operator_token_map { {"++", reserved_token::inc}, {"--", reserved_token::dec}, {"+", reserved_token::add}, {"-", reserved_token::sub}, {"..", reserved_token::concat}, /*more exciting operators*/ }; const lookup<std::string_view, reserved_token> keyword_token_map { {"if", reserved_token::kw_if}, {"else", reserved_token::kw_else}, {"elif", reserved_token::kw_elif}, {"switch", reserved_token::kw_switch}, {"case", reserved_token::kw_case}, {"default", reserved_token::kw_default}, {"for", reserved_token::kw_for}, {"while", reserved_token::kw_while}, {"do", reserved_token::kw_do}, {"break", reserved_token::kw_break}, {"continue", reserved_token::kw_continue}, {"return", reserved_token::kw_return}, {"var", reserved_token::kw_var}, {"fun", reserved_token::kw_fun}, {"void", reserved_token::kw_void}, {"number", reserved_token::kw_number}, {"string", reserved_token::kw_string} };

get_keyword 구현은 완전히 간단하지만 get_operator 의 경우 n번째 문자만 고려하여 주어진 문자를 후보 연산자와 비교하는 사용자 지정 비교기가 필요합니다.

 class maximal_munch_comparator{ private: size_t _idx; public: maximal_munch_comparator(size_t idx) : _idx(idx) { } bool operator()(char l, char r) const { return l < r; } bool operator()( std::pair<std::string_view, reserved_token> l, char r ) const { return l.first.size() <= _idx || l.first[_idx] < r; } bool operator()( char l, std::pair<std::string_view, reserved_token> r ) const { return r.first.size() > _idx && l < r.first[_idx]; } bool operator()( std::pair<std::string_view, reserved_token> l, std::pair<std::string_view, reserved_token> r ) const { return r.first.size() > _idx && ( l.first.size() < _idx || l.first[_idx] < r.first[_idx] ); } };

이것은 idx 위치의 문자만 고려하는 일반적인 어휘 비교기이지만 문자열이 더 짧으면 다른 문자보다 작은 idx 위치에 null 문자가 있는 것처럼 취급합니다.

이것은 maximal_munch_operator 클래스를 더 명확하게 만들어야 하는 get_operator 의 구현입니다.

 std::optional<reserved_token> get_operator(push_back_stream& stream) { auto candidates = std::make_pair( operator_token_map.begin(), operator_token_map.end() ); std::optional<reserved_token> ret; size_t match_size = 0; std::stack<int> chars; for (size_t idx = 0; candidates.first != candidates.second; ++idx) { chars.push(stream()); candidates = std::equal_range( candidates.first, candidates.second, char(chars.top()), maximal_munch_comparator(idx) ); if ( candidates.first != candidates.second && candidates.first->first.size() == idx + 1 ) { match_size = idx + 1; ret = candidates.first->second; } } while (chars.size() > match_size) { stream.push_back(chars.top()); chars.pop(); } return ret; }

기본적으로 처음에는 모든 운영자를 후보로 취급합니다. 그런 다음 문자별로 읽고 equal_range 를 호출하여 n번째 문자만 비교하여 현재 후보를 필터링합니다. 앞의 문자는 이미 비교되어 있으므로 비교할 필요가 없고, 뒤에 오는 문자는 여전히 관련이 없으므로 비교하고 싶지 않습니다.

범위가 비어 있지 않을 때마다 범위의 첫 번째 요소에 더 이상 문자가 없는지 확인합니다(이러한 요소가 존재하는 경우 조회가 정렬될 때 항상 범위의 시작 부분에 있음). 이 경우 일치하는 법적 연산자가 있습니다. 가장 긴 연산자는 우리가 반환하는 연산자입니다. 우리는 그 후에 결국 읽는 모든 문자를 읽지 않을 것입니다.

토크나이저

토큰은 이기종이므로 토큰은 std::variant 다른 토큰 유형을 래핑하는 편의 클래스입니다. 즉:

예약 토큰
식별자
숫자
끈
파일 끝

 class token { private: using token_value = std::variant<reserved_token, identifier, double, std::string, eof>; token_value _value; size_t _line_number; size_t _char_index; public: token(token_value value, size_t line_number, size_t char_index); bool is_reserved_token() const; bool is_identifier() const; bool is_number() const; bool is_string() const; bool is_eof() const; reserved_token get_reserved_token() const; std::string_view get_identifier() const; double get_number() const; std::string_view get_string() const; size_t get_line_number() const; size_t get_char_index() const; };

identifier 는 std::string 유형의 단일 멤버가 있는 클래스일 뿐입니다. 제 생각에는 모든 대안이 다른 유형인 경우 std::variant 가 더 깨끗하기 때문에 편의를 위해 존재합니다.

이제 토크나이저를 작성할 수 있습니다. push_back_stream 을 수락하고 다음 토큰을 반환하는 하나의 함수가 될 것입니다.

트릭은 우리가 읽은 첫 번째 문자의 문자 유형에 따라 다른 코드 분기를 사용하는 것입니다.

파일 끝 문자를 읽으면 함수에서 반환됩니다.
공백을 읽으면 건너 뜁니다.
영숫자 문자(문자, 숫자 또는 밑줄)를 읽는 경우 해당 유형의 모든 연속 문자를 읽습니다(첫 문자가 숫자인 경우 점도 읽음). 그런 다음 첫 번째 문자가 숫자이면 시퀀스를 숫자로 구문 분석하려고 시도합니다. 그렇지 않으면 get_keyword 함수를 사용하여 키워드 또는 식별자인지 확인합니다.
인용 부호를 읽으면 이스케이프 문자를 이스케이프 처리하지 않은 문자열로 처리합니다.
슬래시 문자( / )를 읽으면 다음 문자가 슬래시인지 별표( * )인지 확인하고 이 경우 줄/블록 주석을 건너뜁니다.
그렇지 않으면 get_operator 함수를 사용합니다.

다음은 토큰화 기능 구현입니다. 호출하는 함수의 구현 세부정보는 생략하겠습니다.

 token tokenize(push_back_stream& stream) { while (true) { size_t line_number = stream.line_number(); size_t char_index = stream.char_index(); int c = stream(); switch (get_character_type(c)) { case character_type::eof: return {eof(), line_number, char_index}; case character_type::space: continue; case character_type::alphanum: stream.push_back(c); return fetch_word(stream); case character_type::punct: switch (c) { case '"': return fetch_string(stream); case '/': { char c1 = stream(); switch(c1) { case '/': skip_line_comment(stream); continue; case '*': skip_block_comment(stream); continue; default: stream.push_back(c1); } } default: stream.push_back(c); return fetch_operator(stream); } break; } } }

하위 수준 함수를 호출하기 전에 읽은 문자를 다시 푸시하는 것을 볼 수 있습니다. 성능 저하가 거의 없으며 하위 수준 기능 코드가 훨씬 깨끗합니다.

예외

예외에 대한 그의 호언장담 중 하나에서 내 형제는 언젠가 이렇게 말했습니다.

“예외를 던지는 사람과 예외를 잡아야 하는 사람, 두 종류의 사람이 있습니다. 나는 항상 그 슬픈 두 번째 그룹에 속해 있습니다.”

나는 그 말의 정신에 동의한다. 저는 특히 예외를 좋아하지 않으며 예외를 던지면 코드를 유지 관리하고 읽기가 훨씬 더 어려워질 수 있습니다. 거의 언제나.

나는 그 규칙에 예외(나쁜 말장난)를 하기로 결정했습니다. 컴파일 깊이에서 긴장을 풀기 위해 컴파일러에서 예외를 throw하는 것이 정말 편리합니다.

다음은 예외 구현입니다.

 class error: public std::exception { private: std::string _message; size_t _line_number; size_t _char_index; public: error(std::string message, size_t line_number, size_t char_index) noexcept; const char* what() const noexcept override; size_t line_number() const noexcept; size_t char_index() const noexcept; };

그러나 최상위 코드에서 모든 예외를 포착할 것을 약속합니다. 예쁜 인쇄를 위해 line_number 및 char_index 멤버와 이를 수행하는 함수도 추가했습니다.

 void format_error( const error& err, get_character source, std::ostream& output );

마무리

이것으로 시리즈의 첫 번째 부분을 마칩니다. 그다지 흥미롭지는 않았지만 이제 기본 구문 분석 오류 처리와 함께 유용한 토크나이저가 있습니다. 두 가지 모두 다음 기사에서 더 흥미로운 내용을 작성하기 위한 중요한 구성 요소입니다.

이 게시물에서 좋은 아이디어를 얻으셨기를 바라며, 자세한 내용을 보려면 내 GitHub 페이지로 이동하세요.

Toptal 엔지니어링 블로그에 대한 추가 정보:

처음부터 통역사 작성에 접근하는 방법