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

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

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

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

Язык: Mu(μ)

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

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

Подходы к двух- и трехступечатому проектированию, которые мы используем на проектах в EDISON Software Development Centre.

Шаги:

• Lexer
• Parser
• Interpreter

Lexer

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

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

Пример:



Из-за того, что 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()
}

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 и вычислять значения, применяя оператор к дочерним узлам.

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)

Заключение

• Ввод 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

• ruslanspivak.com/lsbasi-part1
• www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811
• llvm.org/docs/tutorial