Объясняем бабушке, как написать свой язык программирования

Автор оригинала: marciok
  • Перевод
  • Tutorial
Это игровая площадка, где я попытаюсь объяснить, как создать малюсенький язык программирования (Mu). Можно посмотреть вживую на открытые исходники здесь или скачать тут. Туториал можете прочитать прямо сейчас.

image

Пишем свой язык программирования (на Swift)


Для того, чтобы написать свой язык программирования, необязательно иметь степень в Computer Science, достаточно понимать 3 базовых шага.

Язык: Mu(μ)


Mu — это минимальный язык, который содержит постфиксный оператор, бинарную операцию и «одноциферные» числа.

Пример: (s 2 4) or (s (s 4 5) 4) or (s (s 4 5) (s 3 2))…

Шаги:


  • Lexer
  • Parser
  • Interpreter

Lexer


В компьютерных науках лексический анализ — это процесс аналитического разбора входной последовательности символов (например, такой как исходный код на одном из языков программирования) с целью получения на выходе последовательности символов, называемых «токенами» (подобно группировке букв в словах).

Группа символов входной последовательности, идентифицируемая на выходе процесса как токен, называется лексемой. В процессе лексического анализа производится распознавание и выделение лексем из входной последовательности символов.
— Википедия

Пример:

image

Из-за того, что Mu так мал — только один оператор и числа — вы можете просто совершать итерации ввода и проверять каждый символ.

enum Token {
    case parensOpen
    case op(String)
    case number(Int)
    case parensClose
}

struct Lexer {

    static func tokenize(_ input: String) -> [Token] {
        return input.characters.flatMap {
            switch $0 {
                case "(": return Token.parensOpen
                case ")": return Token.parensClose
                case "s": return Token.op($0.description)
            default:
                if "0"..."9" ~= $0 {
                    return Token.number(Int($0.description)!)
                }
            }

            return nil
        }
    }
}

let input = "(s (s 4 5) 4)"
let tokens = Lexer.tokenize(input)

Parser


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

Grammar:


expression: parensOpen operator primaryExpression primaryExpression parensClose
primaryExpression: expression | number
parensOpen: "("
parensClose: ")"
operator: "s"
number: [0-9]

Грамматика Mu — это бесконтекстная грамматика, что означает, что она описывает все возможные варианты строк в языке. Парсер начинает с верха (корня сгенерированного дерева) и двигается до самого нижнего узла.

Совет: код должен быть прямым представлением граммматики

func parseExpression() -> ExpressionNode {
   ...
   firstPrimaryExpression = parsePrimaryExpression()
   secondPrimaryExpression = parsePrimaryExpression()
   ...
}

func parseExpression() -> PrimaryExpressionNode {
   return parseExpression() || parseNumber()
}

image

indirect enum PrimaryExpressionNode {
    case number(Int)
    case expression(ExpressionNode)
}

struct ExpressionNode {
    var op: String
    var firstExpression: PrimaryExpressionNode
    var secondExpression: PrimaryExpressionNode
}

struct Parser {

    var index = 0
    let tokens: [Token]
    init(tokens: [Token]) {
        self.tokens = tokens
    }

    mutating func popToken() -> Token {
        let token = tokens[index]
        index += 1

        return token
    }

    mutating func peekToken() -> Token {
        return tokens[index]
    }

    mutating func parse() throws -> ExpressionNode {
        return try parseExpression()
    }

    mutating func parseExpression() throws -> ExpressionNode {
        guard case .parensOpen = popToken() else {
            throw ParsingError.unexpectedToken
        }
        guard case let Token.op(_operator) = popToken() else {
            throw ParsingError.unexpectedToken
        }

        let firstExpression = try parsePrimaryExpression()
        let secondExpression = try parsePrimaryExpression()

        guard case .parensClose = popToken() else {
            throw ParsingError.unexpectedToken
        }

        return ExpressionNode(op: _operator, firstExpression: firstExpression, secondExpression: secondExpression)
    }

    mutating func parsePrimaryExpression() throws -> PrimaryExpressionNode {
        switch peekToken() {
        case .number:
            return try parseNumber()
        case .parensOpen:
            let expressionNode = try parseExpression()

            return PrimaryExpressionNode.expression(expressionNode)
        default:
            throw ParsingError.unexpectedToken
        }
    }

