Створіть власну мову програмування та її компілятор

Компілятор

Компілятор — це програма, яка перетворює вихідний код, написаний мовою програмування високого рівня, у виконуваний машинний код (або іншу мову, у нашому прикладі — Java), який можна запустити на комп’ютері.

Типовий компілятор складається з декількох компонентів або фаз, які працюють разом для перетворення вихідного коду програми у виконуваний код. Ось основні компоненти компілятора:

1. Лексичний аналізатор: Лексичний аналізатор, також відомий як сканер, читає вихідний код і розбиває його на потік токенів. Токени — це найменші значущі одиниці мови програмування, такі як ключові слова, ідентифікатори, оператори і константи.
2. Аналізатор синтаксису: Синтаксичний аналізатор, також відомий як парсер, приймає потік токенів, згенерованих лексичним аналізатором, і будує дерево розбору або абстрактне дерево синтаксису (АДС). Дерево розбору представляє структуру програми відповідно до правил граматики мови програмування.
3. Семантичний аналізатор: Семантичний аналізатор перевіряє дерево розбору на наявність семантичних помилок і невідповідностей. Він перевіряє відповідність типів виразів і змінних, а також те, що всі змінні оголошені до їх використання. Він також виконує виведення типів, де компілятор робить висновок про тип змінної на основі її використання.
4. Генератор коду: Просто приймає АСТ як модель програми, а потім генерує цільовий код.
5. Таблиця символів: Таблиця символів — це структура даних, яка використовується компілятором для зберігання інформації про змінні, функції та інші елементи програми.
6. Обробник помилок: Обробник помилок відповідає за виявлення та повідомлення про помилки у вихідному коді.

Приклад

Ми створимо мову з назвою L і скомпілюємо її до Java-мішені.

Компоненти

Файл граматики

Ми будемо використовувати ANTLR.

ANTLR (ANother Tool for Language Recognition) — це потужний генератор, який можна використовувати для створення синтаксичних аналізаторів, лексем і компіляторів для мов програмування, конфігураційних файлів, форматів даних та інших форматів структурованого тексту. Він використовує комбінацію граматик лексем і синтаксичних аналізаторів для аналізу вхідного тексту і створення абстрактних синтаксичних дерев (АСТ), які можуть бути використані компіляторами або інтерпретаторами для виконання програми.

Детальний посібник з налаштування та використання ANTLR тут: Java з ANTLR | Baeldung.

Приклад коду для нашої мови наведено нижче:

def mul[x: Int, y: Int]: Int <- x * y;
var x: Int <- 2;
var y: Int;
y <- x * 2 + x;
mul[x, y+2];

Ми можемо визначити правила для цієї мови у файлі ANTLR g4:

grammar L;

l: statement*
;

statement: function_def
| variable_def
| variable_assign
| function_call
;

function_def : 'def' ID '[' parameters? ']' ':' type assign SC
;

parameters : parameter (',' parameter)*
;

parameter : ID ':' type
;

function_call : ID '[' arguments? ']' SC
;

arguments : argument (',' argument)*
;

argument : expression
;

variable_def : 'var' ID ':' type assign? SC
;

variable_assign : ID assign SC
;

assign: '<-' expression
;

type : 'Int' | 'String' | 'Boolean' | ID
;

expression : value
| ID
| '(' expression ')'
| expression '+' expression
| expression '-' expression
| expression '*' expression
| expression '/' expression
| expression '>' expression
| expression '<' expression
| expression '>=' expression
| expression '<=' expression
| expression '==' expression
| expression '!=' expression
| '!' expression
| expression '&&' expression
| expression '||' expression
;

value : INT
| STRING
| TRUE
| FALSE
;

INT : ('0'..'9')+
;

