1. Introducción

En este tutorial, construiremos nuestro propio lenguaje de programación y compilador usando Java (puedes usar cualquier otro lenguaje, preferiblemente orientado a objetos). El propósito de este artículo es ayudar a las personas que buscan una forma de crear su propio lenguaje de programación y compilador. Este es un ejemplo de juguete, pero intentará ayudarlo a comprender por dónde empezar y en qué dirección moverse. El código fuente completo está disponible en GitHub

Cada idioma tiene varias etapas desde el código fuente hasta el archivo ejecutable final. Cada una de las etapas formatea los datos entrantes de cierta manera:

1. El análisis léxico en términos simples es una división del código fuente en tokens. Cada token puede contener un lexema diferente: palabra clave, identificador/variable, operador con el valor correspondiente, etc.
2. El análisis de sintaxis o analizador convierte una lista de tokens entrantes en el árbol de sintaxis abstracta ( AST ), que le permite presentar estructuralmente las reglas del lenguaje que se está creando. El proceso en sí es bastante simple, como se puede ver a primera vista, pero con un aumento de las construcciones del lenguaje, puede volverse mucho más complicado.
3. Una vez que se ha creado AST, podemos generar el código. El código generalmente se genera recursivamente usando un árbol de sintaxis abstracta. Nuestro compilador, en aras de la simplicidad, producirá declaraciones durante el análisis de sintaxis.

Crearemos un lenguaje sencillo con las siguientes capacidades:

1. asignar las variables (numéricas, lógicas y de texto)
2. declarar estructuras, crear instancias y acceder a campos
3. realizar operaciones matemáticas simples (suma, resta, NOT)
4. imprimir variables, valores y expresiones más complejas con operadores matemáticos
5. leer valores numéricos, lógicos y de texto desde la consola
6. realizar sentencias si-entonces

Hay un ejemplo del código de nuestro lenguaje, es una mezcla de sintaxis de Ruby y Python:

 struct Person arg name arg experience arg is_developer end input your_name input your_experience_in_years input do_you_like_programming person = new Person [your_name your_experience_in_years do_you_like_programming == "yes"] print person if person :: is_developer then person_name = person :: name print "hey " + person_name + "!" experience = person :: experience if experience > 0 then started_in = 2022 - experience print "you had started your career in " + started_in end end

2 Análisis léxico

En primer lugar, comenzaremos con el análisis léxico. Imaginemos que recibiste un mensaje de un amigo con el siguiente contenido:

 “Ienjoyreadingbooks”

Esta expresión es un poco difícil de leer. Es solo un conjunto de letras sin ningún significado. Esto se debe a que nuestro analizador léxico natural no puede encontrar ninguna palabra apropiada en nuestro diccionario. Sin embargo, si ponemos los espacios correctamente, todo queda claro:

 “I enjoy reading books”

El analizador léxico de un lenguaje de programación funciona según el mismo principio. Cuando hablamos destacamos palabras individuales por entonación y pausas para entendernos. De la misma forma debemos proporcionar el código al analizador léxico para que nos entienda. Si lo escribimos mal, el analizador léxico no podrá separar lexemas, palabras y construcciones sintácticas individuales.

Hay seis unidades de lexemas (tokens) que contaremos en nuestro lenguaje de programación durante el análisis léxico:

1. Espacio, retorno de carro y otros caracteres de espacio en blanco

Estas unidades de lexema no tienen mucho sentido. No puede declarar ningún bloque de código o parámetro de función usando un espacio. La intención principal es solo ayudar a un desarrollador a dividir su código en lexemas separados. Por lo tanto, el analizador léxico primero buscará espacios y saltos de línea para comprender cómo resaltar los lexemas proporcionados en el código.

2. Operadores: + , - , = , < , > , ::

Pueden ser parte de declaraciones compuestas más complejas. El signo igual puede significar no solo un operador de asignación, sino que también puede combinar un operador de comparación de igualdad más complejo, que consta de dos `=` en una fila. En este caso, el analizador léxico intentará leer las expresiones de izquierda a derecha intentando captar el operador más largo.

3. Divisores de grupo: [ , ]

Los divisores de grupo pueden separar dos lexemas de grupo entre sí. Por ejemplo, se puede usar un corchete abierto para marcar el comienzo de un grupo específico y un corchete cerrado marcará el final del grupo iniciado. En nuestro idioma, los corchetes solo se utilizarán para declarar argumentos de instancia de estructura.

4. Palabras clave: print , input , struct , arg , end , new , if , then

Una palabra clave es un conjunto de caracteres alfabéticos con algún sentido específico asignado por el compilador. Por ejemplo, una combinación de 5 letras `print` forma una palabra y el compilador del lenguaje la percibe como una definición de declaración de salida de la consola. Este significado no puede ser cambiado por un programador. Esa es la idea básica de las palabras clave, son axiomas del lenguaje que combinamos para crear nuestras propias declaraciones: programas.

5. Variables o identificadores

Además de las palabras clave, también debemos tener en cuenta las variables. Una variable es una secuencia de caracteres con algún significado dado por un programador, no por un compilador. Al mismo tiempo, debemos poner ciertas restricciones en los nombres de las variables. Nuestras variables contendrán solo letras, números y caracteres de subrayado. No pueden aparecer otros caracteres dentro del identificador porque la mayoría de los operadores que describimos son delimitadores y, por lo tanto, no pueden formar parte de otro lexema. En este caso, la variable no puede comenzar con un dígito debido a que el analizador léxico detecta un dígito e inmediatamente intenta relacionarlo con un número. Además, es importante tener en cuenta que la variable no se puede expresar mediante una palabra clave. Significa que si nuestro lenguaje define la palabra clave `imprimir`, entonces el programador no puede introducir una variable con el mismo conjunto de caracteres definidos en el mismo orden.

6. literales

Si la secuencia de caracteres dada no es una palabra clave y no es una variable, la última opción permanece: puede ser una constante literal. Nuestro lenguaje podrá definir literales numéricos, lógicos y de texto. Los literales numéricos son variables especiales que contienen dígitos. En aras de la simplicidad, no usaremos números de punto flotante (fracciones), puede implementarlo usted mismo más adelante. Los literales lógicos pueden contener valores booleanos: falso o verdadero. El literal de texto es un conjunto arbitrario de caracteres del alfabeto entre comillas dobles.

Ahora que tenemos la información básica sobre todos los lexemas posibles en nuestro lenguaje de programación, profundicemos en el código y comencemos a declarar nuestros tipos de token. Usaremos constantes de enumeración con la expresión de patrón correspondiente para cada tipo de lexema. Usaré las anotaciones de Lombok para minimizar el código repetitivo:

 @RequiredArgsConstructor @Getter public enum TokenType { Whitespace("[\\s\\t\\n\\r]"), Keyword("(if|then|end|print|input|struct|arg|new)"), GroupDivider("(\\[|\\])"), Logical("true|false"), Numeric("[0-9]+"), Text("\"([^\"]*)\""), Variable("[a-zA-Z_]+[a-zA-Z0-9_]*"), Operator("(\\+|\\-|\\>|\\<|\\={1,2}|\\!|\\:{2})"); private final String regex; }

Para simplificar el análisis de literales, dividí cada uno de los tipos de literales en un lexema separado: Numeric , Logical y Text . Para el Text literal, establecemos un grupo separado ([^"]*) para tomar el valor literal sin comillas dobles. Para los iguales, declaramos el rango {1,2} . Con dos signos iguales == , esperamos obtener el operador de comparación en su lugar. de la asignación Para acceder a un campo de estructura declaramos el operador de dos puntos :: .

Ahora, para encontrar un token en nuestro código, simplemente iteramos y filtramos todos los valores de TokenType aplicando expresiones regulares en nuestro código fuente. Para que coincida con el comienzo de la fila, colocamos el metacarácter ^ al comienzo de cada expresión regular creando una instancia de patrón. El token de texto capturará el valor sin comillas en el grupo separado. Por lo tanto, para acceder al valor sin comillas tomamos un valor del grupo con índice 1 si tenemos al menos un grupo explícito:

 for (TokenType tokenType : TokenType.values()) { Pattern pattern = Pattern.compile("^" + tokenType.getRegex()); Matcher matcher = pattern.matcher(sourceCode); if (matcher.find()) { // group(1) is used to get text literal without double quotes String token = matcher.groupCount() > 0 ? matcher.group(1) : matcher.group(); } }

Para almacenar los lexemas encontrados, debemos declarar la siguiente clase de Token con campos de tipo y valor:

 @Builder @Getter public class Token { private final TokenType type; private final String value; }

Ahora tenemos todo para crear nuestro analizador léxico. Recibiremos el código fuente como una cadena en el constructor e inicializaremos la lista de tokens:

 public class LexicalParser { private final List<Token> tokens; private final String source; public LexicalParser(String source) { this.source = source; this.tokens = new ArrayList<>(); } ... }

Para recuperar todos los tokens del código fuente, necesitamos cortar la fuente después de cada lexema encontrado. Declararemos el método nextToken() que aceptará el índice actual del código fuente como argumento y tomará el siguiente token que comienza después de la posición actual:

 public class LexicalParser { ... private int nextToken(int position) { String nextToken = source.substring(position); for (TokenType tokenType : TokenType.values()) { Pattern pattern = Pattern.compile("^" + tokenType.getRegex()); Matcher matcher = pattern.matcher(nextToken); if (matcher.find()) { if (tokenType != TokenType.Whitespace) { // group(1) is used to get text literal without double quotes String value = matcher.groupCount() > 0 ? matcher.group(1) : matcher.group(); Token token = Token.builder().type(tokenType).value(value).build(); tokens.add(token); } return matcher.group().length(); } } throw new TokenException(String.format("invalid expression: `%s`", nextToken)); } }

Después de una captura exitosa, creamos una instancia de Token y la acumulamos en la lista de tokens. No agregaremos los lexemas de Whitespace en blanco ya que solo se usan para dividir dos lexemas entre sí. Al final devolvemos la longitud del lexema encontrado.

Para capturar todos los tokens en la fuente, creamos el método parse() con el ciclo while aumentando la posición de la fuente cada vez que capturamos un token:

 public class LexicalParser { ... public List<Token> parse() { int position = 0; while (position < source.length()) { position += nextToken(position); } return tokens; } ... }

3 Análisis de sintaxis

Dentro de nuestro modelo de compilador, el analizador de sintaxis recibirá una lista de tokens del analizador léxico y verificará si la gramática del lenguaje puede generar esta secuencia. Al final, este analizador de sintaxis debería devolver un árbol de sintaxis abstracto.

Iniciaremos el analizador de sintaxis declarando la interfaz Expression :

 public interface Expression { }

Esta interfaz se utilizará para declarar literales, variables y expresiones compuestas con operadores.

3.1 Literales

En primer lugar, creamos implementaciones de Expression para los tipos literales de nuestro lenguaje: Numeric , Text y Logical con los tipos de Java correspondientes: Integer , String y Boolean . Crearemos la clase Value base con tipo genérico que se extiende Comparable (se usará más adelante con operadores de comparación):

 @RequiredArgsConstructor @Getter public class Value<T extends Comparable<T>> implements Expression { private final T value; @Override public String toString() { return value.toString(); } } public class NumericValue extends Value<Integer> { public NumericValue(Integer value) { super(value); } } public class TextValue extends Value<String> { public TextValue(String value) { super(value); } } public class LogicalValue extends Value<Boolean> { public LogicalValue(Boolean value) { super(value); } }

También declararemos StructureValue para nuestras instancias de estructura:

 public class StructureValue extends Value<StructureExpression> { public StructureValue(StructureExpression value) { super(value); } }

StructureExpression se tratará un poco más adelante.

3.2 Variables

La expresión variable tendrá un solo campo que representa su nombre:

 @AllArgsConstructor @Getter public class VariableExpression implements Expression { private final String name; }

3.3 Estructuras

Para almacenar una instancia de estructura, necesitaremos conocer la definición de la estructura y los valores de los argumentos que estamos pasando para crear un objeto. Los valores de los argumentos pueden significar cualquier expresión, incluidos literales, variables y expresiones más complejas que implementan la interfaz Expression . Por lo tanto, usaremos Expression como tipo de valores:

 @RequiredArgsConstructor @Getter public class StructureExpression implements Expression { private final StructureDefinition definition; private final List<Expression> values; } @RequiredArgsConstructor @Getter @EqualsAndHashCode(onlyExplicitlyIncluded = true) public class StructureDefinition { @EqualsAndHashCode.Include private final String name; private final List<String> arguments; }

Los valores pueden ser un tipo de VariableExpression . Necesitamos una forma de acceder al valor de la variable por su nombre. Delegaré esta responsabilidad a la interfaz de la función, que aceptará el nombre de la variable y devolverá un objeto de Value :

 ... public class StructureExpression implements Expression { ... private final Function<String, Value<?>> variableValue; }

Ahora podemos implementar una interfaz para recuperar el valor de un argumento por su nombre, se usará para acceder a los valores de instancia de la estructura. El método getValue() se implementará un poco más tarde:

 ... public class StructureExpression implements Expression { … public Value<?> getArgumentValue(String field) { return IntStream .range(0, values.size()) .filter(i -> definition.getArguments().get(i).equals(field)) .mapToObj(this::getValue) //will be implemented later .findFirst() .orElse(null); } }

No olvide que nuestra StructureExpression se utiliza como parámetro para el tipo genérico StructureValue que amplía Comparable. Por lo tanto, debemos implementar una interfaz comparable para nuestra expresión de StructureExpression :

 ... public class StructureExpression implements Expression, Comparable<StructureExpression> { ... @Override public int compareTo(StructureExpression o) { for (String field : definition.getArguments()) { Value<?> value = getArgumentValue(field); Value<?> oValue = o.getArgumentValue(field); if (value == null && oValue == null) continue; if (value == null) return -1; if (oValue == null) return 1; //noinspection unchecked,rawtypes int result = ((Comparable) value.getValue()).compareTo(oValue.getValue()); if (result != 0) return result; } return 0; } }

También podemos anular el método toString() estándar. Será útil si queremos imprimir una instancia de estructura completa en la consola:

 ... public class ObjectExpression implements Expression, Comparable<ObjectExpression> { ... @Override public String toString() { return IntStream .range(0, values.size()) .mapToObj(i -> { Value<?> value = getValue(i); //will be implemented later String fieldName = definition.getArguments().get(i); return fieldName + " = " + value; }) .collect(Collectors.joining(", ", definition.getName() + " [ ", " ]")); } }

3.4 Operadores

En nuestro lenguaje tendremos operadores unarios con 1 operando y operadores binarios con 2 operandos.

Implementemos la interfaz Expression para cada uno de nuestros operadores. Declaramos la interfaz OperatorExpression y creamos implementaciones base para operadores binarios y unarios:

 public interface OperatorExpression extends Expression { } @RequiredArgsConstructor @Getter public class UnaryOperatorExpression implements OperatorExpression { private final Expression value; } @RequiredArgsConstructor @Getter public class BinaryOperatorExpression implements OperatorExpression { private final Expression left; private final Expression right; }

También necesitamos declarar un método calc() abstracto para cada una de nuestras implementaciones de operadores con los valores correspondientes de los operandos. Este método calculará el Value de los operandos dependiendo de la esencia de cada operador. La transición del operando de la Expression al Value se cubrirá un poco más adelante.

 … public abstract class UnaryOperatorExpression extends OperatorExpression { … public abstract Value<?> calc(Value<?> value); } … public abstract class BinaryOperatorExpression extends OperatorExpression { … public abstract Value<?> calc(Value<?> left, Value<?> right); }

Después de declarar las clases de operadores base, podemos crear implementaciones más detalladas:

3.4.1 ¡NO !

Este operador solo funcionará con LogicalValue devolviendo la nueva instancia de LogicalValue con valor invertido:

 public class NotOperator extends UnaryOperatorExpression { ... @Override public Value<?> calc(Value<?> value) { if (value instanceof LogicalValue) { return new LogicalValue(!((LogicalValue) value.getValue()).getValue()); } else { throw new ExecutionException(String.format("Unable to perform NOT operator for non logical value `%s`", value)); } } }

Ahora cambiaremos a las implementaciones de BinaryOperatorExpression con dos operandos:

3.4.2 Suma +

La primera es la suma. El método calc() hará la adición de objetos NumericValue . Para los otros tipos de valor, concatenaremos los valores de String toString() que devuelven la instancia TextValue :

 public class AdditionOperator extends BinaryOperatorExpression { public AdditionOperator(Expression left, Expression right) { super(left, right); } @Override public Value<?> calc(Value<?> left, Value<?> right) { if (left instanceof NumericValue && right instanceof NumericValue) { return new NumericValue(((NumericValue) left).getValue() + ((NumericValue) right).getValue()); } else { return new TextValue(left.toString() + right.toString()); } } }

3.4.3 Resta -

calc() hará una comparación de getValue() solo si ambos valores tienen el tipo NumericValue . En el otro caso, ambos valores se asignarán a la Cadena, eliminando las coincidencias del segundo valor del primer valor:

 public class SubtractionOperator extends BinaryOperatorExpression { ... @Override public Value<?> calc(Value<?> left, Value<?> right) { if (left instanceof NumericValue && right instanceof NumericValue) { return new NumericValue(((NumericValue) left).getValue() - ((NumericValue) right).getValue()); } else { return new TextValue(left.toString().replaceAll(right.toString(), "")); } } }

3.4.4 Igual ==

calc() hará una comparación de getValue() solo si ambos valores tienen el mismo tipo. En el otro caso, ambos valores se asignarán a la Cadena:

 public class EqualsOperator extends BinaryOperatorExpression { ... @Override public Value<?> calc(Value<?> left, Value<?> right) { boolean result; if (Objects.equals(left.getClass(), right.getClass())) { result = ((Comparable) left.getValue()).compareTo(right.getValue()) == 0; } else { result = ((Comparable) left.toString()).compareTo(right.toString()) == 0; } return new LogicalValue(result); } }

3.4.5 Menor que < y mayor que >

 public class LessThanOperator extends BinaryOperatorExpression { ... @Override public Value<?> calc(Value<?> left, Value<?> right) { boolean result; if (Objects.equals(left.getClass(), right.getClass())) { result = ((Comparable) left.getValue()).compareTo(right.getValue()) < 0; } else { result = left.toString().compareTo(right.toString()) < 0; } return new LogicalValue(result); } } public class GreaterThanOperator extends BinaryOperatorExpression { ... @Override public Value<?> calc(Value<?> left, Value<?> right) { boolean result; if (Objects.equals(left.getClass(), right.getClass())) { result = ((Comparable) left.getValue()).compareTo(right.getValue()) > 0; } else { result = left.toString().compareTo(right.toString()) > 0; } return new LogicalValue(result); } }

3.4.6 Operador de valor de estructura ::

Para leer el valor de un argumento de estructura, esperamos recibir el valor de la izquierda como un tipo de valor de StructureValue :

 public class StructureValueOperator extends BinaryOperatorExpression { ... @Override public Value<?> calc(Value<?> left, Value<?> right) { if (left instanceof StructureValue) return ((StructureValue) left).getValue().getArgumentValue(right.toString()); return left; } }

3.5 Evaluación del valor

Si queremos pasar variables o implementaciones de Expression más complejas a los operadores, incluidos los propios operadores, necesitamos una forma de transformar el objeto Expression en Value . Para hacer esto, declaramos el método de evaluate() en nuestra interfaz de Expression :

 public interface Expression { Value<?> evaluate(); }

La clase de valor solo devolverá this instancia:

 public class Value<T extends Comparable<T>> implements Expression { ... @Override public Value<?> evaluate() { return this; } }

Para implementar la evaluate() para VariableExpression , primero debemos proporcionar la capacidad de obtener Value por el nombre de la variable. Delegamos este trabajo al campo Function que aceptará el nombre de la variable y devolverá el objeto Value correspondiente:

 ... public class VariableExpression implements Expression { ... private final Function<String, Value<?>> variableValue; @Override public Value<?> evaluate() { Value<?> value = variableValue.apply(name); if (value == null) { return new TextValue(name); } return value; } }

Para evaluar StructureExpression , crearemos una instancia de StructureValue . También necesitamos implementar el método getValue() faltante que aceptará un índice de argumento y devolverá un valor según el tipo de Expression :

 ... public class StructureExpression implements Expression, Comparable<StructureExpression> { ... @Override public Value<?> evaluate() { return new StructureValue(this); } private Value<?> getValue(int index) { Expression expression = values.get(index); if (expression instanceof VariableExpression) { return variableValue.apply(((VariableExpression) expression).getName()); } else { return expression.evaluate(); } } }

Para las expresiones de operador, evaluamos los valores de los operandos y los pasamos al método calc() :

 public abstract class UnaryOperatorExpression extends OperatorExpression { ... @Override public Value<?> evaluate() { return calc(getValue().evaluate()); } } public abstract class BinaryOperatorExpression extends OperatorExpression { ... @Override public Value<?> evaluate() { return calc(getLeft().evaluate(), getRight().evaluate()); } }

3.6 Declaraciones

Antes de comenzar a crear nuestro analizador de sintaxis, debemos presentar un modelo para las declaraciones de nuestro lenguaje. Comencemos con la interfaz de Statement con el método de procedimiento de execute() que se llamará durante la ejecución del código:

 public interface Statement { void execute(); }

3.6.1 Imprimir declaración

La primera declaración que implementaremos es PrintStatement . Esta declaración necesita saber la expresión para imprimir. Nuestro lenguaje admitirá la impresión de literales, variables y otras expresiones implementando Expression que se evaluará durante la ejecución para calcular el objeto Value :

 @AllArgsConstructor @Getter public class PrintStatement implements Statement { private final Expression expression; @Override public void execute() { Value<?> value = expression.evaluate(); System.out.println(value); } }

3.6.2 Sentencia de asignación

Para declarar una asignación necesitamos saber el nombre de la variable y la expresión que queremos asignar. Nuestro lenguaje podrá asignar literales, variables y expresiones más complejas implementando la interfaz Expression :

 @AllArgsConstructor @Getter public class AssignStatement implements Statement { private final String name; private final Expression expression; @Override public void execute() { ... } }

Durante la ejecución, necesitamos almacenar los valores de las variables en algún lugar. Deleguemos esta lógica al campo BiConsumer que pasará un nombre de variable y el valor asignado. Tenga en cuenta que el valor de Expression debe evaluarse al realizar una tarea:

 ... public class AssignStatement implements Statement { ... private final BiConsumer<String, Value<?>> variableSetter; @Override public void execute() { variableSetter.accept(name, expression.evaluate()); } }

3.6.3 Declaración de entrada

Para leer una expresión desde la consola, necesitamos saber el nombre de la variable para asignarle un valor. Durante la execute() debemos leer una línea desde la consola. Este trabajo se puede delegar al Supplier , por lo que no crearemos múltiples flujos de entrada. Después de leer la línea, la analizamos en el objeto Value correspondiente y delegamos la asignación a la instancia de BiConsumer como lo hicimos para AssignStatement :

 @AllArgsConstructor @Getter public class InputStatement implements Statement { private final String name; private final Supplier<String> consoleSupplier; private final BiConsumer<String, Value<?>> variableSetter; @Override public void execute() { //just a way to tell the user in which variable the entered value will be assigned System.out.printf("enter \"%s\" >>> ", name.replace("_", " ")); String line = consoleSupplier.get(); Value<?> value; if (line.matches("[0-9]+")) { value = new NumericValue(Integer.parseInt(line)); } else if (line.matches("true|false")) { value = new LogicalValue(Boolean.valueOf(line)); } else { value = new TextValue(line); } variableSetter.accept(name, value); } }

3.6.4 Declaración de condición

Primero, presentaremos la clase CompositeStatement que contendrá una lista interna de declaraciones para ejecutar:

 @Getter public class CompositeStatement implements Statement { private final List<Statement> statements2Execute = new ArrayList<>(); public void addStatement(Statement statement) { if (statement != null) statements2Execute.add(statement); } @Override public void execute() { statements2Execute.forEach(Statement::execute); } }

Esta clase se puede reutilizar más tarde en caso de que creemos una construcción de sentencias compuestas. La primera de las construcciones será la declaración de Condition . Para describir la condición podemos usar literales, variables y construcciones más complejas implementando la interfaz Expression . Al final, durante la ejecución, calculamos el valor de la Expression y nos aseguramos de que el valor sea Lógico y que el resultado interno sea verdadero. Solo en este caso podemos realizar sentencias internas:

 @RequiredArgsConstructor @Getter public class ConditionStatement extends CompositeStatement { private final Expression condition; @Override public void execute() { Value<?> value = condition.evaluate(); if (value instanceof LogicalValue) { if (((LogicalValue) value).getValue()) { super.execute(); } } else { throw new ExecutionException(String.format("Cannot compare non logical value `%s`", value)); } } }

3.7 Analizador de declaraciones

Ahora que tenemos las declaraciones para trabajar con nuestros lexemas, ahora podemos construir el StatementParser . Dentro de la clase declaramos una lista de tokens y variables de posición de tokens mutables:

 public class StatementParser { private final List<Token> tokens; private int position; public StatementParser(List<Token> tokens) { this.tokens = tokens; } ... }

Luego creamos el método parseExpression() que manejará los tokens proporcionados y devolverá una declaración completa:

 public Statement parseExpression() { ... }

Las expresiones de nuestro lenguaje solo pueden comenzar declarando una variable o una palabra clave. Por lo tanto, primero necesitamos leer un token y validar que tenga el tipo de token Variable o Keyword . Para manejar esto, declaramos un método next() separado con tipos de token varargs como argumento que validará que el próximo token tenga el mismo tipo. En el caso real, incrementamos el campo de posición de StatementParser y devolvemos el token encontrado:

 private Statement parseExpression() { Token token = next(TokenType.Keyword, TokenType.Variable); ... } private Token next(TokenType type, TokenType... types) { TokenType[] tokenTypes = org.apache.commons.lang3.ArrayUtils.add(types, type); if (position < tokens.size()) { Token token = tokens.get(position); if (Stream.of(tokenTypes).anyMatch(t -> t == token.getType())) { position++; return token; } } Token previousToken = tokens.get(position - 1); throw new SyntaxException(String.format("After `%s` declaration expected any of the following lexemes `%s`", previousToken, Arrays.toString(tokenTypes))); }

Una vez que hayamos encontrado el token apropiado, podemos construir nuestra declaración según el tipo de token.

3.7.1 Variables

Cada asignación de variable comienza con el tipo de token Variable , que ya leímos. El siguiente token que esperamos es el operador equals = . Puede anular el método next() que aceptará TokenType con la representación del operador String (por ejemplo, = ) y devolverá el siguiente token encontrado solo si tiene el mismo tipo y valor que el solicitado:

 public Statement parseExpression() { Token token = next(TokenType.Keyword, TokenType.Variable); switch (token.getType()) { case Variable: next(TokenType.Operator, "="); //skip equals Expression value; if (peek(TokenType.Keyword, "new")) { value = readInstance(); } else { value = readExpression(); } return new AssignStatement(token.getValue(), value, variables::put); } ... }

Después del operador igual, leemos una expresión. Una expresión puede comenzar con la new palabra clave cuando instanciamos una estructura. Cubriremos este caso un poco más adelante. Para consumir un token con la intención de validar su valor sin incrementar la posición y arrojar un error, crearemos un método peek() adicional que devolverá el valor verdadero si el próximo token es el mismo que esperamos:

 ... private boolean peek(TokenType type, String value) { if (position < tokens.size()) { Token token = tokens.get(position); return type == token.getType() && token.getValue().equals(value); } return false; } ...

Para crear una instancia de AssignStatement necesitamos pasar un objeto BiConsumer al constructor. Vayamos a la StatementParser de campos de StatementParser y agreguemos un nuevo campo de variables de mapa que almacenará el nombre de la variable como una clave y el valor de la variable como un valor:

 public class StatementParser { ... private final Map<String, Value<?>> variables; public StatementParser(List<Token> tokens) { ... this.variables = new HashMap<>(); } ... }

expresión variable

Primero, cubriremos la lectura de expresión de variable simple que puede ser un literal, otra variable o una expresión más compleja con operadores. Por lo tanto, el método readExpression() devolverá la Expression con las implementaciones correspondientes. Dentro de este método, declaramos la instancia de Expression izquierda. Una expresión puede comenzar solo con un literal o con otra variable. Por lo tanto, esperamos obtener el tipo de token Variable , Numeric , Logical o Text de nuestro método next() . Después de leer un token adecuado, lo transformamos en el objeto Expression apropiado dentro del siguiente bloque de interruptores y lo asignamos a la variable Expression de la izquierda:

 private Expression readExpression() { Expression left; Token token = next(TokenType.Variable, TokenType.Numeric, TokenType.Logical, TokenType.Text); String value = token.getValue(); switch (token.getType()) { case Numeric: left = new NumericValue(Integer.parseInt(value)); case Logical: left = new LogicalValue(Boolean.valueOf(value)); case Text: left = new TextValue(value); case Variable: default: left = new VariableExpression(value, variables::get); } ... }

Después de leer la variable izquierda o el literal, esperamos capturar un lexema de Operator :

 private Expression readExpression() { Expression left; Token token = next(TokenType.Variable, TokenType.Numeric, TokenType.Logical, TokenType.Text); String value = token.getValue(); switch (token.getType()) { ... } Token operation = next(TokenType.Operator); Class<? extends OperatorExpression> operatorType = Operator.getType(operation.getValue()); ... }

Luego mapeamos nuestro lexema de Operator al objeto OperatorExpression . Para hacerlo, puede usar un bloque de cambio que devuelva la clase OperatorExpression adecuada según el valor del token. Usaré constantes de enumeración con un tipo de expresión de OperatorExpression apropiado:

 @RequiredArgsConstructor @Getter public enum Operator { Not("!", NotOperator.class), Addition("+", AdditionOperator.class), Subtraction("-", SubtractionOperator.class), Equality("==", EqualsOperator.class), GreaterThan(">", GreaterThanOperator.class), LessThan("<", LessThanOperator.class), StructureValue("::", StructureValueOperator.class); private final String character; private final Class<? extends OperatorExpression> operatorType; public static Class<? extends OperatorExpression> getType(String character) { return Arrays.stream(values()) .filter(t -> Objects.equals(t.getCharacter(), character)) .map(Operator::getOperatorType) .findAny().orElse(null); } }

Al final, leemos el literal o la variable de la derecha como lo hicimos con la Expression de la izquierda. Para no duplicar el código, extraemos la Expression de lectura en un método nextExpression() separado:

 private Expression nextExpression() { Token token = next(TokenType.Variable, TokenType.Numeric, TokenType.Logical, TokenType.Text); String value = token.getValue(); switch (token.getType()) { case Numeric: return new NumericValue(Integer.parseInt(value)); case Logical: return new LogicalValue(Boolean.valueOf(value)); case Text: return new TextValue(value); case Variable: default: return new VariableExpression(value, variables::get); } }

Refactoricemos el método readExpression() y leamos el lexema correcto usando nextExpression() . Pero antes de leer el lexema correcto, debemos estar seguros de que nuestro operador admite dos operandos. Podemos verificar si nuestro operador extiende BinaryOperatorExpression . En el otro caso, si el operador es unario, creamos un OperatorExpression solo usando la expresión de la izquierda. Para crear un objeto OperatorExpression , recuperamos el constructor adecuado para la implementación del operador unario o binario y luego creamos una instancia con las expresiones anteriores obtenidas:

 @SneakyThrows private Expression readExpression() { Expression left = nextExpression(); Token operation = next(TokenType.Operator); Class<? extends OperatorExpression> operatorType = Operator.getType(operation.getValue()); if (BinaryOperatorExpression.class.isAssignableFrom(operatorType)) { Expression right = nextExpression(); return operatorType .getConstructor(Expression.class, Expression.class) .newInstance(left, right); } else if (UnaryOperatorExpression.class.isAssignableFrom(operatorType)) { return operatorType .getConstructor(Expression.class) .newInstance(left); } return left; }

Además, podemos brindar la oportunidad de crear una expresión larga con múltiples operadores o sin operadores con solo un literal o variable. Incluyamos la operación read en el bucle while con la condición de que tengamos un Operador como el siguiente lexema. Cada vez que creamos una expresión de OperatorExpression , la asignamos a la expresión de la izquierda, creando así un árbol de operadores posteriores dentro de una Expression hasta que leemos la expresión completa. Al final devolvemos la expresión de la izquierda:

 @SneakyThrows private Expression readExpression() { Expression left = nextExpression(); //recursively read an expression while (peek(TokenType.Operator)) { Token operation = next(TokenType.Operator); Class<? extends OperatorExpression> operatorType = Operator.getType(operation.getValue()); if (BinaryOperatorExpression.class.isAssignableFrom(operatorType)) { Expression right = nextExpression(); left = operatorType .getConstructor(Expression.class, Expression.class) .newInstance(left, right); } else if (UnaryOperatorExpression.class.isAssignableFrom(operatorType)) { left = operatorType .getConstructor(Expression.class) .newInstance(left); } } return left; } private boolean peek(TokenType type) { if (position < tokens.size()) { Token token = tokens.get(position); return token.getType() == type; } return false; }

Instancia de estructura

Después de completar la implementación de readExpression() , podemos volver a parseExpression() y finalizar la implementación de readInstance() para instanciar una instancia de estructura:

De acuerdo con la semántica de nuestro lenguaje, sabemos que la creación de instancias de nuestra estructura comienza con la new palabra clave, podemos omitir el siguiente token llamando al método next() . El siguiente lexema significará el nombre de la estructura, lo leemos como el tipo de token Variable . Después del nombre de la estructura, esperamos recibir argumentos entre corchetes como divisores de grupo. En algunos casos, nuestra estructura se puede crear sin ningún tipo de argumento. Por lo tanto, usamos peek() primero. Cada argumento que se pasa a la estructura puede significar una expresión, por lo que llamamos a readExpression() y pasamos el resultado a la lista de argumentos. Después de construir argumentos de estructura, podemos construir nuestra StructureExpression preliminarmente recuperando la StructureDefinition apropiada:

 private Expression readInstance() { next(TokenType.Keyword, "new"); //skip new Token type = next(TokenType.Variable); List<Expression> arguments = new ArrayList<>(); if (peek(TokenType.GroupDivider, "[")) { next(TokenType.GroupDivider, "["); //skip open square bracket while (!peek(TokenType.GroupDivider, "]")) { Expression value = readExpression(); arguments.add(value); } next(TokenType.GroupDivider, "]"); //skip close square bracket } StructureDefinition definition = structures.get(type.getValue()); if (definition == null) { throw new SyntaxException(String.format("Structure is not defined: %s", type.getValue())); } return new StructureExpression(definition, arguments, variables::get); }

Para recuperar la definición de StructureDefinition por nombre, debemos declarar el mapa de estructuras como el campo de StatementParser , lo completaremos más tarde durante el análisis de palabras clave de struct :

 public class StatementParser { ... private final Map<String, StructureDefinition> structures; public StatementParser(List<Token> tokens) { ... this.structures = new HashMap<>(); } ... }

3.7.2 Palabra clave

Ahora podemos continuar trabajando en el método parseExpression() cuando recibamos el lexema de la Keyword :

 public Statement parseExpression() { ... switch (token.getType()) { case Variable: ... case Keyword: switch (token.getValue()) { case "print": case "input": case "if": case "struct": } ... } }

Nuestra expresión de lenguaje puede comenzar con las palabras clave print , input , if y struct .

Impresión

Para leer el valor de impresión, llamamos al método readExpression() ya creado. Leerá una implementación de Expression literal, variable o más compleja como lo hicimos para la asignación de variables. Luego creamos y devolvemos una instancia de PrintStatement :

 ... case "print": Expression expression = readExpression(); return new PrintStatement(expression); ...

Aporte

Para la declaración de entrada, necesitamos saber el nombre de la variable al que asignamos valor. Por lo tanto, le pedimos al método next() que capture el siguiente token de Variable por nosotros:

 ... case "input": Token variable = next(TokenType.Variable); return new InputStatement(variable.getValue(), scanner::nextLine, variables::put); ...

Para crear una instancia de InputStatement introducimos un objeto Scanner en la StatementParser de campos de StatementParser que nos ayudará a leer una línea desde la consola:

 public class StatementParser { ... private final Scanner scanner; public StatementParser(List<Token> tokens) { ... this.scanner = new Scanner(System.in); } ... }

Si

La siguiente declaración que tocaremos es la condición if/then :

En primer lugar, cuando recibimos la palabra clave if , leemos la expresión de la condición llamando a readExpression() . Luego, de acuerdo con la semántica de nuestro lenguaje, necesitamos captar la palabra clave then . Dentro de nuestra condición podemos declarar otras declaraciones, incluidas otras declaraciones de condición. Por lo tanto, agregamos recursivamente parseExpression() a las declaraciones internas de la condición hasta que leamos la palabra clave end :

 ... case "if": Expression condition = readExpression(); next(TokenType.Keyword, "then"); //skip then ConditionStatement conditionStatement = new ConditionStatement(condition); while (!peek(TokenType.Keyword, "end")) { Statement statement = parseExpression(); conditionStatement.addStatement(statement); } next(TokenType.Keyword, "end"); //skip end return conditionStatement; ...

estructura

La declaración de estructura es bastante simple porque consta solo de tipos de token Variable y Keyword . Después de leer la palabra clave struct , esperamos leer el nombre de la estructura como tipo de token Variable . Luego leemos los argumentos hasta que terminamos con la palabra clave end . Al final, construimos nuestra definición de StructureDefinition y la colocamos en el mapa de estructuras para acceder a ella en el futuro cuando creemos una instancia de estructura:

 ... case "struct": Token type = next(TokenType.Variable); Set<String> args = new HashSet<>(); while (!peek(TokenType.Keyword, "end")) { next(TokenType.Keyword, "arg"); Token arg = next(TokenType.Variable); args.add(arg.getValue()); } next(TokenType.Keyword, "end"); //skip end structures.put(type.getValue(), new StructureDefinition(type.getValue(), new ArrayList<>(args))); return null; ...

El método parseExpression() completo:

 ... public Statement parseExpression() { Token token = next(TokenType.Keyword, TokenType.Variable); switch (token.getType()) { case Variable: next(TokenType.Operator, "="); //skip equals Expression value; if (peek(TokenType.Keyword, "new")) { value = readInstance(); } else { value = readExpression(); } return new AssignStatement(token.getValue(), value, variables::put); case Keyword: switch (token.getValue()) { case "print": Expression expression = readExpression(); return new PrintStatement(expression); case "input": Token variable = next(TokenType.Variable); return new InputStatement(variable.getValue(), scanner::nextLine, variables::put); case "if": Expression condition = readExpression(); next(TokenType.Keyword, "then"); //skip then ConditionStatement conditionStatement = new ConditionStatement(condition); while (!peek(TokenType.Keyword, "end")) { Statement statement = parseExpression(); conditionStatement.addStatement(statement); } next(TokenType.Keyword, "end"); //skip end return conditionStatement; case "struct": Token type = next(TokenType.Variable); Set<String> args = new HashSet<>(); while (!peek(TokenType.Keyword, "end")) { next(TokenType.Keyword, "arg"); Token arg = next(TokenType.Variable); args.add(arg.getValue()); } next(TokenType.Keyword, "end"); //skip end structures.put(type.getValue(), new StructureDefinition(type.getValue(), new ArrayList<>(args))); return null; } default: throw new SyntaxException(String.format("Statement can't start with the following lexeme `%s`", token)); } } ...

Para encontrar y acumular todas las declaraciones, creamos el método parse() que analizará todas las expresiones de los tokens dados y devolverá la instancia de CompositeStatement :

 ... public Statement parse() { CompositeStatement root = new CompositeStatement(); while (position < tokens.size()) { Statement statement = parseExpression(); root.addStatement(statement); } return root; } ...

4 Idioma del juguete

Terminamos con el analizador léxico y sintáctico. Ahora podemos reunir ambas implementaciones en la clase ToyLanguage y finalmente ejecutar nuestro lenguaje:

 public class ToyLanguage { @SneakyThrows public void execute(Path path) { String source = Files.readString(path); LexicalParser lexicalParser = new LexicalParser(source); List<Token> tokens = lexicalParser.parse(); StatementParser statementParser = new StatementParser(tokens); Statement statement = statementParser.parse(); statement.execute(); } }

5 Resumiendo

En este tutorial, construimos nuestro propio lenguaje con análisis léxico y sintáctico. Espero que este artículo sea útil para alguien. Le recomiendo que intente escribir su propio idioma, a pesar de que debe comprender muchos detalles de implementación. ¡Este es un experimento interesante, de aprendizaje y de superación personal!