6,103 lượt đọc

Xây dựng ngôn ngữ lập trình của riêng bạn từ đầu: Phần VII - Các lớp học

từ tác giả Alexander Makeev22m2022/12/15

dài quá đọc không nổi

Trong phần tạo ngôn ngữ lập trình của riêng bạn, chúng tôi sẽ triển khai các lớp và ở phần cuối sẽ viết triển khai Stack thực

featured image - Xây dựng ngôn ngữ lập trình của riêng bạn từ đầu: Phần VII - Các lớp học

Trong phần tạo ngôn ngữ lập trình của riêng bạn này, chúng ta sẽ triển khai các lớp như một phần mở rộng trên các cấu trúc đã xác định trước đó. Mời các bạn xem lại các phần trước:

Mã nguồn đầy đủ có sẵn trên GitHub .

1. Phân tích từ vựng

Trong phần đầu tiên, chúng ta sẽ đề cập đến phân tích từ vựng. Tóm lại, đó là một quá trình phân chia mã nguồn thành các từ vựng ngôn ngữ, chẳng hạn như từ khóa, biến, toán tử, v.v.

Bạn có thể nhớ từ các phần trước rằng tôi đã sử dụng các biểu thức regex trong TokenType enum để xác định tất cả các loại từ vựng.

Hãy xem nguyên mẫu lớp sau đây và thêm các phần biểu thức chính quy còn thiếu vào các từ TokenType của chúng tôi:

Đầu tiên, chúng ta cần đặt từ class trong biểu thức của Keyword lexeme để cho bộ phân tích từ vựng biết nơi khai báo lớp của chúng ta bắt đầu:

 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; }

Thứ hai, chúng ta cần từ vựng This mới làm điểm đánh dấu để tham chiếu đến đối tượng hiện tại:

 public enum TokenType { ... This("(this)(?=,|\\s|$)"); private final String regex; }

2. Phân tích cú pháp

Trong phần thứ hai, chúng tôi sẽ chuyển đổi các từ vựng nhận được từ bộ phân tích từ vựng thành các câu lệnh cuối cùng tuân theo các quy tắc ngôn ngữ của chúng tôi.

2.1 Phạm vi định nghĩa

Khi chúng ta khai báo một lớp hoặc một hàm, khai báo này sẽ có sẵn trong các giới hạn riêng biệt đã xác định. Ví dụ: nếu chúng ta khai báo một hàm có tên là turn_on [] trong danh sách sau, thì hàm này sẽ có sẵn để thực thi sau khi khai báo:

Nhưng nếu chúng ta khai báo cùng một chức năng bên trong phạm vi lớp, chức năng này sẽ không còn được truy cập trực tiếp từ khối chính:

Để triển khai các giới hạn định nghĩa này, chúng ta sẽ tạo lớp DefinitionScope và lưu trữ tất cả các định nghĩa đã khai báo bên trong hai tập hợp cho các lớp và hàm:

 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<>(); } }

Ngoài ra, chúng tôi có thể muốn truy cập phạm vi định nghĩa của cha mẹ. Ví dụ: nếu chúng ta khai báo hai lớp riêng biệt và tạo một thể hiện của lớp đầu tiên bên trong lớp thứ hai:

Để cung cấp khả năng này, chúng tôi sẽ thêm thể hiện chính của DefinitionScope làm tham chiếu đến lớp trên, mà chúng tôi sẽ sử dụng để leo lên lớp định nghĩa trên cùng.

 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; } }

Bây giờ, hãy kết thúc quá trình triển khai bằng cách cung cấp các giao diện để thêm định nghĩa và truy xuất nó theo tên bằng phạm vi cha:

 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); } }

Cuối cùng, để quản lý phạm vi định nghĩa đã khai báo và chuyển đổi giữa chúng, chúng ta tạo lớp ngữ cảnh bằng cách sử dụng bộ sưu tập 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 Phạm vi bộ nhớ

Trong phần này, chúng ta sẽ đề cập đến MemoryScope để quản lý các biến của lớp và hàm.

Mỗi biến được khai báo, tương tự như định nghĩa lớp hoặc hàm, chỉ có thể truy cập được trong một khối mã riêng biệt. Ví dụ, nếu chúng ta định nghĩa một biến trong danh sách sau, bạn có thể truy cập nó ngay sau khi khai báo:

Nhưng nếu chúng ta khai báo một biến trong một hàm hoặc một lớp, thì biến đó sẽ không còn khả dụng trong khối mã chính (phía trên):

Để triển khai logic này và lưu trữ các biến được xác định trong một phạm vi cụ thể, chúng ta tạo lớp MemoryScope sẽ chứa một bản đồ với tên biến là khóa và biến Value là giá trị:

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

Tiếp theo, tương tự như DefinitionScope , chúng tôi cung cấp quyền truy cập vào các biến phạm vi của cha mẹ:

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

