从头开始构建您自己的编程语言：第七部分 - 类

在创建您自己的编程语言的这一部分，我们将实现类作为对先前定义的结构的扩展。请查看前面的部分： 从零开始构建你自己的编程语言 从头开始构建您自己的编程语言：第二部分 - Dijkstra 的双栈算法 构建您自己的编程语言第 III 部分：使用 Regex Lookaheads 改进词法分析 从头开始构建您自己的编程语言第四部分：实现函数 从头开始构建您自己的编程语言：第五部分 - 数组 从头开始构建您自己的编程语言：第六部分 - 循环 完整的源代码可用 在 GitHub 上 . 1.词法分析 在第一部分中，我们将介绍词法分析。简而言之，就是将源代码分解成语言词素的过程，如关键字、变量、运算符等。 您可能还记得之前的部分，我在 枚举中使用正则表达式来定义所有词位类型。 TokenType 让我们看看下面的类原型并将缺少的正则表达式部分添加到我们的 词素中： TokenType 首先，我们需要将 词放在 lexeme 的表达式中，让词法分析器知道我们的类声明从哪里开始： class Keyword 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; } 其次，我们需要新的 词素作为对当前对象的引用的标记： This public enum TokenType { ... This("(this)(?=,|\\s|$)"); private final String regex; } 2.语法分析 在第二部分中，我们将从词法分析器接收到的词位转换为遵循我们的语言规则的最终语句。 2.1 定义范围 当我们声明一个类或函数时，该声明应该在定义的隔离范围内可用。例如，如果我们在下面的清单中声明了一个名为 的函数，那么声明之后就可以执行了： turn_on [] 但是，如果我们在类范围内声明相同的函数，将不再直接从主块访问该函数： 为了实现这些定义边界，我们将创建 类并将所有声明的定义存储在类和函数的两个集合中： DefinitionScope package org.example.toylanguage.context.definition; public class DefinitionScope { private final Set classes; private final Set functions; public DefinitionScope() { this.classes = new HashSet<>(); this.functions = new HashSet<>(); } } 此外，我们可能想要访问父级的定义范围。例如，如果我们声明两个单独的类并在第二个类中创建第一个类的实例： 为了提供这种能力，我们将添加 父实例作为对上层的引用，我们将使用它来爬升到顶层定义层。 DefinitionScope public class DefinitionScope { private final Set classes; private final Set functions; private final DefinitionScope parent; public DefinitionScope(DefinitionScope parent) { this.classes = new HashSet<>(); this.functions = new HashSet<>(); this.parent = parent; } } 现在，让我们通过提供接口来完成实现，以添加定义并使用父作用域按名称检索它： public class DefinitionScope { … public ClassDefinition getClass(String name) { Optional 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 = 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); } } 最后，为了管理声明的定义范围并在它们之间切换，我们使用 集合（后进先出）创建上下文类： java.util.Stack package org.example.toylanguage.context.definition; public class DefinitionContext { private final static Stack 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 内存范围 在本节中，我们将介绍 来管理类和函数变量。 MemoryScope 每个声明的变量，类似于类或函数定义，应该只能在隔离的代码块中访问。例如，如果我们在下面的清单中定义了一个变量，您可以在声明之后立即访问它： 但是，如果我们在函数或类中声明一个变量，该变量将不再可从主（上）代码块中获得： 为了实现此逻辑并存储在特定范围内定义的变量，我们创建了 类，该类将包含一个映射，其中变量名称作为键，变量 作为值： MemoryScope Value public class MemoryScope { private final Map > variables; public MemoryScope() { this.variables = new HashMap<>(); } } 接下来，与 类似，我们提供对父级范围变量的访问： DefinitionScope public class MemoryScope { private final Map > variables; private final MemoryScope parent; public MemoryScope(MemoryScope parent) { this.variables = new HashMap<>(); this.parent = parent; } } 接下来，我们添加获取和设置变量的方法。当我们设置一个变量时，如果上层 层已经有定义的变量，我们总是重新赋值之前设置的值： MemoryScope 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); } } 除了 和 方法之外，我们还添加了两个实现来与 的当前（本地）层进行交互： set get MemoryScope public class MemoryScope { ... public Value getLocal(String name) { return variables.get(name); } public void setLocal(String name, Value value) { variables.put(name, value); } } 这些方法稍后将用于初始化函数参数或类的实例参数。例如，如果我们创建 类的实例并传递预定义的全局 变量，则当我们尝试更新 属性时不应更改此变量： Lamp type lamp_instance :: type 最后，为了管理变量和在内存范围之间切换，我们使用 集合创建 实现： java.util.Stack MemoryContext package org.example.toylanguage.context; public class MemoryContext { private static final Stack 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 类定义 在本节中，我们将读取和存储类定义。 首先，我们创建 实现。每次我们创建类的实例时都会执行此语句： Statement package org.example.toylanguage.statement; public class ClassStatement { } 每个类都可以包含用于初始化和其他操作的嵌套语句，如构造函数。为了存储这些语句，我们扩展了包含要执行的嵌套语句列表的 ： CompositeStatement public class ClassStatement extends CompositeStatement { } 接下来，我们声明 来存储类名、它的参数、构造函数语句以及类函数的定义范围： ClassDefinition 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 arguments; private final ClassStatement statement; private final DefinitionScope definitionScope; } 现在，我们已准备好使用 读取类声明。当我们遇到带有 值的关键字词素时，首先我们需要读取方括号内的类名及其参数： StatementParser class package org.example.toylanguage; public class StatementParser { ... private void parseClassDefinition() { Token type = tokens.next(TokenType.Variable); List 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 } } } 在参数之后，我们期望读取嵌套的构造函数语句： 为了存储这些语句，我们创建了先前定义的 的实例： ClassStatement private void parseClassDefinition() { ... ClassStatement classStatement = new ClassStatement(); } 除了参数和嵌套语句之外，我们的类还可以包含函数。为了使这些函数只能在类定义中访问，我们初始化了一个新的 层： DefinitionScope private void parseClassDefinition() { ... ClassStatement classStatement = new ClassStatement(); DefinitionScope classScope = DefinitionContext.newScope(); } 接下来，我们初始化 的实例并将其放入 ： ClassDefinition 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); } 最后，为了读取类构造函数语句和函数，我们调用静态 方法，该方法将收集 实例中的语句，直到我们遇到必须在最后跳过的终结 词位： StatementParser#parse() classStatement end private void parseClassDefinition() { ... //parse class statements StatementParser.parse(this, classStatement, classScope); tokens.next(TokenType.Keyword, "end"); } 2.4 类实例 此时，我们已经可以读取带有构造函数语句和函数的类定义。现在，让我们解析类的实例： 首先，我们定义 ，它将包含每个类实例的状态。与函数不同，类应该有一个永久的 ，并且每次我们与类实例交互时，这个范围应该对所有类的实例参数和状态变量可用： ClassValue MemoryScope public class ClassValue extends IterableValue { private final MemoryScope memoryScope; public ClassValue(ClassDefinition definition, MemoryScope memoryScope) { super(definition); this.memoryScope = memoryScope; } } 接下来，我们提供使用 处理类实例属性的方法： MemoryContext public class ClassValue extends IterableValue { 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); } } 请注意，通过调用 和 方法，我们使用 变量的当前层。但是在访问类的实例状态之前，我们需要将其 放入 并在完成时释放它： MemoryScope#getLocal() MemoryScope#setLocal() MemoryScope MemoryScope MemoryContext public class ClassValue extends IterableValue { ... 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(); } } } 接下来，我们可以实现剩余的 ，用于在语法分析期间构造定义的类实例。为了声明类的实例定义，我们提供了 和 参数列表，它们将在语句执行期间转换为最终的 实例： ClassExpression ClassDefinition Expression Value package org.example.toylanguage.expression; @RequiredArgsConstructor @Getter public class ClassExpression implements Expression { private final ClassDefinition definition; private final List arguments; @Override public Value evaluate() { ... } } 让我们实现 方法，该方法将在执行期间用于创建先前定义的 的实例。首先，我们将 参数评估为 参数： Expression#evaluate() ClassValue Expression Value @Override public Value evaluate() { //initialize class arguments List > values = arguments.stream() .map(Expression::evaluate) .collect(Collectors.toList()); } 接下来，我们创建一个空的内存范围，它应该与其他变量隔离并且只能包含类的实例状态变量： @Override public Value evaluate() { //initialize class arguments List > 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(); } } 接下来，我们创建一个 的实例，并将该类的 参数写入隔离的内存范围： ClassValue Value 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(); } 请注意，在设置空 之前，我们将 参数转换为 参数。否则，我们将无法访问类的实例参数，例如： MemoryScope Expression Value 最后，我们可以执行 。但在此之前，我们应该将类的 设置为能够在构造函数语句中访问类的函数： ClassStatement DefinitionScope 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*。最后一件事，我们可以使类更加灵活，并允许用户在声明类定义之前创建类实例： 这可以通过将 初始化委托给 并仅在我们评估表达式时访问它来完成： ClassDefinition DefinitionContext public class ClassExpression implements Expression { private final String name; private final List arguments; @Override public Value evaluate() { //get class's definition and statement ClassDefinition definition = DefinitionContext.getScope().getClass(name); ... } } 您可以对 执行相同的委托以在定义之前调用函数。 FunctionExpression 最后，我们可以使用 完成类实例的读取。 之间没有区别。我们只需要读取 参数并构造 ： ExpressionReader 先前定义的结构实例 Expression ClassExpression public class ExpressionReader ... // read class instance: new Class[arguments] private ClassExpression readClassInstance(Token token) { List 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 类函数 这时，我们就可以创建一个类，并执行该类的构造函数语句了。但是我们仍然无法执行该类的功能。 让我们重载 方法，该方法将接受 作为对我们要从中调用函数的类实例的引用： FunctionExpression#evaluate ClassValue package org.example.toylanguage.expression; public class FunctionExpression implements Expression { ... public Value evaluate(ClassValue classValue) { } } 下一步是使用当前 将函数 参数转换为 参数： MemoryScope Expression Value public Value evaluate(ClassValue classValue) { //initialize function arguments List > values = argumentExpressions.stream() .map(Expression::evaluate) .collect(Collectors.toList()); } 接下来，我们需要将类的 和 传递给上下文： MemoryScope DefinitionScope ... //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); 最后，对于此实现，我们调用默认的 方法并传递评估的 参数： FunctionExpression#evaluate(List > values) Value public Value evaluate(ClassValue classValue) { //initialize function arguments List > 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(); } } 要调用类的函数，我们将使用双冒号 运算符。目前，此运算符由 ( ) 实现管理，它负责访问类的属性： :: ClassPropertyOperator StructureValueOperator 让我们改进它以支持具有相同双冒号 字符的函数调用： :: 只有当左边的表达式是 而第二个是 时，类的函数才能由这个运算符管理： ClassExpression 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. 总结 在这一部分中，我们实现了类。我们现在可以创建更复杂的东西，比如堆栈实现： 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