Stork: Cómo hacer un lenguaje de programación en C++

Parte 1: Tokenizador

En esta serie, desarrollaremos un nuevo lenguaje de secuencias de comandos y describiremos ese proceso paso a paso.

Es probable que la primera pregunta que surge espontáneamente en la mente de cualquier lector preguntándose sea: "¿Realmente necesitamos un nuevo lenguaje de programación?"

¿Realmente necesitamos un nuevo lenguaje de programación?

Para responder a esta pregunta, me permitiré una pequeña digresión.

Imagina que eres arquitecto (un arquitecto real de ladrillo y mortero, no uno de software) y tienes la mala suerte de nacer en un país muy burocrático. Tiene una gran idea para un centro comercial en su ciudad natal subdesarrollada, por lo que crea el proyecto y solicita un permiso de construcción. Por supuesto, inmediatamente te rechazan alegando que no tienes una empresa registrada. Entonces, registras una empresa. Para hacer eso, necesitas depositar algo de dinero. Luego, se le ocurre un nombre para su empresa, que es rechazado. En su quinto intento, se acepta y su solicitud va al final del montón. En última instancia, te rindes o te das cuenta de que alguien más construyó un centro comercial mientras tanto.

Pero no somos auténticos arquitectos. Somos ingenieros de software y tenemos el privilegio de hacer realidad nuestras ideas sin permisos ni burocracia. Lo único que necesitamos es tiempo libre y ganas de gastarlo en programación en lugar de sudokus.

Si aún insiste en que la motivación para programar no puede ser pura curiosidad, permítame mencionar que el primer lenguaje de programación que diseñé se desarrolló como resultado de la necesidad, no de la mera curiosidad. Sin embargo, esa no debería ser la primera motivación para leer este blog. Creo que muchas ideas que encontrarás aquí son bastante interesantes e innovadoras para mantenerte interesado incluso si no necesitas crear tu propio lenguaje de programación.

Nuestro objetivo de desarrollar un lenguaje de secuencias de comandos de tamaño reducido me inspiró a llamarlo "Stork"; y por suerte, no necesitamos convencer a ningún burócrata para que apruebe el nombre.

Voy a desarrollar el lenguaje de programación a medida que avanzamos en la serie, por lo que existe la posibilidad de que también desarrolle algunos errores. Deben resolverse a medida que nos acercamos al final de la serie.

El código fuente completo de todo lo descrito aquí está disponible gratuitamente en GitHub.

Finalmente, para responder a la pregunta del título de este párrafo, no, en realidad no necesitamos un nuevo lenguaje de programación, pero dado que estamos tratando de demostrar cómo hacer un lenguaje de programación en C++, crearemos uno con fines de demostración. .

Pequeños ayudantes de Tokenizer

No sé si otros programadores enfrentan el mismo problema regularmente, pero me enfrento a este problema con bastante frecuencia:

Necesito un contenedor de clave-valor que debería recuperar valores rápidamente, en tiempo logarítmico. Sin embargo, una vez que inicializo el contenedor, no quiero agregarle nuevos valores. Por lo tanto, std::map<Key, Value> (o std::unordered_map<Key, Value> ) es excesivo, ya que también permite una inserción rápida.

Estoy completamente en contra de la optimización innecesaria, pero en este caso, siento que se desperdicia mucha memoria en nada. No solo eso, sino que más adelante necesitaremos implementar un algoritmo de masticación máxima sobre dicho contenedor, y el map no es el mejor contenedor para eso.

La segunda opción es std::vector<std::pair<Key,Value> > , ordenada después de las inserciones. El único problema con ese enfoque es la menor legibilidad del código, ya que debemos tener en cuenta que el vector está ordenado, por lo que desarrollé una clase pequeña que asegura esa restricción.

(Todas las funciones, clases, etc. se declaran en el espacio de nombres stork . Omitiré ese espacio de nombres para facilitar la lectura).

 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 puede ver, la implementación de esta clase es bastante simple. No quería implementar todos los métodos posibles, solo los que necesitaremos. El contenedor subyacente es un vector , por lo que se puede inicializar con un vector rellenado previamente o con initializer_list .

El tokenizador leerá los caracteres del flujo de entrada. En esta etapa del proyecto, es difícil para mí decidir cuál será el flujo de entrada, por lo que std::function en su lugar.

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

Usaré convenciones bien conocidas de funciones de flujo de estilo C, como getc , que devuelve un int en lugar de char , así como un número negativo para señalar el final de un archivo.

Sin embargo, es realmente conveniente leer un par de caracteres por adelantado, antes de asumir un tipo de token en un tokenizador. Con ese fin, implementé una transmisión que nos permitirá desleer algunos 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 ahorrar espacio, omitiré los detalles de implementación, que puede encontrar en mi página de GitHub.

Como puede ver, push_back_stream se inicializa desde la función get_character . El operator() se usa para recuperar el siguiente carácter, y push_back se usa para devolver el carácter a la secuencia. line_number y char_number son métodos convenientes que se utilizan para los informes de errores.

Tenga en cuenta que char_index no es el índice del carácter en la línea actual sino en general; de lo contrario, tendríamos que mantener todos los caracteres pasados ​​en algún contenedor para implementar correctamente la función push_back .

Fichas reservadas

El tokenizador es el componente del compilador de nivel más bajo. Tiene que leer los tokens de entrada y "escupir". Hay cuatro tipos de tokens que nos interesan:

• fichas reservadas
• Identificadores
• Números
• Instrumentos de cuerda

No estamos interesados ​​en los comentarios, por lo que el tokenizador simplemente los "comerá", sin notificar a nadie.

Para asegurar el atractivo y la popularidad planetaria de este lenguaje, utilizaremos la conocida sintaxis tipo C. Funcionó bastante bien para C, C++, JavaScript, Java, C# y Objective-C, por lo que también debe funcionar para Stork. En caso de que necesite un curso de actualización, puede consultar uno de nuestros artículos anteriores sobre recursos de aprendizaje de C/C++.

Aquí está la enumeración 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, };

Los miembros de la enumeración con el prefijo "kw_" son palabras clave. Tuve que ponerles un prefijo, ya que suelen ser las mismas que las palabras clave de C++. Los que no tienen prefijo son operadores.

Casi todos siguen la convención C. Los que no son:
- concat y concat_assign ( .. y ..= ), que se usarán para la concatenación
- idiv e idiv_assign ( \ y \= ), que se utilizarán para la división de enteros
- kw_var para declaración de variables
- kw_fun para declaración de función
- kw_number para variables numéricas
- kw_string para variables de cadena

Agregaremos palabras clave adicionales, según sea necesario.

Hay una nueva palabra clave que merece ser descrita: kw_elif . Soy un firme creyente de que los bloques de una sola declaración (sin llaves) no valen la pena. No los uso (y no siento que falte nada), salvo en dos ocasiones:

1. Cuando accidentalmente presiono el punto y coma inmediatamente después de una instrucción for , while o if antes del bloque. Si tengo suerte, devuelve un error de tiempo de compilación, pero a veces da como resultado una declaración if ficticia y un bloque que siempre se ejecuta. Afortunadamente, a lo largo de los años, he aprendido de mis errores, por lo que sucede muy raramente. El perro de Pavlov también aprendió, eventualmente.
2. Cuando tengo sentencias if "encadenadas", entonces tengo un bloque if, luego uno o más bloques else-if y, opcionalmente, un bloque else. Técnicamente, cuando escribo else if , ese es un bloque else con una sola declaración, que es esa declaración if.

Por lo tanto, elif se puede usar para eliminar completamente las declaraciones sin llaves. Si lo permitimos o no, es una decisión que puede esperar por ahora.

Hay dos funciones auxiliares que devuelven tokens reservados:

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

La función get_keyword devuelve una palabra clave opcional de la palabra pasada. Esa “palabra” es una secuencia de letras, dígitos y guiones bajos, comenzando con una letra o un guión bajo. Devolverá un reserved_token si la palabra es una palabra clave. De lo contrario, el tokenizador asumirá que es un identificador.

La función get_operator intenta leer tantos caracteres como sea posible, siempre que la secuencia sea un operador válido. Si lee más, dejará de leer todos los caracteres adicionales que haya leído después del operador reconocido más largo.

Para la implementación efectiva de esas dos funciones, necesitamos dos búsquedas entre string_view y 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} };

La implementación get_keyword es completamente sencilla, pero para get_operator , necesitamos un comparador personalizado que compare un carácter determinado con los operadores candidatos, teniendo en cuenta solo el carácter 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] ); } };