    mutating func parseNumber() throws -> PrimaryExpressionNode {
        guard case let Token.number(n) = popToken() else { throw ParsingError.unexpectedToken }

        return PrimaryExpressionNode.number(n)
    }

}

//MARK: Utils

extension ExpressionNode: CustomStringConvertible {
    public var description: String {
        return "\(op) -> [\(firstExpression), \(secondExpression)]"
    }
}
extension PrimaryExpressionNode: CustomStringConvertible {
    public var description: String {
        switch self {
        case .number(let n): return n.description
        case .expression(let exp): return exp.description
        }
    }
}


let input = "(s 2 (s 3 5))"
let tokens = Lexer.tokenize(input)
var parser = Parser(tokens: tokens)
var ast = try! parser.parse()

Interpreter


В computer science, интерпретатор — это программа, которая последовательно выполняет инструкции, написанные на языке программирования или скриптовом языке, без предварительной компиляции в машинный код. (Википедия)

Пример:

Интерпретатор Mu будет проходить через свои A.S.T и вычислять значения, применяя оператор к дочерним узлам.

image

enum InterpreterError: Error {
    case unknownOperator
}

struct Interpreter {
    static func eval(_ expression: ExpressionNode) throws -> Int {
        let firstEval = try eval(expression.first)
        let secEval = try eval(expression.second)

        if expression.op == "s" {
            return firstEval + secEval
        }

        throw InterpreterError.unknownOperator
    }    

    static func eval(_ prim: PrimaryExpressionNode) throws -> Int {
        switch prim {
        case .expression(let exp):
            return try eval(exp)
        case .number(let n):
            return Int(n)
        }
    }

}

let input = "(s (s 5 2) 4)"
let tokens = Lexer.tokenize(input)
var parser = Parser(tokens: tokens)

let ast = try! parser.parse()
try! Interpreter.eval(ast)

Заключение


image

  • Ввод let input = "(s (s 4 5) 4)
  • Извлекаем массив токенов (Lexing) let tokens = Lexer.tokenize(input)
  • Парсим полученные токены в дерево (Parsing).
var parser = Parser(tokens: tokens)
let ast = try! parser.parse()

  • Проходим по дереву, вычисляя значения, находящиеся внутри узлов (Interpreting). let result = try! Interpreter.eval(ast)

Resources





Поддержка публикации — компания Edison, которая специализируется на автоматизации асфальтных заводов и разработке платежных систем и терминалов.
Edison
95,00
Изобретаем успех: софт и стартапы
Поддержать автора
Поделиться публикацией

Комментарии 13

    +8

    Может нужно указать, что пишем его на swift? А то ломанулся смотреть код и ничего почти не понял

      +1
      Теоретически хаб Свифт добавлен, но я тоже в начале подвис. В тексте не помешало бы, да. Перевод конечно, но тем не менее.
      +1
      > Это игровая площадка
      Главное, чтобы для бабушки было без последствий
        +15

        Моя бабушка не знает что такое Swift. Она только асм уважает :(

          +6
          Mu — это минимальный язык, который содержит постфиксный оператор, бинарную операцию и «одноциферные» числа.

          Пример: (s 2 4) or (s (s 4 5) 4) or (s (s 4 5) (s 3 2))…

          Это вы сейчас про префиксный оператор? Постфиксный — это вот:
          (2 4 s) or ((4 5 s) 4 s) or ((4 5 s) (3 2 s) s)
          У постфиксных операторов есть плюс — на момент выполнения уже известны все операнды.
            0
            Вспоминается не только Учитель Йода, но и МК-61.
            Обратная польская удобнее для выполнения, а польская — для разбора в абстрактное дерево.
            +1
            Объясните почему indirect для enum использовали?
              0
              Потому что один из конструкторов перечисления содержит структуру, которая содержит перечисление, один из конструкторов которого содержит структуру… Не в курсе деталей, но именно метка indirect позволяет описывать рекурсивные перечисления.
              +2
              Вы уверены, что изложение в статье годится для объяснения бабушке? Отличная у вас бабушка, надо сказать
                0
                Вот-вот, кто бы мне сначала объяснил =)
                  0
                  Это перевод
                    +1
                    Я понимаю, что это перевод, но в оригинале не было ни слова про бабушку. Отсюда и вывод, что бабушка ваша
                  +2
                  Создать тривиальный язык действительно несложно, кто бы сомневался. Это в документации LLVM делается, например. А ваш язык даже не Тьюринг-полный, вы скорее вводите бабушку в заблуждение.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое