paint-brush
Construindo sua própria linguagem de programação do zero: Parte VII - Aulaspor@alexandermakeev
6,088 leituras
6,088 leituras

Construindo sua própria linguagem de programação do zero: Parte VII - Aulas

por Alexander Makeev22m2022/12/15
Read on Terminal Reader

Muito longo; Para ler

Nesta parte da criação de suas próprias linguagens de programação iremos implementar classes e no final iremos escrever a implementação real do Stack
featured image - Construindo sua própria linguagem de programação do zero: Parte VII - Aulas
Alexander Makeev HackerNoon profile picture

Nesta parte da criação de sua própria linguagem de programação, vamos implementar classes como uma extensão sobre as estruturas definidas anteriormente. Confira as partes anteriores:


  1. Construindo sua própria linguagem de programação do zero
  2. Construindo sua própria linguagem de programação do zero: Parte II - Algoritmo de duas pilhas de Dijkstra
  3. Crie sua própria linguagem de programação Parte III: Melhorando a análise léxica com Regex Lookaheads
  4. Construindo sua própria linguagem de programação do zero Parte IV: Implementando funções
  5. Construindo sua própria linguagem de programação do zero: Parte V - Arrays
  6. Construindo sua própria linguagem de programação do zero: Parte VI - Loops

O código-fonte completo está disponível lá no GitHub .


1. Análise Lexical

Na primeira seção, abordaremos a análise lexical. Resumindo, é um processo para dividir o código-fonte em lexemas de linguagem, como palavra-chave, variável, operador, etc.


Você deve se lembrar das partes anteriores que eu estava usando as expressões regex na enumeração TokenType para definir todos os tipos de lexemas.


Vejamos o seguinte protótipo de classe e adicionemos as partes regex que faltam aos nossos lexemas TokenType :


  1. Primeiro, precisamos colocar a palavra de class na expressão do lexema de palavra- Keyword para permitir que o analisador léxico saiba onde começa nossa declaração de classe:
 package org.example.toylanguage.token; ... public enum TokenType { ... Keyword("(if|elif|else|end|print|input|fun|return|loop|in|by|break|next|class)(?=\\s|$)"), ... private final String regex; }


  1. Em segundo lugar, precisamos do novo lexema This como um marcador para uma referência ao objeto atual:
 public enum TokenType { ... This("(this)(?=,|\\s|$)"); private final String regex; }


2. Análise de Sintaxe

Na segunda seção, transformaremos os lexemas recebidos do analisador léxico em enunciados finais seguindo nossas regras linguísticas.

2.1 Escopo da Definição

Quando declaramos uma classe ou função, esta declaração deve estar disponível dentro dos limites isolados definidos. Por exemplo, se declararmos uma função chamada turn_on [] na listagem a seguir, ela estará disponível para execução após a declaração:


Mas se declararmos a mesma função dentro do escopo de uma classe, esta função não será mais acessada diretamente do bloco principal:


  1. Para implementar esses limites de definição, criaremos a classe DefinitionScope e armazenaremos todas as definições declaradas dentro de dois conjuntos para classes e funções:
 package org.example.toylanguage.context.definition; public class DefinitionScope { private final Set<ClassDefinition> classes; private final Set<FunctionDefinition> functions; public DefinitionScope() { this.classes = new HashSet<>(); this.functions = new HashSet<>(); } }


  1. Além disso, podemos querer acessar o escopo de definição do pai. Por exemplo, se declararmos duas classes separadas e criarmos uma instância da primeira classe dentro da segunda:


Para fornecer essa capacidade, adicionaremos a instância pai DefinitionScope como uma referência à camada superior, que usaremos para subir até a camada de definição superior.

 public class DefinitionScope { private final Set<ClassDefinition> classes; private final Set<FunctionDefinition> functions; private final DefinitionScope parent; public DefinitionScope(DefinitionScope parent) { this.classes = new HashSet<>(); this.functions = new HashSet<>(); this.parent = parent; } }


  1. Agora, vamos terminar a implementação fornecendo as interfaces para adicionar uma definição e recuperá-la pelo nome usando o escopo pai:
 public class DefinitionScope { … public ClassDefinition getClass(String name) { Optional<ClassDefinition> classDefinition = classes.stream() .filter(t -> t.getName().equals(name)) .findAny(); if (classDefinition.isPresent()) return classDefinition.get(); else if (parent != null) return parent.getClass(name); else throw new ExecutionException(String.format("Class is not defined: %s", name)); } public void addClass(ClassDefinition classDefinition) { classes.add(classDefinition); } public FunctionDefinition getFunction(String name) { Optional<FunctionDefinition> functionDefinition = functions.stream() .filter(t -> t.getName().equals(name)) .findAny(); if (functionDefinition.isPresent()) return functionDefinition.get(); else if (parent != null) return parent.getFunction(name); else throw new ExecutionException(String.format("Function is not defined: %s", name)); } public void addFunction(FunctionDefinition functionDefinition) { functions.add(functionDefinition); } }


  1. Por fim, para gerenciar os escopos de definição declarados e alternar entre eles, criamos a classe de contexto usando a coleção java.util.Stack (LIFO):
 package org.example.toylanguage.context.definition; public class DefinitionContext { private final static Stack<DefinitionScope> scopes = new Stack<>(); public static DefinitionScope getScope() { return scopes.peek(); } public static DefinitionScope newScope() { return new DefinitionScope(scopes.isEmpty() ? null : scopes.peek()); } public static void pushScope(DefinitionScope scope) { scopes.push(scope); } public static void endScope() { scopes.pop(); } }


2.2 Escopo de memória

Nesta seção, abordaremos o MemoryScope para gerenciar variáveis de classe e função.


  1. Cada variável declarada, de forma semelhante à definição de classe ou função, deve ser acessível apenas dentro de um bloco de código isolado. Por exemplo, se definirmos uma variável na listagem a seguir, você pode acessá-la logo após a declaração:


Mas se declararmos uma variável dentro de uma função ou classe, a variável não estará mais disponível no bloco de código principal (superior):


Para implementar essa lógica e armazenar variáveis definidas em um escopo específico, criamos a classe MemoryScope que conterá um mapa com o nome da variável como chave e a variável Value como valor:

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


  1. Em seguida, de forma semelhante ao DefinitionScope , fornecemos acesso às variáveis de escopo do pai:
 public class MemoryScope { private final Map<String, Value<?>> variables; private final MemoryScope parent; public MemoryScope(MemoryScope parent) { this.variables = new HashMap<>(); this.parent = parent; } }


  1. Em seguida, adicionamos métodos para obter e definir variáveis. Quando definimos uma variável, sempre reatribuímos o valor definido anteriormente se já houver uma variável definida na camada MemoryScope superior:
 public class MemoryScope { ... public Value<?> get(String name) { Value<?> value = variables.get(name); if (value != null) return value; else if (parent != null) return parent.get(name); else return NullValue.NULL_INSTANCE; } public void set(String name, Value<?> value) { MemoryScope variableScope = findScope(name); if (variableScope == null) { variables.put(name, value); } else { variableScope.variables.put(name, value); } } private MemoryScope findScope(String name) { if (variables.containsKey(name)) return this; return parent == null ? null : parent.findScope(name); } }


  1. Além dos métodos set e get , adicionamos mais duas implementações para interagir com a camada atual (local) do MemoryScope :
 public class MemoryScope { ... public Value<?> getLocal(String name) { return variables.get(name); } public void setLocal(String name, Value<?> value) { variables.put(name, value); } }


Esses métodos serão usados posteriormente para inicializar argumentos de função ou argumentos de instância de classe. Por exemplo, se criamos uma instância da classe Lamp e passamos a variável de type global pré-definida, esta variável não deve ser alterada quando tentamos atualizar a propriedade lamp_instance :: type :


  1. Por fim, para gerenciar variáveis e alternar entre escopos de memória, criamos a implementação MemoryContext usando a coleção java.util.Stack :
 package org.example.toylanguage.context; public class MemoryContext { private static final Stack<MemoryScope> scopes = new Stack<>(); public static MemoryScope getScope() { return scopes.peek(); } public static MemoryScope newScope() { return new MemoryScope(scopes.isEmpty() ? null : scopes.peek()); } public static void pushScope(MemoryScope scope) { scopes.push(scope); } public static void endScope() { scopes.pop(); } }


2.3 Definição de Classe