Es un comparador léxico ordinario que tiene en cuenta solo el carácter en la posición idx , pero si la cadena es más corta, la trata como si tuviera un carácter nulo en la posición idx , que es menor que cualquier otro carácter.

Esta es la implementación de get_operator , que debería aclarar la clase maximal_munch_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; }

Básicamente, tratamos a todos los operadores como candidatos al principio. Luego, leemos carácter por carácter y filtramos los candidatos actuales llamando a equal_range , comparando solo el n-ésimo carácter. No necesitamos comparar los caracteres anteriores, ya que ya se compararon, y no queremos comparar los caracteres que siguen, ya que aún son irrelevantes.

Siempre que el rango no esté vacío, verificamos si el primer elemento del rango no tiene más caracteres (si existe tal elemento, siempre está al comienzo del rango a medida que se ordena la búsqueda). En ese caso, tenemos un operador legal emparejado. El operador más largo es el que devolvemos. Dejaremos de leer todos los caracteres que eventualmente leamos después de eso.

Tokenizador

Dado que los tokens son heterogéneos, un token es una clase de conveniencia que envuelve diferentes tipos de tokens std::variant , a saber:

• ficha reservada
• identificador
• Número
• Cuerda
• Fin del documento

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

El identifier es solo una clase con un solo miembro del tipo std::string . Está ahí por conveniencia ya que, en mi opinión, std::variant es más limpio si todas sus alternativas son de diferentes tipos.

Ahora, podemos escribir el tokenizador. Será una función que aceptará push_back_stream y devolverá el siguiente token.

El truco consiste en usar diferentes ramas de código, según el tipo de carácter del primer carácter que leemos.

• Si leemos el carácter de fin de archivo, regresaremos de la función.
• Si leemos un espacio en blanco, lo saltaremos.
• Si leemos un carácter alfanumérico (una letra, un dígito o un guión bajo), leeremos todos los caracteres sucesivos de ese tipo (también leeremos puntos si el primer carácter es un dígito). Luego, si el primer carácter es un dígito, intentaremos analizar la secuencia como un número. De lo contrario, usaremos la función get_keyword para verificar si es una palabra clave o un identificador.
• Si leemos una comilla, la trataremos como una cadena, eliminando los caracteres escapados de ella.
• Si leemos un carácter de barra inclinada ( / ), comprobaremos si el siguiente carácter es una barra inclinada o un asterisco ( * ), y omitiremos el comentario de línea/bloque en ese caso.
• De lo contrario, usaremos la función get_operator .

Aquí está la implementación de la función tokenize. Omitiré los detalles de implementación de las funciones que está llamando.

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

Puede ver que retrocede los caracteres que lee antes de llamar a una función de nivel inferior. La penalización de rendimiento es casi inexistente y el código de función de nivel inferior es mucho más limpio.

Excepciones

En una de sus peroratas contra las excepciones, mi hermano dijo una vez:

“Hay dos tipos de personas: las que lanzan excepciones y las que tienen que atraparlas. Siempre estoy en ese triste segundo grupo”.

Estoy de acuerdo con el espíritu de esa declaración. No me gustan particularmente las excepciones, y lanzarlas puede hacer que cualquier código sea mucho más difícil de mantener y leer. Casi siempre.

Decidí hacer una excepción (mal juego de palabras) a esa regla. Es realmente conveniente lanzar una excepción desde el compilador para desconectar de las profundidades de la compilación.

Aquí está la implementación de la excepción:

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

Sin embargo, prometo detectar todas las excepciones en el código de nivel superior. Incluso agregué miembros line_number y char_index para la impresión bonita, y la función que lo hace:

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

Terminando

Con esto concluye la primera parte de nuestra serie. Quizás no fue demasiado emocionante, pero ahora tenemos un tokenizador útil, junto con el manejo básico de errores de análisis. Ambos son bloques de construcción cruciales para las cosas más interesantes sobre las que escribiré en los próximos artículos.

Espero que hayas obtenido algunas buenas ideas de esta publicación, y si quieres explorar los detalles, ve a mi página de GitHub.

Lecturas adicionales en el blog de ingeniería de Toptal:

• Cómo abordar la escritura de un intérprete desde cero