Stork: Como fazer uma linguagem de programação em C++

Parte 1: Tokenizador

Nesta série, desenvolveremos uma nova linguagem de script e descreveremos esse processo passo a passo.

A primeira pergunta que vem espontaneamente à mente de qualquer leitor curioso provavelmente será: “Nós realmente precisamos de uma nova linguagem de programação?”

Nós realmente precisamos de uma nova linguagem de programação?

Para responder a esta pergunta, permitir-me-ei uma pequena digressão.

Imagine que você é um arquiteto (um verdadeiro arquiteto de tijolo e argamassa, não um de software), e você tem o azar de nascer em um país muito burocrático. Você tem uma ótima ideia para um shopping center em sua cidade natal subdesenvolvida, então cria o projeto e solicita uma licença de construção. Claro, eles imediatamente o rejeitam com o argumento de que você não tem uma empresa registrada. Então, você registra uma empresa. Para fazer isso, você precisa depositar algum dinheiro. Então, você cria um nome para sua empresa, que é rejeitado. Na sua quinta tentativa, ele é aceito e seu aplicativo vai para a parte inferior do heap. Em última análise, você desiste ou percebe que outra pessoa construiu um shopping center nesse meio tempo.

Mas não somos arquitetos genuínos. Somos engenheiros de software e temos o privilégio de dar vida às nossas ideias sem autorização ou burocracia. A única coisa que precisamos é de tempo livre e vontade de gastá-lo em programação em vez de quebra-cabeças de sudoku.

Se você ainda insiste que a motivação para programar não pode ser pura curiosidade, deixe-me apenas mencionar que a primeira linguagem de programação que eu projetei foi desenvolvida por necessidade, não mera curiosidade. No entanto, essa não deve ser a primeira motivação para a leitura deste blog. Acho que muitas ideias que você encontrará aqui são bastante interessantes e inovadoras para mantê-lo interessado, mesmo que você não precise criar sua própria linguagem de programação.

Nosso objetivo de desenvolver uma linguagem de script de pequena pegada me inspirou a chamá-la de “Cegonha”; e felizmente não precisamos convencer nenhum burocrata a aprovar o nome.

Vou desenvolver a linguagem de programação à medida que avançamos na série, então existe a possibilidade de eu desenvolver alguns bugs também. Eles devem ser resolvidos à medida que nos aproximamos do final da série.

O código-fonte completo para tudo descrito aqui está disponível gratuitamente no GitHub.

Finalmente, para responder à pergunta do título deste parágrafo - não, na verdade não precisamos de uma nova linguagem de programação, mas como estamos tentando demonstrar como fazer uma linguagem de programação em C++, criaremos uma para fins de demonstração .

Ajudantes do Tokenizer

Não sei se outros programadores enfrentam o mesmo problema regularmente, mas enfrento esse problema com bastante frequência:

Eu preciso de um contêiner de valor-chave que deve recuperar valores rapidamente, em tempo logarítmico. No entanto, depois de inicializar o contêiner, não quero adicionar novos valores a ele. Portanto, std::map<Key, Value> (ou std::unordered_map<Key, Value> ) é um exagero, pois também permite inserção rápida.

Sou completamente contra a otimização desnecessária, mas neste caso, sinto que muita memória é desperdiçada em nada. Não só isso, mas mais tarde, precisaremos implementar um algoritmo de munch máximo em cima de tal contêiner, e map não é o melhor contêiner para isso.

A segunda opção é std::vector<std::pair<Key,Value> > , classificada após inserções. O único problema com essa abordagem é a menor legibilidade do código, pois precisamos ter em mente que o vetor é classificado, então desenvolvi uma pequena classe que garante essa restrição.

(Todas as funções, classes, etc. são declaradas no namespace stork . Vou omitir esse namespace para facilitar a leitura.)

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

Como você pode ver, a implementação desta classe é bastante simples. Eu não queria implementar todos os métodos possíveis, apenas os que vamos precisar. O contêiner subjacente é um vector , portanto, pode ser inicializado com um vector pré-preenchido ou com initializer_list .

O tokenizer lerá os caracteres do fluxo de entrada. Nesta fase do projeto, é difícil para mim decidir qual será o fluxo de entrada, então usarei std::function em vez disso.

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

