Некоторое время назад настроение политиков ведущих стран мира вызывало опасения в отношении будущего IT сектора. Санкции Microsoft, Apple, ARM, Ubuntu и многих других не то чтобы повлияли на рынок компьютеров, а полностью предопределили будущее направление развития отечественной кибер инфраструктуры. Об этом говорит политика импортозамещения, проводимая в России.

Поэтому, считаю, не стоит объяснять необходимость нового языка программирования. Если аргументов, представленных выше не достаточно, то в качестве дополнения можно указать избыточность (конструкции типа exactly-once в Python или присваивание как выражение всего, что только вздумается в Kotlin) существующих языков программирования. А также, устаревшую концепцию интерфейса в C++, устаревший стандарт snake_case стандартной библиотеки C++ и т.д.

Предварительные требования

Задачей является компиляция исходного кода, написанного на языке Ace в исполняемый файл (программу консольного типа). Компилятор должен считывать по одной строке кода и выполнять вычисления, определенные в этой строке. В качестве выходных данных исполняемый файл выводит результаты вычислений в консоль.

Требуемые возможности:

• Объявление констант

• Объявление переменных

• Поддержка целочисленного типа данных

• Поддержка типа данных с плавающей точкой

• Отказоустойчивость (в случае ошибки, допущенной программистом, программа выводит сообщение об ошибке, а не завершает аварийно работу)

Архитектура

Ядро компилятора состоит из следующих компонентов:

• Source Code Manager - открывает файл с исходным кодом, расположенным на жестком диске и загружает его в оперативную память

• Text Reader - читает исходный код и хранит информацию о положении курсора

• Token Parser - преобразует строку исходного кода в лексические токены

• Syntactic Analyzer - создает абстрактное синтаксическое дерево из лексических токенов, при этом проверяя грамматику языка программирования

• Executor - проходит по абстрактному синтаксическому дереву, собирая семантическую информацию и выполняет инструкции исходного кода

• Scope - хранит список объявленных переменных

• Compiler - координирует работу всех модулей, указанных выше

Source Code Manager

Поскольку речь идет о компиляции файлов, то требуется модуль, который взаимодействует с операционной системой, а в частности с файловой системой. Его назначение - это открыть и прочитать (загрузить в оперативную память) файл с исходным кодом.

В то же время не стоит забывать, что существует понятие RAII (Resource Acquisition Is Initialization) в языке C++. Поэтому следует предусмотреть возможность освобождения оперативной памяти при необходимости. В итоге модуль имеет следующий интерфейс:

class SourceCodeManager {
  var sourceCode: String { get }
  var fileName: String { get }
  var fileExtension: String { get }
  
  func open(file path: String) throws
  func close()
}

Text Reader

Данный модуль получает в качестве входного параметра строку и читает её посимвольно с мониторингом текущей позиции. Таким образом появляется возможность узнать на какой строке и на каком символе находился компилятор в случае возникновения ошибки компиляции.

Помимо того, часто требуется операция отмены чтения на один шаг назад. Такая потребность возникает, если при распознании встретился ненужный символ, который нельзя пропустить. Модуль имеет такой интерфейс:

class TextReader {
  struct Position {
    var line: Int { get }
    var column: Int { get }
  }

  enum Unit {
    case beginOfFile
    case character(Character)
    case endOfFile
  }
  
  var position: Position { get }
  var unit: Unit { get }

  func load(string: String)
  func read() -> Unit
  func unread(_ unit: Unit)
}

Token Parser

Этот компонент выполняет распознание лексических токенов из строки исходного кода. Причем распознание может завершиться ошибкой, если программист допустил, например, опечатку. Обычно такой компонент используется для первоначальной обработки исходного кода с целью упрощения последующих этапов распознания.

Как было сказано, существует концепция лексических токенов. Набор всех возможных вариантов представлен ниже:

enum Token {
  case keyword(Keyword)
  case punctuator(Punctuator)
  case literal(Literal)
  case identifier(String)
}

Интерфейс компонента максимально прост. На входе строка исходного кода, на выходе - массив лексических токенов.

class TokenParser {
  func parse(string: String) throws -> [Token]
}

Syntactic Analyzer

Самый объемный и, пожалуй, наиболее важный модуль из всех. Он выполняет конструирование абстрактного синтаксического дерева на основе грамматики языка программирования. Очевидно, что построение дерева может завершиться ошибкой, поскольку программист может написать неправильные синтаксические конструкции. Например, некорректное объявление переменной.