Tiếp theo, chúng tôi thêm các phương thức để nhận và đặt biến. Khi chúng tôi đặt một biến, chúng tôi luôn gán lại giá trị đã đặt trước đó nếu đã có một biến được xác định trong lớp MemoryScope phía trên:

 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); } }

Ngoài các phương thức set và get , chúng tôi còn thêm hai cách triển khai nữa để tương tác với lớp (cục bộ) hiện tại của MemoryScope :

 public class MemoryScope { ... public Value<?> getLocal(String name) { return variables.get(name); } public void setLocal(String name, Value<?> value) { variables.put(name, value); } }

Các phương thức này sẽ được sử dụng sau này để khởi tạo các đối số hàm hoặc đối số thể hiện của lớp. Ví dụ: nếu chúng ta tạo một thể hiện của lớp Lamp và chuyển biến type toàn cục được xác định trước, thì biến này sẽ không bị thay đổi khi chúng ta cố cập nhật thuộc tính lamp_instance :: type :

Cuối cùng, để quản lý các biến và chuyển đổi giữa các phạm vi bộ nhớ, chúng tôi tạo triển khai MemoryContext bằng bộ sưu tập 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 Định nghĩa lớp

Trong phần này, chúng ta sẽ đọc và lưu trữ các định nghĩa lớp.

Đầu tiên, chúng tôi tạo triển khai Tuyên bố . Câu lệnh này sẽ được thực thi mỗi khi chúng ta tạo một thể hiện của lớp:

 package org.example.toylanguage.statement; public class ClassStatement { }

Mỗi lớp có thể chứa các câu lệnh lồng nhau để khởi tạo và các hoạt động khác, giống như hàm tạo. Để lưu trữ các câu lệnh này, chúng tôi mở rộng CompositeStatement chứa danh sách các câu lệnh lồng nhau để thực thi:

 public class ClassStatement extends CompositeStatement { }

Tiếp theo, chúng ta khai báo ClassDefinition để lưu trữ tên lớp, các đối số của nó, các câu lệnh khởi tạo và phạm vi định nghĩa với các hàm của lớp:

 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; }

Bây giờ, chúng ta đã sẵn sàng để đọc khai báo lớp bằng StatementParser . Khi chúng ta gặp Từ khóa từ vựng với giá trị class , đầu tiên chúng ta cần đọc tên lớp và các đối số của nó bên trong dấu ngoặc vuông:

 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 } } }

Sau các đối số, chúng tôi mong muốn đọc các câu lệnh hàm tạo lồng nhau:

Để lưu trữ các câu lệnh này, chúng tôi tạo một thể hiện của ClassStatement đã xác định trước đó:

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

Ngoài các đối số và các câu lệnh lồng nhau, các lớp của chúng ta cũng có thể chứa các hàm. Để làm cho các chức năng này chỉ có thể truy cập được trong định nghĩa lớp, chúng tôi khởi tạo một lớp mới của DefinitionScope :

 private void parseClassDefinition() { ... ClassStatement classStatement = new ClassStatement(); DefinitionScope classScope = DefinitionContext.newScope(); }

Tiếp theo, chúng tôi khởi tạo một thể hiện của ClassDefinition và đặt nó vào 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); }

Cuối cùng, để đọc các câu lệnh và hàm của hàm tạo lớp, chúng ta gọi phương thức StatementParser#parse() tĩnh sẽ thu thập các câu lệnh bên trong cá thể classStatement cho đến khi chúng ta gặp từ vựng end phải được bỏ qua ở cuối:

 private void parseClassDefinition() { ... //parse class statements StatementParser.parse(this, classStatement, classScope); tokens.next(TokenType.Keyword, "end"); }

2.4 Phiên bản lớp

Tại thời điểm này, chúng ta đã có thể đọc các định nghĩa lớp với các câu lệnh và hàm khởi tạo. Bây giờ, hãy phân tích ví dụ của lớp:

Đầu tiên, chúng tôi định nghĩa ClassValue , sẽ chứa trạng thái của từng thể hiện của lớp. Các lớp, không giống như các hàm, nên có một MemoryScope cố định và phạm vi này sẽ có sẵn với tất cả các đối số thể hiện và các biến trạng thái của lớp mỗi khi chúng ta tương tác với thể hiện của lớp:

 public class ClassValue extends IterableValue<ClassDefinition> { private final MemoryScope memoryScope; public ClassValue(ClassDefinition definition, MemoryScope memoryScope) { super(definition); this.memoryScope = memoryScope; } }

Tiếp theo, chúng tôi cung cấp các phương thức để làm việc với các thuộc tính thể hiện của lớp bằng cách sử dụng 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); } }

Xin lưu ý rằng bằng cách gọi các phương MemoryScope#getLocal() và MemoryScope#setLocal() , chúng ta sẽ làm việc với lớp biến MemoryScope hiện tại. Nhưng trước khi truy cập trạng thái thể hiện của lớp, chúng ta cần đặt MemoryScope của nó vào MemoryContext và giải phóng nó khi chúng ta hoàn thành:

 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(); } } }