Usarei convenções bem conhecidas de funções de fluxo no estilo C, como getc , que retorna um int em vez de char , bem como um número negativo para sinalizar o final de um arquivo.

No entanto, é realmente conveniente ler alguns caracteres antecipadamente, antes de assumir um tipo de token em um tokenizador. Para isso, implementei um fluxo que nos permitirá desler alguns caracteres.

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

Para economizar espaço, omitirei os detalhes de implementação, que você pode encontrar na minha página do GitHub.

Como você pode ver, push_back_stream é inicializado a partir da função get_character . O operator() é usado para recuperar o próximo caractere e push_back é usado para retornar o caractere de volta ao fluxo. line_number e char_number são métodos de conveniência usados ​​para relatórios de erros.

Tenha em mente que char_index não é o índice do caractere na linha atual, mas no geral; caso contrário, teríamos que manter todos os caracteres anteriores em algum container para implementar a função push_back corretamente.

Tokens Reservados

O tokenizer é o componente do compilador de nível mais baixo. Ele tem que ler os tokens de entrada e “cuspir-out”. Existem quatro tipos de tokens que nos interessam:

• Tokens reservados
• Identificadores
• Números
• Cordas

Não estamos interessados ​​em comentários, então o tokenizer irá apenas “comê-los”, sem notificar ninguém.

Para garantir o apelo e a popularidade planetária dessa linguagem, usaremos a conhecida sintaxe do tipo C. Funcionou muito bem para C, C++, JavaScript, Java, C# e Objective-C, então deve funcionar para Stork também. Caso precise de um curso de atualização, você pode consultar um de nossos artigos anteriores sobre recursos de aprendizado C/C++.

Aqui está a enumeração de tokens reservados:

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

Os membros de enumeração prefixados com “kw_” são palavras-chave. Eu tive que prefixá-los, pois geralmente são os mesmos que as palavras-chave C++. Os sem prefixo são operadores.

Quase todos eles seguem a convenção C. Os que não são:
- concat e concat_assign ( .. e ..= ), que serão usados ​​para concatenação
- idiv e idiv_assign ( \ e \= ), que serão usados ​​para divisão de inteiros
- kw_var para declaração de variável
- kw_fun para declaração de função
- kw_number para variáveis ​​numéricas
- kw_string para variáveis ​​de string

Adicionaremos palavras-chave adicionais, conforme necessário.

Há uma nova palavra-chave que merece ser descrita: kw_elif . Acredito firmemente que blocos de instrução única (sem chaves) não valem a pena. Não os uso (e não sinto que falte nada), exceto em duas ocasiões:

1. Quando eu acidentalmente bato ponto e vírgula imediatamente após uma instrução for , while ou if antes do bloco. Se eu tiver sorte, ele retorna um erro de tempo de compilação, mas às vezes resulta em uma instrução if fictícia e um bloco que sempre é executado. Felizmente, ao longo dos anos, aprendi com meus erros, então isso acontece muito raramente. O cachorro de Pavlov também aprendeu, eventualmente.
2. Quando eu “encadeei” instruções if, então eu tenho um bloco if, então um ou mais blocos else-if e, opcionalmente, um bloco else. Tecnicamente, quando escrevo else if , esse é um bloco else com apenas uma instrução, que é essa instrução if.

Portanto, elif pode ser usado para eliminar completamente as instruções sem chaves. Permitir ou não é uma decisão que pode esperar agora.

Existem duas funções auxiliares que retornam tokens reservados:

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

A função get_keyword retorna uma palavra-chave opcional da palavra passada. Essa “palavra” é uma sequência de letras, dígitos e sublinhados, começando com uma letra ou um sublinhado. Ele retornará um reserved_token se a palavra for uma palavra-chave. Caso contrário, o tokenizer assumirá que é um identificador.

A função get_operator está tentando ler o maior número possível de caracteres, desde que a sequência seja um operador válido. Se ler mais, ele não lerá todos os caracteres extras lidos após o operador reconhecido mais longo.

Para a implementação efetiva dessas duas funções, precisamos de duas pesquisas entre string_view e 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} };

A implementação get_keyword é completamente direta, mas para get_operator , precisamos de um comparador personalizado que compare um determinado caractere com operadores candidatos, levando em consideração apenas o n-ésimo caractere.

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

Esse é um comparador léxico comum que leva em consideração apenas o caractere na posição idx , mas se a string for menor, ela a trata como se tivesse um caractere nulo na posição idx , que é menor que qualquer outro caractere.

Esta é a implementação de get_operator , que deve tornar a classe maximal_munch_operator mais clara:

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

Basicamente, tratamos todos os operadores como candidatos no início. Em seguida, lemos caractere por caractere e filtramos os candidatos atuais chamando equal_range , comparando apenas o n-ésimo caractere. Não precisamos comparar os caracteres anteriores, pois eles já foram comparados, e não queremos comparar os caracteres seguintes, pois ainda são irrelevantes.

Sempre que o intervalo não estiver vazio, verificamos se o primeiro elemento do intervalo não possui mais caracteres (se tal elemento existir, ele estará sempre no início do intervalo conforme a pesquisa for classificada). Nesse caso, temos um operador legal correspondido. O operador mais longo é aquele que retornamos. Vamos desler todos os personagens que eventualmente lemos depois disso.

Tokenizador

Como os tokens são heterogêneos, um token é uma classe de conveniência que envolve diferentes tipos de token std::variant , a saber:

• Token reservado
• Identificador
• Número
• Corda
• Fim do arquivo

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

O identifier é apenas uma classe com um único membro do tipo std::string . Está lá por conveniência, pois, na minha opinião, std::variant é mais limpo se todas as suas alternativas forem de tipos diferentes.

Agora, podemos escrever o tokenizer. Será uma função que aceitará push_back_stream e retornará o próximo token.

O truque é usar diferentes ramificações de código, com base no tipo de caractere do primeiro caractere que lemos.

• Se lermos o caractere de fim de arquivo, retornaremos da função.
• Se lermos um espaço em branco, vamos ignorá-lo.
• Se lermos um caractere alfanumérico (uma letra, um dígito ou um sublinhado), leremos todos os caracteres sucessivos desse tipo (também leremos pontos se o primeiro caractere for um dígito). Então, se o primeiro caractere for um dígito, tentaremos analisar a sequência como um número. Caso contrário, usaremos a função get_keyword para verificar se é uma palavra-chave ou um identificador.
• Se lermos uma aspa, vamos tratá-la como uma string, sem escape de caracteres de escape.
• Se lermos um caractere de barra ( / ), verificaremos se o próximo caractere é uma barra ou um asterisco ( * ) e pularemos o comentário de linha/bloco nesse caso.
• Caso contrário, usaremos a função get_operator .

Aqui está a implementação da função tokenize. Omitirei os detalhes de implementação das funções que ele está chamando.

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

Você pode ver que ele retorna os caracteres que lê antes de chamar uma função de nível inferior. A penalidade de desempenho é quase inexistente e o código de função de nível inferior é muito mais limpo.

Exceções

Em um de seus discursos contra exceções, meu irmão disse uma vez:

“Existem dois tipos de pessoas: aquelas que lançam exceções e aquelas que precisam pegá-las. Estou sempre nesse segundo grupo triste.”

Concordo com o espírito dessa afirmação. Eu particularmente não gosto de exceções, e lançá-las pode tornar qualquer código muito mais difícil de manter e ler. Quase sempre.

Eu decidi fazer uma exceção (trocadilho ruim intencional) a essa regra. É realmente conveniente lançar uma exceção do compilador para relaxar das profundezas da compilação.

Aqui está a implementação da exceção:

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

No entanto, prometo capturar todas as exceções no código de nível superior. Eu até adicionei os membros line_number e char_index para impressão bonita e a função que faz isso:

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

Empacotando

Isso conclui a primeira parte da nossa série. Talvez não tenha sido muito empolgante, mas agora temos um tokenizer útil, juntamente com o tratamento básico de erros de análise. Ambos são blocos de construção cruciais para as coisas mais interessantes sobre as quais escreverei nos próximos artigos.

Espero que você tenha tirado algumas boas ideias deste post e, se quiser explorar os detalhes, acesse minha página do GitHub.

Leitura adicional no Blog da Toptal Engineering:

• Como abordar a escrita de um intérprete do zero