Еще одна сложность реализации заключается в том, что дерево имеет более двух так называемых листьев. (Подробнее см. алгоритмы и структуры данных.) Это добавляет трудностей, в первую очередь, при отладке и выводе дерева на экран.

Базовой единицей дерева является узел. Узел может иметь неограниченное количество таких же узлов, либо быть нетерминалом. (Подробнее см. грамматика языков программирования.) Интерфейс сущности следующий:

class SyntacticNode: Node {
  var id: UUID { get }
  var children: [SyntacticNode] { get }
  var kind: Kind { get }
  var value: String? { get set }

  init(kind: Kind, value: String?)
  init(kind: Kind, value: Character)

  func joined() -> String
}

Не будет лишним указать, что для работы с лексическими токенами используется концепция потока (Stream), которая позволят считать очередной токен, вернуть его обратно в поток, либо выполнить предпросмотр следующего токена.

Сам модуль настолько объемный, что его просто необходимо разделить на несколько компонентов, реализующих специфичную для распознания функцию. Таким образом, модуль состоит из:

class SyntacticAnalyzer {
  func parse(tokens: [Token]) throws -> SyntacticNode
}

class StatementsParser {
  func parseStatement(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание выражения.

class DeclarationsParser {
  func parseDeclaration(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание объявления либо константы, либо переменной.

class IdentifiersParser {
  func parseIdentifierList(stream: Stream<[Token]>) throws -> SyntacticNode
  func parseIdentifier(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание идентификатора или списка идентификаторов, перечисленных через запятую.

class TypesParser {
  func parseType(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание типа, указанного в аннотации к переменной через символ ":".

class ExpressionsParser {
  func parseExpression(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание выражения с учетом приоритетов операторов сложения (вычитания) и умножения (деления), а также скобок.

class LiteralsParser {
  func parseLiteral(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание литералов. Как целочисленных, так и с плавающей точкой.

class IntegerLiteralsParser {
  func parseIntegerLiteral(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание целочисленных литералов.

class FloatingPointLiteralsParser {
  func parseFloatLiteral(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание литералов с плавающей точкой.

class OperatorsParser {
  func parseBinaryOperator(stream: Stream<[Token]>) throws -> SyntacticNode
  func parseUnaryOperator(stream: Stream<[Token]>) throws -> SyntacticNode
  func parseAssignOperator(stream: Stream<[Token]>) throws -> SyntacticNode
}

Выполняет распознание операторов. Унарных, бинарных и присваивания.

class CharactersParser {
  func parseLetter(character: Character) throws -> SyntacticNode
  func parseDecimalDigit(character: Character) throws -> SyntacticNode
  func parseBinaryDigit(character: Character) throws -> SyntacticNode
  func parseOctalDigit(character: Character) throws -> SyntacticNode
  func parseHexadecimalDigit(character: Character) throws -> SyntacticNode
  func parseUnicodeLetter(character: Character) throws -> SyntacticNode
  func parseUnicodeDigit(character: Character) throws -> SyntacticNode
}

Выполняет распознание символов как базовых единиц языка программирования.

Executor

Построив абстрактное синтаксическое дерево необходимо его обработать. Под обработкой имеется в виду его выполнение (выполнение инструкций исходного кода). Для этой цели служит данный модуль.

Учитывая, что дерево содержит большое количество ветвей, которые нужно проанализировать, требуется вспомогательный объект, собирающий семантическую информацию при проходе по дереву. Этот объект получил название SemanticCollector:

class SemanticCollector {
  enum Operation {
    case declaration
    case assignment
  }

  var operation: Operation? { get set}
  var id: Symbol.Id? { get set}
  var type: BaseType? { get set}
  var value: Symbol.Value? { get set}
  var mutability: Symbol.Mutability? { get set}
}

Нетрудно заметить, что также была введена концепция Symbol. Она описывает переменную, которую объявляет и которыми оперирует программист в исходном коде.

class Symbol {
  typealias Id = String
  typealias Value = Any

  enum Mutability {
    case constant
    case variable
  }

  var id: Id { get }
  var type: BaseType { get }
  var mutability: Mutability { get }
  var value: Value? { get set }
}

Интерфейс самого модуля тривиален и имеет один метод, принимающий в качестве входного параметра абстрактное синтаксическое дерево. Но для его работы требуется дополнительный объект, которому делегируются некоторые операции над списком переменных:

protocol ExecutorDelegate: AnyObject {
  func declare(symbol: Symbol) throws
  func value(of identifier: Symbol.Id) throws -> Symbol.Value?
  func changeValue(of identifier: Symbol.Id, newValue: Symbol.Value) throws
}

В то время как Executor остается реализовать проход по дереву. В то же время, не стоит забывать о том, что абстрактное синтаксическое дерево достаточно сложная структура, содержащая большое количество ветвей. Поэтому модуль содержит несколько компонентов.

class Executor {
  weak var delegate: ExecutorDelegate? { get set }
  func execute(syntacticTree root: SyntacticNode) throws
}

class ExpressionsExecutor {
  weak var delegate: ExecutorDelegate? { get set }
  func executeExpression(node: SyntacticNode) throws -> Symbol.Value
}

Выполняет вычисление выражения, определенного в дереве.

class IntegerLiteralsExecutor {
  func executeIntegerLiteral(node: SyntacticNode) throws -> Symbol.Value
}

Выполняет вычисление значения целочисленного литерала.

class FloatLiteralsExecutor {
   func executeFloatLiteral(node: SyntacticNode) throws -> Symbol.Value
}

Выполняет вычисление значения литерала с плавающей точкой.

Scope

Также нужен модуль, который бы хранил все переменные, с которыми работает программист. Обычно такой модуль называют Scope (область видимости).

В настоящей реализации языка программирования Ace существуют только одна, глобальная область видимости, но введя понятие Scope, нетрудно будет разработать поддержку классовых и локальных областей видимости.

Данный модуль, как уже было сказано выше, хранит все переменные и обеспечивает операции для работы с ними. Интерфейс представлен ниже:

class Scope: ExecutorDelegate {
  var recordTable: RecordTable { get }
  
  func declare(symbol: Symbol) throws
  func value(of identifier: Symbol.Id) throws -> Symbol.Value?
  func changeValue(of identifier: Symbol.Id, newValue: Symbol.Value) throws
}

Внимательного читателя заинтересует свойство var recordTable: RecordTable. Это некого рода таблица, которая хранит информацию об объявленных переменных. Но при этом информация доступна только для чтения. Такой подход довольно удобен при отладке программы. Сущность Record имеет следующий интерфейс:

struct Record {
  typealias Id = Symbol.Id
  typealias Value = Symbol.Value

  var id: Id { get }
  var type: BaseType { get }
  var value: Value? { get }
}

Compiler

Финальный модуль управляет работой всех перечисленных модулей. Таким образом именно на этом этапе координируются чтение исходного кода, распознание лексических токенов, построение абстрактного синтаксического дерева, выполнение инструкций и вывод результатов.

Благодаря модульной архитектуре код прост в чтении и сопровожнеии, а сам модуль содержит всего один метод:

import Foundation

final class Compiler {
 
 // MARK: - Methods
 
  func compile(file path: String) throws -> RecordTable {
  let sourceCodeManager = SourceCodeManager()
  try sourceCodeManager.open(file: path)
  
  let sourceCode = sourceCodeManager.sourceCode
  let lines = sourceCode.split(separator: "\n")
  
  let tokenParser = TokenParser()
  let syntacticAnalyzer = SyntacticAnalyzer()
  
  let executor = Executor()
  let scope = Scope()
  executor.delegate = scope
  
  for line in lines {
   let tokens = try tokenParser.parse(string: String(line))
   let syntacticTree = try syntacticAnalyzer.parse(tokens: tokens)
   try executor.execute(syntacticTree: syntacticTree)
  }
  
  return scope.recordTable
 }
}

Заключение

В результате был реализован компилятор нового языка программирования Ace. Более того, все заявленые требования были удовлетворены, а модульная архитектура решения позволяет добавлять и разрабатывать новые возможности. Например, объявление методов, классов, интерфейсов, полиморфное поведение и т.д.

Также считаю необходимым привести пример выполнения программы. Исходный код следующего вида:

val value = 0.5

var another = 2.5
another = 3.0

val result = value + another

приведет вы выводу на экран следующих результатов:

value: Double = 0.5
another: Double = 3.0
result: Double = 3.5

Проект open source и доступен по ссылке The Ace Programming Language.

Список литературы

1. Оригинал статьи

2. Совершенный код. Практическое руководство по разработке программного обеспечения

3. Compilers: Principles, Techniques, and Tools

4. Разработка операционной системы и компилятора. Проект Оберон

5. Построение компиляторов