Tiếp theo, chúng ta có thể triển khai ClassExpression còn lại sẽ được sử dụng để xây dựng các thể hiện của lớp đã xác định trong quá trình phân tích cú pháp. Để khai báo định nghĩa thể hiện của lớp, chúng tôi cung cấp Định nghĩa ClassDefinition và danh sách các đối số Expression sẽ được chuyển đổi thành các thể hiện Value cuối cùng trong quá trình thực thi câu lệnh:

 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() { ... } }

Hãy triển khai phương Expression#evaluate() sẽ được sử dụng trong quá trình thực thi để tạo một thể hiện của ClassValue đã xác định trước đó. Đầu tiên, chúng tôi đánh giá các đối số Expression thành các đối số Value :

 @Override public Value<?> evaluate() { //initialize class arguments List<Value<?>> values = arguments.stream() .map(Expression::evaluate) .collect(Collectors.toList()); }

Tiếp theo, chúng tôi tạo một phạm vi bộ nhớ trống sẽ được tách biệt khỏi các biến khác và chỉ có thể chứa các biến trạng thái thể hiện của lớp:

 @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(); } }

Tiếp theo, chúng tôi tạo một thể hiện của ClassValue và ghi các đối số Value của lớp vào phạm vi bộ nhớ bị cô lập:

 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(); }

Xin lưu ý rằng chúng tôi đã chuyển đổi các đối số Expression thành các đối số Value trước khi thiết lập một MemoryScope trống. Nếu không, chúng ta sẽ không thể truy cập các đối số thể hiện của lớp, ví dụ:

Và cuối cùng, chúng ta có thể thực thi ClassStatement . Nhưng trước đó, chúng ta nên thiết lập DefinitionScope của lớp để có thể truy cập các chức năng của lớp trong các câu lệnh khởi tạo:

 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*. Một điều cuối cùng, chúng ta có thể làm cho các lớp linh hoạt hơn và cho phép người dùng tạo các thể hiện của lớp trước khi khai báo định nghĩa lớp:

Điều này có thể được thực hiện bằng cách ủy quyền khởi tạo ClassDefinition cho DefinitionContext và chỉ truy cập nó khi chúng ta đánh giá một biểu thức:

 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); ... } }

Bạn có thể thực hiện ủy quyền tương tự cho FunctionExpression để gọi các hàm trước khi định nghĩa.

Cuối cùng, chúng ta có thể hoàn thành việc đọc các thể hiện của lớp với ExpressionReader . Không có sự khác biệt giữa các trường hợp cấu trúc được xác định trước đó . Chúng ta chỉ cần đọc các đối số của Expression và xây dựng 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 Chức năng lớp

Tại thời điểm này, chúng ta có thể tạo một lớp và thực thi các câu lệnh khởi tạo của lớp. Nhưng chúng tôi vẫn không thể thực hiện các chức năng của lớp.

Hãy quá tải phương thức FunctionExpression#evaluate sẽ chấp nhận ClassValue làm tham chiếu đến thể hiện của lớp mà chúng ta muốn gọi một hàm từ:

 package org.example.toylanguage.expression; public class FunctionExpression implements Expression { ... public Value<?> evaluate(ClassValue classValue) { } }

Bước tiếp theo là chuyển đổi các đối số Expression hàm thành các đối số Value bằng cách sử dụng MemoryScope hiện tại:

 public Value<?> evaluate(ClassValue classValue) { //initialize function arguments List<Value<?>> values = argumentExpressions.stream() .map(Expression::evaluate) .collect(Collectors.toList()); }

Tiếp theo, chúng ta cần chuyển MemoryScope và DefinitionScope của lớp vào ngữ cảnh:

 ... //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);

Cuối cùng để thực hiện điều này, chúng tôi gọi phương thức FunctionExpression#evaluate(List<Value<?>> values) mặc định và chuyển các đối số Value được đánh giá:

 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(); } }

Để gọi hàm của lớp, chúng ta sẽ sử dụng toán tử dấu hai chấm :: . Hiện tại, toán tử này được quản lý bởi triển ClassPropertyOperator ( StructureValueOperator ), chịu trách nhiệm truy cập các thuộc tính của lớp:

Hãy cải thiện nó để hỗ trợ các lời gọi hàm với cùng một dấu hai chấm :: ký tự:

Hàm của lớp chỉ có thể được quản lý bởi toán tử này khi biểu thức bên trái là ClassExpression và biểu thức thứ hai là 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. Kết thúc

Trong phần này, chúng tôi đã triển khai các lớp. Bây giờ chúng ta có thể tạo ra những thứ phức tạp hơn, chẳng hạn như triển khai ngăn xếp:

 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