Создание собственного языка программирования с нуля: Часть VII — Классы
16 декабря 2022 г.В этой части создания собственного языка программирования мы будем реализовывать классы как расширение ранее определенных структур. Пожалуйста, ознакомьтесь с предыдущими частями:
- Создание собственного языка программирования с нуля
- Построение Ваш собственный язык программирования с нуля: часть II — двухстековый алгоритм Дейкстры
- Сборка Ваш собственный язык программирования, часть III: Улучшение лексического анализа с помощью регулярных выражений Lookaheads
- Создание собственного языка программирования С нуля, часть 4: реализация функций
- Создание собственного языка программирования с нуля : Часть V. Массивы
- Создание собственного языка программирования с нуля: Часть VI - Циклы< /а>
Полный исходный код доступен на GitHub. >
1. Лексический анализ
В первом разделе мы рассмотрим лексический анализ. Короче говоря, это процесс разделения исходного кода на языковые лексемы, такие как ключевое слово, переменная, оператор и т. д.
Возможно, вы помните из предыдущих частей, что я использовал выражения регулярных выражений в TokenType для определения всех типов лексем.
Давайте посмотрим на следующий прототип класса и добавим недостающие части регулярного выражения в наши лексемы TokenType:
1) Во-первых, нам нужно поместить слово 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;
}
2) Во-вторых, нам нужна новая лексема This в качестве маркера ссылки на текущий объект:
public enum TokenType {
...
This("(this)(?=,|s|$)");
private final String regex;
}
2. Синтаксический анализ
Во втором разделе мы преобразуем лексемы, полученные от лексического анализатора, в окончательные утверждения в соответствии с нашими языковыми правилами.
2.1 Область определения
Когда мы объявляем класс или функцию, это объявление должно быть доступно в определенных изолированных границах. Например, если мы объявим функцию с именем turn_on[] в следующем листинге, она будет доступна для выполнения после объявления:
Но если мы объявим ту же функцию внутри области видимости класса, доступ к этой функции больше не будет осуществляться напрямую из основного блока:
1) Чтобы реализовать эти границы определения, мы создадим класс DefinitionScope и будем хранить все объявленные определения внутри двух наборов для классов и функций:
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<>();
}
}
2) Кроме того, мы можем захотеть получить доступ к области определения родителя. Например, если мы объявим два отдельных класса и создадим экземпляр первого класса внутри второго:
Чтобы обеспечить эту возможность, мы добавим родительский экземпляр DefinitionScope в качестве ссылки на верхний уровень, который мы будем использовать для перехода к верхнему уровню определения.
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;
}
}
3) Теперь давайте закончим реализацию, предоставив интерфейсы для добавления определения и извлечения его по имени с использованием родительской области:
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);
}
}
4) Наконец, чтобы управлять объявленными областями определения и переключаться между ними, мы создаем класс контекста, используя коллекцию 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 Область памяти
В этом разделе мы рассмотрим MemoryScope для управления переменными класса и функции.
1) Каждая объявленная переменная, как и определение класса или функции, должна быть доступна только в пределах изолированного блока кода. Например, если мы определяем переменную в следующем листинге, вы можете получить к ней доступ сразу после объявления:
Но если мы объявим переменную внутри функции или класса, переменная больше не будет доступна из основного (верхнего) блока кода:
Чтобы реализовать эту логику и хранить переменные, определенные в определенной области, мы создаем класс MemoryScope, который будет содержать карту с именем переменной в качестве ключа и переменной Value в качестве значение:
public class MemoryScope {
private final Map<String, Value<?>> variables;
public MemoryScope() {
this.variables = new HashMap<>();
}
}
2) Далее, аналогично DefinitionScope, мы предоставляем доступ к переменным области видимости родителя:
public class MemoryScope {
private final Map<String, Value<?>> variables;
private final MemoryScope parent;
public MemoryScope(MemoryScope parent) {
this.variables = new HashMap<>();
this.parent = parent;
}
}
3) Далее добавляем методы для получения и установки переменных. Когда мы устанавливаем переменную, мы всегда повторно присваиваем ранее установленное значение, если уже есть определенная переменная в верхнем слое 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);
}
}
4) В дополнение к методам set и get добавляем еще две реализации для взаимодействия с текущим (локальным) слоем MemoryScope:< /p>
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 свойство:
5) Наконец, для управления переменными и переключения между областями памяти мы создаем реализацию MemoryContext с использованием коллекции 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 Определение класса
В этом разделе мы прочитаем и сохраним определения классов.
1) Сначала мы создаем оператор. реализация. Этот оператор будет выполняться каждый раз, когда мы создаем экземпляр класса:
package org.example.toylanguage.statement;
public class ClassStatement {
}
2) Каждый класс может содержать вложенные операторы для инициализации и других операций, таких как конструктор. Для хранения этих операторов мы расширяем CompositeStatement, который содержит список вложенных операторов для выполнения:
public class ClassStatement extends CompositeStatement {
}
3) Затем мы объявляем 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<String> arguments;
private final ClassStatement statement;
private final DefinitionScope definitionScope;
}
4) Теперь мы готовы прочитать объявление класса, используя Парсер операторов. Когда мы встречаем лексему Keyword со значением class, сначала нам нужно прочитать имя класса и его аргументы в квадратных скобках:
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
}
}
}
5) После аргументов мы ожидаем прочитать операторы вложенного конструктора:
Чтобы сохранить эти операторы, мы создаем экземпляр ранее определенного ClassStatement:
private void parseClassDefinition() {
...
ClassStatement classStatement = new ClassStatement();
}
6) Помимо аргументов и вложенных операторов, наши классы также могут содержать функции. Чтобы сделать эти функции доступными только внутри определения класса, мы инициализируем новый уровень DefinitionScope:
private void parseClassDefinition() {
...
ClassStatement classStatement = new ClassStatement();
DefinitionScope classScope = DefinitionContext.newScope();
}
7) Затем мы инициализируем экземпляр 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);
}
8) Наконец, чтобы прочитать операторы и функции конструктора класса, мы вызываем статический StatementParser#parse(), который будет собирать операторы внутри экземпляра classStatement до тех пор, пока мы не встретим завершающую лексему end, которая должна быть пропущено в конце:
private void parseClassDefinition() {
...
//parse class statements
StatementParser.parse(this, classStatement, classScope);
tokens.next(TokenType.Keyword, "end");
}
2.4 Экземпляр класса
На данный момент мы уже можем читать определения классов с операторами конструктора и функциями. Теперь давайте разберем экземпляр класса:
1) Сначала мы определяем ClassValue, который будет содержать состояние каждого экземпляра класса. Классы, в отличие от функций, должны иметь постоянную область MemoryScope, и эта область должна быть доступна со всеми аргументами экземпляра класса и переменными состояния каждый раз, когда мы взаимодействуем с экземпляром класса:
public class ClassValue extends IterableValue<ClassDefinition> {
private final MemoryScope memoryScope;
public ClassValue(ClassDefinition definition, MemoryScope memoryScope) {
super(definition);
this.memoryScope = memoryScope;
}
}
2) Затем мы предоставляем методы для работы со свойствами экземпляра класса, используя 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);
}
}
3) Обратите внимание, что при вызове методов MemoryScope#getLocal() и MemoryScope#setLocal() мы работаем с текущим уровнем MemoryScope. переменные. Но прежде чем получить доступ к состоянию экземпляра класса, нам нужно поместить его MemoryScope в MemoryContext и освободить его, когда мы закончим:
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();
}
}
}
4) Затем мы можем реализовать оставшееся ClassExpression, которое будет использоваться для создания определенных экземпляров класса во время синтаксического анализа. Чтобы объявить определение экземпляра класса, мы предоставляем ClassDefinition и список аргументов Expression, которые будут преобразованы в окончательные экземпляры Value во время выполнения инструкции:< /p>
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() {
...
}
}
5) Давайте реализуем метод Expression#evaluate(), который будет использоваться во время выполнения для создания экземпляра ранее определенного ClassValue. Сначала мы преобразуем аргументы Expression в аргументы Value:
@Override
public Value<?> evaluate() {
//initialize class arguments
List<Value<?>> values = arguments.stream()
.map(Expression::evaluate)
.collect(Collectors.toList());
}
6) Затем мы создаем пустую область памяти, которая должна быть изолирована от других переменных и может содержать только переменные состояния экземпляра класса:
@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();
}
}
7) Затем мы создаем экземпляр 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();
}
Обратите внимание, что мы преобразовали аргументы Expression в аргументы Value перед настройкой пустого MemoryScope. В противном случае мы не сможем получить доступ к аргументам экземпляра класса, например:
8) И, наконец, мы можем выполнить 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<Expression> arguments;
@Override
public Value<?> evaluate() {
//get class's definition and statement
ClassDefinition definition = DefinitionContext.getScope().getClass(name);
...
}
}
Вы можете выполнить такое же делегирование для FunctionExpression для вызова функций перед определением.
10) Наконец, мы можем закончить чтение экземпляров класса с помощью ExpressionReader. Нет никакой разницы между ранее определенные экземпляры структуры. Нам просто нужно прочитать аргументы Expression и построить 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 Функция класса
В этот момент мы можем создать класс и выполнить операторы конструктора класса. Но мы по-прежнему не можем выполнять функции класса. п
1) Давайте перегрузим метод FunctionExpression#evaluate, который примет ClassValue как ссылку на экземпляр класса, из которого мы хотим вызвать функцию:
package org.example.toylanguage.expression;
public class FunctionExpression implements Expression {
...
public Value<?> evaluate(ClassValue classValue) {
}
}
2) Следующим шагом является преобразование аргументов функции Expression в аргументы Value с использованием текущего MemoryScope:
public Value<?> evaluate(ClassValue classValue) {
//initialize function arguments
List<Value<?>> values = argumentExpressions.stream()
.map(Expression::evaluate)
.collect(Collectors.toList());
}
3) Затем нам нужно передать 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);
4) Наконец, для этой реализации мы вызываем значение по умолчанию FunctionExpression#evaluate(List<Value<?>> values) и передать оцененные аргументы Value:
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();
}
}
5) Чтобы вызвать функцию класса, мы будем использовать оператор :: с двойным двоеточием. В настоящее время этот оператор управляется 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
Оригинал