STRING : '"' (ESC | ~["\\])* '"'
;

fragment ESC : '\\' ["\\/bfnrt]
;

TRUE : 'true'
;

FALSE : 'false'
;

ID : [a-zA-Z][a-zA-Z0-9]*
;

SC : ';'
;

WS : [ \t\r\n]+ -> skip
;

• Правило l: Це початкове правило, якому відповідає нуль або більше операторів.
• Правило statement: Відповідає одному з чотирьох типів операторів: визначенням функцій, визначенням змінних, присвоюванням змінних або викликам функцій.
• Правило function_def: Відповідає визначенню функції, яке складається з імені, необов’язкових параметрів, типу повернення і тіла. Тіло — це вираз, який присвоюється імені функції.
• Правило parameters: Відповідає списку параметрів функції, розділених комами.
• Правило parameter: Відповідає одному параметру, який складається з імені, двокрапки та типу.
• Правило function_call: Відповідає виклику функції, який складається з імені функції та нуля або більше аргументів.
• Правило arguments: Відповідає списку аргументів для виклику функції, розділених комами.
• Правило argument: Відповідає єдиному аргументу, який є просто виразом.
• Правило variable_def: Відповідає визначенню змінної, яке складається з імені, двокрапки, типу та необов’язкового присвоєння.
• Правило variable_assign: Відповідає присвоюванню змінної, яке складається з імені змінної та виразу, який їй присвоюється.
• Правило assign: Відповідає оператору присвоєння та виразу.
• Правило type: Відповідає типу, яким може бути Int, String, Boolean або будь-який інший ідентифікатор.
• Правило expression: Відповідає базовому виразу, яким може бути значення, змінна, вираз у круглих дужках або комбінація виразів з використанням арифметичних, логічних операторів або операторів порівняння.
• Правило value: Відповідає буквальному значенню, яке може бути цілим числом, рядком, істиною або хибністю.

Токени:

• Правило INT: Збігається з цілочисельним літералом.
• Правило STRING: Відповідає рядковому літералу, який може містити екрановані послідовності.
• Правило ESC: Відповідає екранованим послідовностям всередині рядкового літерала.
• Правила TRUE і FALSE: Відповідають булевим літералам true і false.
• Правило ID: Відповідає ідентифікатору, який використовується для імен змінних, функцій та типів.
• Правило SC: Відповідає крапці з комою, яка використовується для завершення операторів.
• Правило WS: Збігається з пробілами і пропускає їх.

AST

Наш AST має інтерфейс:

public interface Statement {
public String getType();
}

І реалізує його наступне

public class VariableAssign implements Statement {
private Identifier identifier;
private Assign assign;

@Override
public String getType() {
return "variable_assign";
}
}

public class VariableDef implements Statement {
private Identifier identifier;
private Boolean initialized;
private Assign assign;

@Override
public String getType() {
return "variable_def";
}
}

public class FunctionCall implements Statement {
String name;
List<Argument> arguments;

@Override
public String getType() {
return "function_call";
}
}

public class FunctionDef implements Statement {
String name;
List<Parameter> parameters;
Assign assign;

@Override
public String getType() {
return "function_def";
}
}

Це класи Java, які реалізують інтерфейс Statement і представляють різні типи операторів, які можна розбирати з мови L.

VariableAssign — це оператор, який присвоює значення змінній. Він містить об’єкт Identifier для змінної, що присвоюється, і об’єкт Assign для виразу присвоєння.

VariableDef — це оператор, який визначає змінну. Містить об’єкт Identifier для змінної, що визначається, логічний прапорець, який вказує, чи змінна ініціалізована, та об’єкт Assign для виразу присвоєння (якщо змінна ініціалізована).

FunctionCall представляє інструкцію, яка викликає функцію. Він містить ім’я функції та список об’єктів Argument для аргументів функції.

FunctionDef — це оператор, який визначає функцію. Він містить ім’я функції, список об’єктів Parameter для параметрів функції та об’єкт Assign для тіла функції.

Повний код AST — за посиланням.

Лексичний та синтаксичний аналізатор

Цей код є реалізацією відвідувача ANTLR4 для мови програмування. Відвідувач аналізує вхідний код і будує список операторів, які потім можуть бути використані для подальшого аналізу або виконання.

public class LVisitor extends LBaseVisitor {

public List<Statement> statements = new LinkedList<>();
ScopeService scope = new ScopeService();

@Override
public Object visitStatement(LParser.StatementContext ctx) {
Object result = super.visitStatement(ctx);
statements.add((Statement) result);
return result;
}

@Override
public Statement visitVariable_def(LParser.Variable_defContext ctx) {
VariableDef.VariableDefBuilder builder = VariableDef.builder();

// Add the identifier
Identifier identifier = new Identifier(ctx.ID().getText(), new Type(ctx.type().getText()));
scope.addIdentifier(identifier);
builder.identifier(identifier);

// Add the assign if exists
if (ctx.assign() != null) {
Assign assign = buildAssign(ctx.assign(), identifier.getType());
builder.initialized(true);
builder.assign(assign);
}

return builder.build();
}

@Override
public Statement visitVariable_assign(LParser.Variable_assignContext ctx) {
Identifier identifier = scope.getIdentifier(ctx.ID().getText());
Assign assign = buildAssign(ctx.assign(), identifier.getType());
return new VariableAssign(identifier, assign);
}

@Override
public Statement visitFunction_def(LParser.Function_defContext ctx) {
String name = ctx.ID().getText();
List<Parameter> parameters = new LinkedList<>();
scope.openScope();
for (int i = 0; i < ctx.parameters().parameter().size(); i++) {
LParser.ParameterContext pc = ctx.parameters().parameter().get(i);
Identifier identifier = new Identifier(pc.ID().getText(), new Type(pc.type().getText()));
scope.addIdentifier(identifier);
parameters.add(new Parameter(identifier, i));
}
Assign assign = buildAssign(ctx.assign(), new Type(ctx.type().getText()));
scope.closeScope();
FunctionDef def = new FunctionDef(name, parameters, assign);
scope.addFunction(def);
return def;
}

@Override
public Statement visitFunction_call(LParser.Function_callContext ctx) {
String name = ctx.ID().getText();
List<Argument> arguments = new LinkedList<>();
for (int i = 0; i < ctx.arguments().argument().size(); i++) {
LParser.ArgumentContext arg = ctx.arguments().argument().get(i);
Expression expression = buildExpression(arg.expression());
arguments.add(new Argument(i, expression));
}
// Validate function exists and it's arguments
scope.getFunctionDef(name, arguments);
return new FunctionCall(name, arguments);
}

private Assign buildAssign(LParser.AssignContext ctx, Type type) {
return new Assign(type, buildExpression(ctx.expression()));
}

private Expression buildExpression(LParser.ExpressionContext ctx) {

if (ctx.value() != null) {
return getValueExpression(ctx.value());
} else if (ctx.ID() != null) {
return getIDExpression(ctx.ID().getText());
} else if (ctx.getChildCount() == 3) {
Expression left = buildExpression(ctx.expression(0));
Expression right = buildExpression(ctx.expression(1));
String operator = ctx.getChild(1).getText();
return getBinaryExpression(operator, left, right);
} else if (ctx.getChildCount() == 2) {
String operator = ctx.getChild(0).getText();
Expression right = buildExpression(ctx.expression(0));
return getUnaryExpression(operator, right);
} else {
return null;
}
}

private Expression getUnaryExpression(String op, Expression rhs) {
Expression.ExpressionBuilder builder = Expression.builder();
builder
.expressionType(Expression.ExpressionType.UNARY)
.op(op)
.rhs(rhs);
return builder.build();
}

private Expression getBinaryExpression(String op, Expression lhs, Expression rhs) {
Expression.ExpressionBuilder builder = Expression.builder();
builder
.expressionType(Expression.ExpressionType.BINARY)
.op(op)
.lhs(lhs)
.rhs(rhs);
return builder.build();
}

private Expression getIDExpression(String name) {
Expression.ExpressionBuilder builder = Expression.builder();
builder
.expressionType(Expression.ExpressionType.ID)
.ID(scope.getIdentifier(name));
return builder.build();
}

private Expression getValueExpression(LParser.ValueContext context) {
Expression.ExpressionBuilder builder = Expression.builder();
builder.expressionType(Expression.ExpressionType.VALUE)
.value(new Value(getValueExpressionType(context), context.getText()));

return builder.build();
}

private Type getValueExpressionType(LParser.ValueContext context) {
if (context.STRING() != null) return new Type("String");
else if (context.INT() != null) return new Type("Int");
else if (context.TRUE() != null || context.FALSE() != null) return new Type("Bool");
else return new Type("String");
}
}

Відвідувач визначає методи для кожного правила граматики ANTLR4, і кожен метод створює відповідний оператор або об’єкт виразу, який потім додається до списку операторів.

Відвідувач також керує областю видимості (таблицею символів), яка використовується для відстеження змінних і функцій, оголошених у програмі. Область видимості оновлюється при оголошенні нових змінних і функцій, а також використовується для пошуку ідентифікаторів, коли на них посилаються в коді (семантичний аналізатор і обробник помилок).

Таблиця символів

public class Scope {

List<Identifier> identifiers = new LinkedList<>();
List<FunctionDef> functions = new LinkedList<>();
Scope parent = null;

public void addIdentifier(Identifier identifier) {
Optional<Identifier> check = identifiers.stream().filter(i -> i.getName().equals(identifier.getName())).findFirst();
if (check.isPresent()) {
throw new IdentifierAlreadyInScope(identifier.getName());
}
identifiers.add(identifier);
}

public void addFunction(FunctionDef functionDef) {
Optional<FunctionDef> check = functions.stream().filter(i -> i.getName().equals(functionDef.getName())).findFirst();
if (check.isPresent()) {
throw new IdentifierAlreadyInScope(functionDef.getName());
}
functions.add(functionDef);
}

public Identifier getIdentifier(String id) throws IdentifierNotFoundInScope {
Optional<Identifier> identifier = identifiers.stream().filter(i -> i.getName().equals(id)).findFirst();
if (identifier.isPresent()) {
return identifier.get();
}
if (parent != null) {
return parent.getIdentifier(id);
}
throw new IdentifierNotFoundInScope(id);
}

public FunctionDef getFunction(String id, List<Argument> arguments) throws IdentifierNotFoundInScope {
Optional<FunctionDef> function = functions.stream().filter(i -> i.getName().equals(id)).findFirst();
if (function.isPresent()) {
List<Parameter> parameters = function.get().getParameters();
if (!(arguments.size() == parameters.size())) {
// Validate argument count matching parameter count.
throw new ArgumentsNotCompliantWithParametersList(id);
}
for (int i = 0; i < parameters.size(); i++) {
// Validate argument types matching parameter types.
if (!arguments.get(i).getExpression().resultType().equals(parameters.get(i).getIdentifier().getType())) {
throw new ArgumentsNotCompliantWithParametersList(id);
}
}
return function.get();
}
if (parent != null) {
return parent.getFunction(id, arguments);
}
throw new IdentifierNotFoundInScope(id);
}

public void clear() {
identifiers.clear();
}
}

Це клас Java під назвою Scope, який використовується для відстеження змінних і функцій у певній області видимості програми.

Клас має три поля:

• ідентифікатори: Список об’єктів ідентифікаторів, що представляють змінні у поточній області видимості.
• функції: Список об’єктів FunctionDef, що представляють функції у поточній області видимості.
• батьківський: Посилання на батьківський об’єкт області видимості. Використовується для пошуку змінних і функцій у зовнішніх областях видимості.

Клас має декілька методів:

• addIdentifier(): Додає об’єкт Identifier до списку ідентифікаторів, але спочатку перевіряє на наявність дублікатів.
• addFunction(): Додає об’єкт FunctionDef до списку функцій, але спочатку перевіряє на наявність дублікатів.
• getIdentifier(): Повертає об’єкт Identifier за його іменем. Якщо ідентифікатор не знайдено у поточній області видимості, він шукається у батьківській області видимості (якщо вона існує). Якщо ідентифікатор все ще не знайдено, генерується виключення IdentifierNotFoundInScope.
• getFunction(): Повертає об’єкт FunctionDef за його іменем та списком аргументів. Перевіряє, чи кількість аргументів відповідає кількості параметрів, і чи типи аргументів відповідають типам параметрів. Якщо функцію не знайдено у поточній області видимості, вона шукається у батьківській області видимості (якщо вона існує). Якщо функцію все одно не знайдено, згенерується виключення IdentifierNotFoundInScope.
• clear(): Очищає список ідентифікаторів. Це використовується для скидання області видимості між викликами функції.

public class ScopeService {

Scope currentScope = new Scope();

public void openScope() {
Scope newScope = new Scope();
newScope.setParent(currentScope);
currentScope = newScope;
}

public void closeScope() {
currentScope.clear();
currentScope = currentScope.getParent();
}

public void addIdentifier(Identifier identifier) throws IdentifierAlreadyInScope {
currentScope.addIdentifier(identifier);
}

public Identifier getIdentifier(String id) throws IdentifierNotFoundInScope {
return currentScope.getIdentifier(id);
}

public void addFunction(FunctionDef def) throws IdentifierAlreadyInScope {
currentScope.addFunction(def);
}

public FunctionDef getFunctionDef(String id, List<Argument> arguments) throws IdentifierNotFoundInScope {
return currentScope.getFunction(id, arguments);
}

}

ScopeService, який надає методи для керування діапазонами та ідентифікаторами всередині них. Клас має змінну екземпляра з назвою currentScope, яка спочатку встановлюється на новий об’єкт Scope.

Метод openScope створює новий об’єкт Scope, встановлює його батька у поточну область видимості і робить нову область видимості поточною.

Метод closeScope очищає поточну область видимості і встановлює поточну область видимості на її батька.

Метод addIdentifier додає об’єкт Identifier до поточної області видимості за допомогою методу addIdentifier поточної області видимості.

Метод getIdentifier отримує об’єкт Identifier за іменем з поточної області видимості за допомогою методу getIdentifier поточної області видимості.

Метод addFunction додає об’єкт FunctionDef до поточної області видимості з допомогою методу addFunction поточної області видимості.

Метод getFunctionDef отримує об’єкт FunctionDef за іменем та аргументами з поточної області видимості методом getFunction поточної області видимості.

Шаблон коду Java та генерація коду

FreeMarker — це движок шаблонів на основі Java, який використовується для створення динамічного контенту, такого як веб-сторінки HTML, електронні листи та документи. Він дозволяє розробникам відокремити рівень презентації від рівня бізнес-логіки за допомогою шаблонів. Шаблони FreeMarker — це, по суті, текстові файли із заповнювачами, які під час обробки шаблону замінюються динамічним контентом.

Детальніше — за посиланням.

Файл цільового шаблону Java:

package samsaydali.l.codegen;

public class Main {

public static void main(String[] args) {
<#list statements as statement>
<#if statement.getType() == "variable_def">
${statement.identifier.type.type} ${statement.identifier.name}<#if statement.initialized??> = ${statement.assign.expression.getText()}</#if>;
</#if>
<#if statement.getType() == "variable_assign">
${statement.identifier.name} = ${statement.assign.expression.getText()};
</#if>
<#if statement.getType() == "function_call">
${statement.name}(${statement.arguments?map(a -> a.expression.getText())?join(', ')?no_esc});
</#if>
</#list>

}

<#list statements?filter(s -> s.getType() == 'function_def') as function>
private static int ${function.name}(${function.parameters?map(p -> p.identifier.type.type + " " + p.identifier.name)?join(', ')?no_esc}) {
return ${function.assign.expression.getText()};
}
</#list>
}

Шаблон FreeMarker використовується для генерації коду на основі списку операторів. Він містить кілька умовних блоків, які перевіряють тип кожного оператора і генерують відповідний код на основі цього типу.

Наприклад, якщо оператор є визначенням змінної, шаблон генерує рядок коду, який оголошує змінну з вказаним типом та іменем, опціонально ініціалізовану значенням виразу, що стоїть праворуч від знаку рівності. Якщо оператор є викликом функції, шаблон генерує рядок коду, який викликає вказану функцію з заданими аргументами.

Крім того, шаблон містить цикл, який перебирає список операторів і генерує код для кожного визначення функції, знайденого в списку. Кожне визначення функції перетворюється на закритий статичний метод з тим самим іменем, що й функція, з відповідними типами та іменами параметрів, а тіло методу встановлюється у значення виразу, присвоєного функції.

Варто зазначити, що оператори <#if> і <#list> є частиною синтаксису FreeMarker і використовуються тут для умовної генерації коду на основі типу кожного оператора і для циклічного перегляду списку операторів для генерації коду для кожного визначення функції.

Фінальний додаток

public class LCompiler {

public LVisitor visit(String lInput) {
LLexer lexer = new LLexer(CharStreams.fromString(lInput));
CommonTokenStream tokens = new CommonTokenStream(lexer);
LParser parser = new LParser(tokens);

LVisitor visitor = new LVisitor();
parser.l().accept(visitor);

повернути visitor;
}

public List<Statement> getAST(LVisitor visitor) {
повернути visitor.statements;
}

public JavaGenerator getGenerator() {
повернути новий JavaGenerator();
}

public String generateCode(List<Statement> ast) throws TemplateException, IOException {
return getGenerator().generate(ast);
}

public String compileToJava(String lInput) throws TemplateException, IOException {
LVisitor visitor = visit(lInput);
List<Statement> ast = getAST(visitor);
Рядок javaCode = generateCode(ast);
return javaCode;
}

}

Клас LCompiler є основним класом, що відповідає за компіляцію L-коду в код Java.

Метод visit приймає вхідні дані L, ініціалізує лексер і синтаксичний аналізатор за допомогою ANTLR і передає розібраний AST екземпляру LVisitor, який відповідає за відвідування вузлів AST і побудову списку об’єктів Statement.

Метод getAST просто повертає список об’єктів Statement, побудований відвідувачем.

Метод getGenerator створює і повертає новий екземпляр JavaGenerator, який є класом, що відповідає за генерацію Java-коду зі списку об’єктів Statement.

Метод generateCode отримує список об’єктів Statement і генерує Java-код за допомогою класу JavaGenerator.

Нарешті, метод compileToJava отримує вхідні дані L, компілює їх у список об’єктів Statement за допомогою visit, генерує Java-код зі списку об’єктів Statement за допомогою generateCode і повертає результуючий Java-код.

Повний код тут.

Цей текст взято з особистого блогу після отримання дозволу автора.