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

Algunos dicen que "todo se reduce a unos y ceros", pero ¿realmente entendemos cómo nuestros programas se traducen en esos bits?

Tanto los compiladores como los intérpretes toman una cadena sin procesar que representa un programa, la analizan y le dan sentido. Aunque los intérpretes son los más simples de los dos, escribir incluso un intérprete muy simple (que solo hace sumas y multiplicaciones) será instructivo. Nos centraremos en lo que los compiladores y los intérpretes tienen en común: leer y analizar la entrada.

Lo que se debe y lo que no se debe hacer al escribir su propio intérprete

Los lectores pueden preguntarse ¿Qué tiene de malo una expresión regular? Las expresiones regulares son poderosas, pero las gramáticas del código fuente no son lo suficientemente simples como para que las analicen. Tampoco lo son los lenguajes específicos de dominio (DSL), y un cliente podría necesitar un DSL personalizado para las expresiones de autorización, por ejemplo. Pero incluso sin aplicar esta habilidad directamente, escribir un intérprete hace que sea mucho más fácil apreciar el esfuerzo detrás de muchos lenguajes de programación, formatos de archivo y DSL.

Escribir analizadores correctamente a mano puede ser un desafío con todos los casos extremos involucrados. Es por eso que existen herramientas populares, como ANTLR, que pueden generar analizadores para muchos lenguajes de programación populares. También hay bibliotecas llamadas combinadores de analizadores , que permiten a los desarrolladores escribir analizadores directamente en sus lenguajes de programación preferidos. Los ejemplos incluyen FastParse para Scala y Parsec para Python.

Recomendamos que, en un contexto profesional, los lectores utilicen dichas herramientas y bibliotecas para evitar reinventar la rueda. Aún así, comprender los desafíos y las posibilidades de escribir un intérprete desde cero ayudará a los desarrolladores a aprovechar dichas soluciones de manera más efectiva.

Descripción general de los componentes del intérprete

Un intérprete es un programa complejo, por lo que tiene varias etapas:

1. Un lexer es la parte de un intérprete que convierte una secuencia de caracteres (texto sin formato) en una secuencia de tokens.
2. Un analizador , a su vez, toma una secuencia de tokens y produce un árbol de sintaxis abstracta (AST) de un lenguaje. Las reglas por las que opera un analizador suelen especificarse mediante una gramática formal.
3. Un intérprete es un programa que interpreta el AST de la fuente de un programa sobre la marcha (sin compilarlo primero).

No construiremos un intérprete integrado específico aquí. En cambio, exploraremos cada una de estas partes y sus problemas comunes con ejemplos separados. Al final, el código de usuario se verá así:

 val input = "2 * 7 + 5" val tokens = Lexer(input).lex() val ast = Parser(tokens).parse() val res = Interpreter(ast).interpret() println(s"Result is: $res")

Después de las tres etapas, esperaremos que este código calcule un valor final e imprima Result is: 19 . Este tutorial usa Scala porque es:

• Muy conciso, cabe una gran cantidad de código en una pantalla.
• Orientado a expresiones, sin necesidad de variables no inicializadas/nulas.
• Escriba de forma segura, con una potente biblioteca de colecciones, enumeraciones y clases de casos.

Específicamente, el código aquí está escrito en la sintaxis de llaves opcionales de Scala3 (una sintaxis basada en sangrado similar a Python). Pero ninguno de los enfoques es específico de Scala , y Scala es similar a muchos otros lenguajes: a los lectores les resultará sencillo convertir estos ejemplos de código a otros lenguajes. Salvo eso, los ejemplos se pueden ejecutar en línea usando Scastie.

Por último, las secciones Lexer, Parser e Interpreter tienen diferentes gramáticas de ejemplo . Como muestra el repositorio de GitHub correspondiente, las dependencias en ejemplos posteriores cambian ligeramente para implementar estas gramáticas, pero los conceptos generales siguen siendo los mismos.

Intérprete Componente 1: Escribir un Lexer

Digamos que queremos leer esta cadena: "123 + 45 true * false1" . Contiene diferentes tipos de tokens:

• Literales enteros
• Un operador +
• Un operador *
• un true literal
• Un identificador, false1

En este ejemplo, se omitirán los espacios en blanco entre tokens.

En esta etapa, las expresiones no tienen que tener sentido; el lexer simplemente convierte la cadena de entrada en una lista de tokens. (El trabajo de "dar sentido a los tokens" se deja al analizador).

Usaremos este código para representar un token:

 case class Token( tpe: Token.Type, text: String, startPos: Int ) object Token: enum Type: case Num case Plus case Times case Identifier case True case False case EOF

Cada token tiene un tipo, una representación textual y una posición en la entrada original. El puesto puede ayudar a los usuarios finales del lexer con la depuración.

El token EOF es un token especial que marca el final de la entrada. No existe en el texto fuente; solo lo usamos para simplificar la etapa del analizador.

Esta será la salida de nuestro lexer:

 Lexing input: 123 + 45 true * false1 Tokens: List( Token(tpe = Num, text = "123", tokenStartPos = 0), Token(tpe = Plus, text = "+", tokenStartPos = 4), Token(tpe = Num, text = "45", tokenStartPos = 6), Token(tpe = True, text = "true", tokenStartPos = 9), Token(tpe = Times, text = "*", tokenStartPos = 14), Token(tpe = Identifier, text = "false1", tokenStartPos = 16), Token(tpe = EOF, text = "<EOF>", tokenStartPos = 22) )

Examinemos la implementación:

 class Lexer(input: String): def lex(): List[Token] = val tokens = mutable.ArrayBuffer.empty[Token] var currentPos = 0 while currentPos < input.length do val tokenStartPos = currentPos val lookahead = input(currentPos) if lookahead.isWhitespace then currentPos += 1 // ignore whitespace else if lookahead == '+' then currentPos += 1 tokens += Token(Type.Plus, lookahead.toString, tokenStartPos) else if lookahead == '*' then currentPos += 1 tokens += Token(Type.Times, lookahead.toString, tokenStartPos) else if lookahead.isDigit then var text = "" while currentPos < input.length && input(currentPos).isDigit do text += input(currentPos) currentPos += 1 tokens += Token(Type.Num, text, tokenStartPos) else if lookahead.isLetter then // first must be letter var text = "" while currentPos < input.length && input(currentPos).isLetterOrDigit do text += input(currentPos) currentPos += 1 val tpe = text match case "true" => Type.True // special casing literals case "false" => Type.False case _ => Type.Identifier tokens += Token(tpe, text, tokenStartPos) else error(s"Unknown character '$lookahead' at position $currentPos") tokens += Token(Type.EOF, "<EOF>", currentPos) // special end marker tokens.toList

Comenzamos con una lista vacía de tokens, luego revisamos la cadena y agregamos tokens a medida que vienen.

Usamos el carácter anticipado para decidir el tipo del siguiente token . Tenga en cuenta que el carácter anticipado no siempre es el carácter más adelantado que se examina. Según la búsqueda anticipada, sabemos cómo se ve el token y usamos currentPos para escanear todos los caracteres esperados en el token actual, luego agregamos el token a la lista:

Si la anticipación es un espacio en blanco, lo omitimos. Los tokens de una sola letra son triviales; los agregamos e incrementamos el índice. Para números enteros, solo necesitamos cuidar el índice.

Ahora llegamos a algo un poco complicado: identificadores versus literales. La regla es que tomamos la coincidencia más larga posible y verificamos si es un literal; si no lo es, es un identificador.

Tenga cuidado al manejar operadores como < y <= . Ahí tienes que mirar hacia adelante un carácter más y ver si es = antes de concluir que es un operador <= . De lo contrario, es solo un < .

Con eso, nuestro lexer ha producido una lista de tokens.

Componente de intérprete 2: escribir un analizador

Tenemos que dar cierta estructura a nuestros tokens; no podemos hacer mucho solo con una lista. Por ejemplo, necesitamos saber:

¿Qué expresiones están anidadas? ¿Qué operadores se aplican en qué orden? ¿Qué reglas de alcance se aplican, si las hay?

Una estructura de árbol permite anidar y ordenar. Pero primero, tenemos que definir algunas reglas para construir árboles. Nos gustaría que nuestro analizador no sea ambiguo, que siempre devuelva la misma estructura para una entrada determinada.

Tenga en cuenta que el siguiente analizador no utiliza el ejemplo de lexer anterior . Este es para sumar números, por lo que su gramática tiene solo dos tokens, '+' y NUM :

 expr -> expr '+' expr expr -> NUM

Un equivalente, usando un carácter de barra vertical ( | ) como un símbolo "o" como en las expresiones regulares, es:

 expr -> expr '+' expr | NUM

De cualquier manera, tenemos dos reglas: una que dice que podemos sumar dos expr y otra que dice que expr puede ser un token NUM , lo que aquí significará un número entero no negativo.

Las reglas generalmente se especifican con una gramática formal . Una gramática formal consta de: Las reglas mismas, como se muestra arriba Una regla inicial (la primera regla especificada, por convención) Dos tipos de símbolos para definir las reglas con: Terminales: las “letras” (y otros caracteres) de nuestro idioma— los símbolos irreducibles que componen los tokens No terminales: construcciones intermedias utilizadas para el análisis (es decir, símbolos que se pueden reemplazar)

Solo un no terminal puede estar en el lado izquierdo de una regla; el lado derecho puede tener terminales y no terminales. En el ejemplo anterior, los terminales son '+' y NUM , y el único no terminal es expr . Para un ejemplo más amplio, en el lenguaje Java, tenemos terminales como 'true' , '+' , Identifier y '[' , y no terminales como BlockStatements , ClassBody y MethodOrFieldDecl .

Hay muchas formas de implementar este analizador. Aquí, usaremos una técnica de análisis de "descenso recursivo". Es el tipo más común porque es el más simple de entender e implementar.

Un analizador de descenso recursivo usa una función para cada no terminal en la gramática. Comienza desde la regla inicial y desciende desde allí (por lo tanto, "descenso"), determinando qué regla aplicar en cada función. ¡La parte "recursiva" es vital porque podemos anidar no terminales recursivamente! Las expresiones regulares no pueden hacer eso: ni siquiera pueden manejar paréntesis equilibrados. Así que necesitamos una herramienta más poderosa.

Un analizador de la primera regla se vería así (código completo):

 def expr() = expr() eat('+') expr()

La función eat() verifica si la búsqueda anticipada coincide con el token esperado y luego mueve el índice de búsqueda anticipada. Desafortunadamente, esto no funcionará todavía porque necesitamos solucionar algunos problemas con nuestra gramática.

Ambigüedad gramatical

El primer problema es la ambigüedad de nuestra gramática, que puede no ser evidente a primera vista:

 expr -> expr '+' expr | NUM

Dada la entrada 1 + 2 + 3 , nuestro analizador podría optar por calcular primero la expr izquierda o la expr derecha en el AST resultante:

Es por eso que necesitamos introducir algo de asimetría :

 expr -> expr '+' NUM | NUM

El conjunto de expresiones que podemos representar con esta gramática no ha cambiado desde su primera versión. Solo que ahora es inequívoco : el analizador siempre va a la izquierda. ¡Justo lo que necesitábamos!

Esto hace que nuestra operación + sea asociativa por la izquierda , pero esto se hará evidente cuando lleguemos a la sección Intérprete.

Reglas recursivas a la izquierda

Desafortunadamente, la solución anterior no resuelve nuestro otro problema, la recursividad izquierda:

 def expr() = expr() eat('+') eat(NUM)

Tenemos recursividad infinita aquí. Si tuviéramos que entrar en esta función, eventualmente obtendríamos un error de desbordamiento de pila. ¡Pero la teoría del análisis puede ayudar!

Supongamos que tenemos una gramática como esta, donde alpha podría ser cualquier secuencia de terminales y no terminales:

 A -> A alpha | B

Podemos reescribir esta gramática como:

 A -> BA' A' -> alpha A' | epsilon

Allí, epsilon es una cadena vacía: nada, sin token.

Tomemos la revisión actual de nuestra gramática:

 expr -> expr '+' NUM | NUM

Siguiendo el método de reescribir las reglas de análisis detalladas anteriormente, siendo alpha nuestros tokens '+' NUM , nuestra gramática se convierte en:

 expr -> NUM exprOpt exprOpt -> '+' NUM exprOpt | epsilon

Ahora la gramática está bien y podemos analizarla con un analizador descendente recursivo. Veamos cómo se vería un analizador de este tipo para esta última iteración de nuestra gramática:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Unit = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") private def expr(): Unit = eat(Type.Num) exprOpt() private def exprOpt(): Unit = if lookahead.tpe == Type.Plus then eat(Type.Plus) eat(Type.Num) exprOpt() // else: end recursion, epsilon private def eat(tpe: Type): Unit = if lookahead.tpe != tpe then error(s"Expected: $tpe, got: ${lookahead.tpe} at position ${lookahead.startPos}") tokens = tokens.tail lookahead = tokens.head

Aquí usamos el token EOF para simplificar nuestro analizador. Siempre estamos seguros de que hay al menos un token en nuestra lista, por lo que no necesitamos manejar un caso especial de una lista vacía.

Además, si cambiamos a un lexer de transmisión, no tendríamos una lista en memoria sino un iterador, por lo que necesitamos un marcador para saber cuándo llegamos al final de la entrada. Cuando lleguemos al final, el token EOF debería ser el último token restante.

Recorriendo el código, podemos ver que una expresión puede ser solo un número. Si no queda nada, el siguiente token no sería un Plus , por lo que dejaríamos de analizar. El último token sería EOF y habríamos terminado.

Si la cadena de entrada tiene más tokens, estos deberían parecerse a + 123 . ¡Ahí es donde entra en juego la recursividad en exprOpt() !

Generación de un AST

Ahora que analizamos con éxito nuestra expresión, es difícil hacer algo con ella tal como está. Podríamos poner algunas devoluciones de llamada en nuestro analizador, pero eso sería muy engorroso e ilegible. En su lugar, devolveremos un AST, un árbol que representa la expresión de entrada:

 case class Expr(num: Int, exprOpt: ExprOpt) enum ExprOpt: case Opt(num: Int, exprOpt: ExprOpt) case Epsilon

Esto se parece a nuestras reglas, usando clases de datos simples.

Nuestro analizador ahora devuelve una estructura de datos útil:

 class Parser(allTokens: List[Token]): import Token.Type private var tokens = allTokens private var lookahead = tokens.head def parse(): Expr = val res = expr() if lookahead.tpe != Type.EOF then error(s"Unknown token '${lookahead.text}' at position ${lookahead.tokenStartPos}") else res private def expr(): Expr = val num = eat(Type.Num) Expr(num.text.toInt, exprOpt()) private def exprOpt(): ExprOpt = if lookahead.tpe == Type.Plus then eat(Type.Plus) val num = eat(Type.Num) ExprOpt.Opt(num.text.toInt, exprOpt()) else ExprOpt.Epsilon

Para eat() , error() y otros detalles de implementación, consulte el repositorio de GitHub adjunto.

Reglas simplificadas

Nuestro no terminal ExprOpt aún se puede mejorar:

 '+' NUM exprOpt | epsilon

Es difícil reconocer el patrón que representa en nuestra gramática con solo mirarlo. Resulta que podemos reemplazar esta recursión con una construcción más simple:

 ('+' NUM)*

Esta construcción simplemente significa que '+' NUM ocurre cero o más veces.

Ahora nuestra gramática completa se ve así:

 expr -> NUM exprOpt* exprOpt -> '+' NUM

Y nuestro AST se ve mejor:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(num: Int)

El analizador resultante tiene la misma longitud pero es más sencillo de entender y usar. Hemos eliminado Epsilon , que ahora está implícito al comenzar con una estructura vacía.

Ni siquiera necesitábamos la clase ExprOpt aquí. Podríamos haber puesto simplemente case class Expr(num: Int, exprOpts: Seq[Int]) , o en formato gramatical, NUM ('+' NUM)* . Entonces, ¿por qué no lo hicimos?

Considere que si tuviéramos varios operadores posibles, como - o * , tendríamos una gramática como esta:

 expr -> NUM exprOpt* exprOpt -> [+-*] NUM

En este caso, el AST necesita ExprOpt para adaptarse al tipo de operador:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: String, num: Int)

Tenga en cuenta que la sintaxis [+-*] en la gramática significa lo mismo que en las expresiones regulares: "uno de esos tres caracteres". Veremos esto en acción pronto.

Intérprete Componente 3: Escribir un intérprete

Nuestro intérprete hará uso de nuestro lexer y analizador para obtener el AST de nuestra expresión de entrada y luego evaluará ese AST de la forma que queramos. En este caso, estamos tratando con números y queremos evaluar su suma.

En la implementación de nuestro ejemplo de intérprete, usaremos esta gramática simple:

 expr -> NUM exprOpt* exprOpt -> [+-] NUM

Y este AST:

 case class Expr(num: Int, exprOpts: Seq[ExprOpt]) case class ExprOpt(op: Token.Type, num: Int)

(Hemos cubierto cómo implementar un lexer y un analizador para gramáticas similares, pero cualquier lector que se atasque puede leer detenidamente las implementaciones de lexer y analizador para esta gramática exacta en el repositorio).

Ahora veremos cómo escribir un intérprete para la gramática anterior:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = expr.num expr.exprOpts.foreach { exprOpt => if exprOpt.op == Token.Type.Plus then tmp += exprOpt.num else tmp -= exprOpt.num } tmp

Si analizamos nuestra entrada en un AST sin encontrar un error, estamos seguros de que siempre tendremos al menos un NUM . Luego tomamos los números opcionales y los sumamos (o los restamos) a nuestro resultado.

La nota del principio sobre la asociatividad izquierda de + ahora es clara: Partimos del número más a la izquierda y agregamos otros, de izquierda a derecha. Esto puede parecer poco importante para la suma, pero considere la resta: la expresión 5 - 2 - 1 se evalúa como (5 - 2) - 1 = 3 - 1 = 2 y no como 5 - (2 - 1) = 5 - 1 = 4 !

Pero si queremos ir más allá de la interpretación de los operadores más y menos, hay otra regla que definir.

Precedencia

Sabemos cómo analizar una expresión simple como 1 + 2 + 3 , pero cuando se trata de 2 + 3 * 4 + 5 , tenemos un pequeño problema.

La mayoría de la gente está de acuerdo con la convención de que la multiplicación tiene mayor precedencia que la suma. Pero el analizador no lo sabe. No podemos simplemente evaluarlo como ((2 + 3) * 4) + 5 . En su lugar, queremos (2 + (3 * 4)) + 5 .

Esto significa que necesitamos evaluar la multiplicación primero . La multiplicación debe estar más lejos de la raíz del AST para forzar su evaluación antes de la suma. Para esto, necesitamos introducir otra capa más de direccionamiento indirecto.

Arreglando una gramática ingenua de principio a fin

Esta es nuestra gramática original, recursiva a la izquierda, que no tiene reglas de precedencia:

 expr -> expr '+' expr | expr '*' expr | NUM

Primero, le damos reglas de precedencia y eliminamos su ambigüedad :

 expr -> expr '+' term | term term -> term '*' NUM | NUM

Luego obtiene reglas no recursivas a la izquierda :

 expr -> term exprOpt* exprOpt -> '+' term term -> NUM termOpt* termOpt -> '*' NUM

El resultado es un AST maravillosamente expresivo:

 case class Expr(term: Term, exprOpts: Seq[ExprOpt]) case class ExprOpt(term: Term) case class Term(num: Int, termOpts: Seq[TermOpt]) case class TermOpt(num: Int)

Esto nos deja con una implementación de intérprete concisa:

 class Interpreter(ast: Expr): def interpret(): Int = eval(ast) private def eval(expr: Expr): Int = var tmp = eval(expr.term) expr.exprOpts.foreach { exprOpt => tmp += eval(exprOpt.term) } tmp private def eval(term: Term): Int = var tmp = term.num term.termOpts.foreach { termOpt => tmp *= termOpt.num } tmp

Como antes, las ideas en el lexer y la gramática necesarios se cubrieron anteriormente, pero los lectores pueden encontrarlas en el repositorio si es necesario.

Próximos pasos en la escritura de intérpretes

No cubrimos esto, pero el manejo de errores y los informes son características cruciales de cualquier analizador. Como desarrolladores, sabemos lo frustrante que puede ser cuando un compilador produce errores confusos o engañosos. Es un área que tiene muchos problemas interesantes que resolver, como dar mensajes de error correctos y precisos, no disuadir al usuario con más mensajes de los necesarios y recuperarse con gracia de los errores. Depende de los desarrolladores escribir un intérprete o compilador para garantizar que sus futuros usuarios tengan una mejor experiencia.

Al analizar nuestros ejemplos de lectores, analizadores e intérpretes, solo arañamos la superficie de las teorías detrás de los compiladores e intérpretes, que cubren temas como:

• Ámbitos y tablas de símbolos
• Tipos estáticos
• Optimización del tiempo de compilación
• Analizadores de programas estáticos y linters
• Formateo de código e impresión bonita
• Idiomas específicos del dominio

Para leer más, recomiendo estos recursos:

• Patrones de implementación del lenguaje por Terence Parr
• Un libro gratuito en línea, Crafting Interpreters , de Bob Nystrom
• Introducción a la gramática y el análisis sintáctico de Paul Klint
• Escribir buenos mensajes de error del compilador por Caleb Meredith
• Las notas del curso de la Universidad de Carolina del Este "Traducción y compilación de programas"