Nesta seção, leremos e armazenaremos as definições de classe.


  1. Primeiro, criamos a implementação da Declaração . Esta instrução será executada toda vez que criarmos uma instância de classe:
 package org.example.toylanguage.statement; public class ClassStatement { }


  1. Cada classe pode conter instruções aninhadas para inicialização e outras operações, como um construtor. Para armazenar essas instruções, estendemos o CompositeStatement que contém a lista de instruções aninhadas a serem executadas:
 public class ClassStatement extends CompositeStatement { }


  1. Em seguida, declaramos a ClassDefinition para armazenar o nome da classe, seus argumentos, instruções do construtor e o escopo da definição com as funções da classe:
 package org.example.toylanguage.context.definition; import java.util.List; @RequiredArgsConstructor @Getter @EqualsAndHashCode(onlyExplicitlyIncluded = true) public class ClassDefinition implements Definition { @EqualsAndHashCode.Include private final String name; private final List<String> arguments; private final ClassStatement statement; private final DefinitionScope definitionScope; }


  1. Agora, estamos prontos para ler a declaração da classe usando StatementParser . Quando encontramos o lexema de palavras-chave com valor de class , primeiro precisamos ler o nome da classe e seus argumentos dentro dos colchetes:


 package org.example.toylanguage; public class StatementParser { ... private void parseClassDefinition() { Token type = tokens.next(TokenType.Variable); List<String> arguments = new ArrayList<>(); if (tokens.peek(TokenType.GroupDivider, "[")) { tokens.next(TokenType.GroupDivider, "["); //skip opening square bracket while (!tokens.peek(TokenType.GroupDivider, "]")) { Token argumentToken = tokens.next(TokenType.Variable); arguments.add(argumentToken.getValue()); if (tokens.peek(TokenType.GroupDivider, ",")) tokens.next(); } tokens.next(TokenType.GroupDivider, "]"); //skip closing square bracket } } }


  1. Após os argumentos, esperamos ler as instruções do construtor aninhado:


Para armazenar essas instruções, criamos uma instância do ClassStatement definido anteriormente:

 private void parseClassDefinition() { ... ClassStatement classStatement = new ClassStatement(); }


  1. Além de argumentos e instruções aninhadas, nossas classes também podem conter funções. Para tornar essas funções acessíveis apenas dentro da definição de classe, inicializamos uma nova camada de DefinitionScope :
 private void parseClassDefinition() { ... ClassStatement classStatement = new ClassStatement(); DefinitionScope classScope = DefinitionContext.newScope(); }


  1. Em seguida, inicializamos uma instância de ClassDefinition e a colocamos no DefinitionContext :
 private void parseClassDefinition() { ... ClassStatement classStatement = new ClassStatement(); DefinitionScope classScope = DefinitionContext.newScope(); ClassDefinition classDefinition = new ClassDefinition(type.getValue(), arguments, classStatement, classScope); DefinitionContext.getScope().addClass(classDefinition); }


  1. Por fim, para ler as instruções e funções do construtor de classe, chamamos o método estático StatementParser#parse() que coletará as instruções dentro da instância classStatement até encontrarmos o lexema end de finalização que deve ser ignorado no final:
 private void parseClassDefinition() { ... //parse class statements StatementParser.parse(this, classStatement, classScope); tokens.next(TokenType.Keyword, "end"); }


2.4 Instância de Classe

Neste ponto, já podemos ler as definições de classe com instruções e funções do construtor. Agora, vamos analisar a instância da classe:


  1. Primeiro, definimos ClassValue , que conterá o estado de cada instância de classe. As classes, ao contrário das funções, devem ter um MemoryScope permanente e esse escopo deve estar disponível com todos os argumentos de instância da classe e variáveis de estado toda vez que interagirmos com a instância da classe:
 public class ClassValue extends IterableValue<ClassDefinition> { private final MemoryScope memoryScope; public ClassValue(ClassDefinition definition, MemoryScope memoryScope) { super(definition); this.memoryScope = memoryScope; } }


  1. Em seguida, fornecemos métodos para trabalhar com as propriedades de instância da classe usando MemoryContext :
 public class ClassValue extends IterableValue<ClassDefinition> { private final MemoryScope memoryScope; public ClassValue(ClassDefinition definition, MemoryScope memoryScope) { super(definition); this.memoryScope = memoryScope; } @Override public String toString() { return getValue().getArguments().stream() .map(t -> t + " = " + getValue(t)) .collect(Collectors.joining(", ", getValue().getName() + " [ ", " ]")); } public Value<?> getValue(String name) { Value<?> result = MemoryContext.getScope().getLocal(name); return result != null ? result : NULL_INSTANCE; } public void setValue(String name, Value<?> value) { MemoryContext.getScope().setLocal(name, value); } }


  1. Observe que ao chamar os MemoryScope#getLocal() e MemoryScope#setLocal() , trabalhamos com a camada atual de variáveis MemoryScope . Mas antes de acessar o estado da instância da classe, precisamos colocar seu MemoryScope no MemoryContext e liberá-lo quando terminarmos:
 public class ClassValue extends IterableValue<ClassDefinition> { ... public Value<?> getValue(String name) { MemoryContext.pushScope(memoryScope); try { Value<?> result = MemoryContext.getScope().getLocal(name); return result != null ? result : NULL_INSTANCE; } finally { MemoryContext.endScope(); } } public void setValue(String name, Value<?> value) { MemoryContext.pushScope(memoryScope); try { MemoryContext.getScope().setLocal(name, value); } finally { MemoryContext.endScope(); } } }


  1. Em seguida, podemos implementar a ClassExpression restante que será usada para construir instâncias de classe definidas durante a análise de sintaxe. Para declarar a definição da instância da classe, fornecemos a ClassDefinition e a lista de argumentos Expression que serão transformados nas instâncias finais do Value durante a execução da instrução:
 package org.example.toylanguage.expression; @RequiredArgsConstructor @Getter public class ClassExpression implements Expression { private final ClassDefinition definition; private final List<Expression> arguments; @Override public Value<?> evaluate() { ... } }


  1. Vamos implementar o método Expression#evaluate() que será utilizado durante a execução para criar uma instância do ClassValue definido anteriormente. Primeiro, avaliamos os argumentos Expression nos argumentos Value :
 @Override public Value<?> evaluate() { //initialize class arguments List<Value<?>> values = arguments.stream() .map(Expression::evaluate) .collect(Collectors.toList()); }


  1. Em seguida, criamos um escopo de memória vazio que deve ser isolado das outras variáveis e pode conter apenas as variáveis de estado da instância da classe:
 @Override public Value<?> evaluate() { //initialize class arguments List<Value<?>> values = arguments.stream().map(Expression::evaluate).collect(Collectors.toList()); //get class's definition and statement ClassStatement classStatement = definition.getStatement(); //set separate scope MemoryScope classScope = new MemoryScope(null); MemoryContext.pushScope(classScope); try { ... } finally { MemoryContext.endScope(); } }


  1. Em seguida, criamos uma instância de ClassValue e escrevemos os argumentos Value da classe no escopo de memória isolado:
 try { //initialize constructor arguments ClassValue classValue = new ClassValue(definition, classScope); IntStream.range(0, definition.getArguments().size()).boxed() .forEach(i -> MemoryContext.getScope() .setLocal(definition.getArguments().get(i), values.size() > i ? values.get(i) : NullValue.NULL_INSTANCE)); ... } finally { MemoryContext.endScope(); }


Observe que transformamos os argumentos Expression nos argumentos Value antes de configurar um MemoryScope vazio. Caso contrário, não conseguiremos acessar os argumentos de instância da classe, por exemplo:


  1. E, finalmente, podemos executar o ClassStatement . Mas antes disso, devemos definir o DefinitionScope da classe para poder acessar as funções da classe nas instruções do construtor:
 try { //initialize constructor arguments ClassValue classValue = new ClassValue(definition, classScope); ClassInstanceContext.pushValue(classValue); IntStream.range(0, definition.getArguments().size()).boxed() .forEach(i -> MemoryContext.getScope() .setLocal(definition.getArguments().get(i), values.size() > i ? values.get(i) : NullValue.NULL_INSTANCE)); //execute function body DefinitionContext.pushScope(definition.getDefinitionScope()); try { classStatement.execute(); } finally { DefinitionContext.endScope(); } return classValue; } finally { MemoryContext.endScope(); ClassInstanceContext.popValue(); }


9*. Uma última coisa, podemos tornar as classes mais flexíveis e permitir que um usuário crie instâncias de classe antes de declarar a definição de classe:


Isso pode ser feito delegando a inicialização de ClassDefinition para o DefinitionContext e acessando-o somente quando avaliamos uma expressão:

 public class ClassExpression implements Expression { private final String name; private final List<Expression> arguments; @Override public Value<?> evaluate() { //get class's definition and statement ClassDefinition definition = DefinitionContext.getScope().getClass(name); ... } }


Você pode fazer a mesma delegação para FunctionExpression invocar funções antes da definição.


  1. Por fim, podemos concluir a leitura das instâncias da classe com o ExpressionReader . Não há diferença entre as instâncias da estrutura previamente definidas . Precisamos apenas ler os argumentos Expression e construir a ClassExpression :
 public class ExpressionReader ... // read class instance: new Class[arguments] private ClassExpression readClassInstance(Token token) { List<Expression> arguments = new ArrayList<>(); if (tokens.peekSameLine(TokenType.GroupDivider, "[")) { tokens.next(TokenType.GroupDivider, "["); //skip opening square bracket while (!tokens.peekSameLine(TokenType.GroupDivider, "]")) { Expression value = ExpressionReader.readExpression(this); arguments.add(value); if (tokens.peekSameLine(TokenType.GroupDivider, ",")) tokens.next(); } tokens.next(TokenType.GroupDivider, "]"); //skip closing square bracket } return new ClassExpression(token.getValue(), arguments); } }


2.5 Função de Classe

Neste momento, podemos criar uma classe e executar as instruções do construtor da classe. Mas ainda não conseguimos executar as funções da classe.

  1. Vamos sobrecarregar o método FunctionExpression#evaluate que aceitará ClassValue como uma referência à instância da classe da qual queremos invocar uma função:
 package org.example.toylanguage.expression; public class FunctionExpression implements Expression { ... public Value<?> evaluate(ClassValue classValue) { } }


  1. A próxima etapa é transformar os argumentos da função Expression nos argumentos Value usando o MemoryScope atual:
 public Value<?> evaluate(ClassValue classValue) { //initialize function arguments List<Value<?>> values = argumentExpressions.stream() .map(Expression::evaluate) .collect(Collectors.toList()); }


  1. Em seguida, precisamos passar o MemoryScope e o DefinitionScope da classe para o contexto:
 ... //get definition and memory scopes from class definition ClassDefinition classDefinition = classValue.getValue(); DefinitionScope classDefinitionScope = classDefinition.getDefinitionScope(); //set class's definition and memory scopes DefinitionContext.pushScope(classDefinitionScope); MemoryContext.pushScope(memoryScope);


  1. Por fim, para esta implementação, invocamos o método padrão FunctionExpression#evaluate(List<Value<?>> values) e passamos os argumentos Value avaliados:
 public Value<?> evaluate(ClassValue classValue) { //initialize function arguments List<Value<?>> values = argumentExpressions.stream().map(Expression::evaluate).collect(Collectors.toList()); //get definition and memory scopes from class definition ClassDefinition classDefinition = classValue.getValue(); DefinitionScope classDefinitionScope = classDefinition.getDefinitionScope(); MemoryScope memoryScope = classValue.getMemoryScope(); //set class's definition and memory scopes DefinitionContext.pushScope(classDefinitionScope); MemoryContext.pushScope(memoryScope); try { //proceed function return evaluate(values); } finally { DefinitionContext.endScope(); MemoryContext.endScope(); } }


  1. Para invocar a função da classe, usaremos o operador de dois pontos :: . Atualmente, este operador é gerenciado pela implementação ClassPropertyOperator ( StructureValueOperator ), que é responsável por acessar as propriedades da classe:


Vamos melhorá-lo para oferecer suporte a invocações de função com os mesmos dois pontos duplos :: caractere:


A função da classe pode ser gerenciada por este operador somente quando a expressão da esquerda é a ClassExpression e a segunda é a FunctionExpression :

 package org.example.toylanguage.expression.operator; public class ClassPropertyOperator extends BinaryOperatorExpression implements AssignExpression { public ClassPropertyOperator(Expression left, Expression right) { super(left, right); } @Override public Value<?> evaluate() { Value<?> left = getLeft().evaluate(); if (left instanceof ClassValue) { if (getRight() instanceof VariableExpression) { // access class's property // new ClassInstance[] :: class_argument return ((ClassValue) left).getValue(((VariableExpression) getRight()).getName()); } else if (getRight() instanceof FunctionExpression) { // execute class's function // new ClassInstance[] :: class_function [] return ((FunctionExpression) getRight()).evaluate((ClassValue) left); } } throw new ExecutionException(String.format("Unable to access class's property `%s``", getRight())); } @Override public void assign(Value<?> value) { Value<?> left = getLeft().evaluate(); if (left instanceof ClassValue && getRight() instanceof VariableExpression) { String propertyName = ((VariableExpression) getRight()).getName(); ((ClassValue) left).setValue(propertyName, value); } } }


3. Conclusão

Nesta parte, implementamos classes. Agora podemos criar coisas mais complexas, como implementação de pilha:

 main [] fun main [] stack = new Stack [] loop num in 0..5 # push 0,1,2,3,4 stack :: push [ num ] end size = stack :: size [] loop i in 0..size # should print 4,3,2,1,0 print stack :: pop [] end end class Stack [] arr = {} n = 0 fun push [ item ] this :: arr << item n = n + 1 end fun pop [] n = n - 1 item = arr { n } arr { n } = null return item end fun size [] return this :: n end end