Пишем свой язык программирования без мам, пап и бизонов. Часть 0: теория

Тема написания своего ЯПа не дает мне покоя уже около полугода. Я не ставил перед собой цель "убить" CoffeeScript, TypeScript, ELM, тысячи их, я просто хотел понять кухню и как они вообще пишутся.

К моему неприятному удивлению, большинство из этих языков используют Jison (Bison для JavaScript), а это не совсем попадало под мою задачу — "понять", так как по сути дела Jison делает все за вас, собирает AST по заданным вами правилам (Jison как таковой отличный инструмент, который делает за вас львиную долю работы, но сейчас не о нем).

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

Стоит заметить, что данное руководство не привязано к JavaScript, он выбран исключительно из соображений скорости разработки и читаемости, так что вы можете написать свой "лисп"/"питон"/"ваш абсолютно новый синтаксис" на любом знакомом вам языке.

Также до момента написании компилятора (в нашем случае транслятора), процесс написания языка не отличается от процессов создания языков компилируемых в ASM/JVM bitcode/LLVM bitcode/etc, а это значит, что данное руководство не ограничивается созданием языка трансляцируемого в JavaScript.

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

Немного теории

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

source code -(Lexer)-> tokens -(Parser)-> AST -(Compiler)-> js code

Что тут происходит:

1) Lexer

Исходный код нашей программы разбивается на лексемы. По-простому это нахождение в исходном тексте ключевых слов, литералов, символов, идентификаторов и т.д.

Т.е. на выходе из этого (CoffeeScript):

a = true

if a
    console.log('Hello, lexer')

Мы получаем это (сокращенная запись):

[IDENTIFIER:"a"]
[ASSIGN:"="]
[BOOLEAN:"true"]
[NEWLINE:"n"]
[NEWLINE:"n"]
[KEYWORD:"if"]
[IDENTIFIER:"a"]
[NEWLINE:"n"]
[INDENT:"    "]
[IDENTIFIER:"console"]
[DOT:"."]
[IDENTIFIER:"log"]
[ROUND_BRAKET_START:"("]
[STRING:"'Hello, lexer'"]
[ROUND_BRAKET_END:")"]
[NEWLINE:"n"]
[OUTDENT:""]
[EOF:"EOF"]

Так-как CoffeeScript отступо-чувствительный и не имеет явного выделения блока скобками { и }, блоки отделяются отступами (INDENTом и OUTDENTом), которые по сути заменяет скобки.

2) Parser

Парсер составляет AST из токенов (лексем). Он обходит весь массив и рекурсивно подбирает подходящие паттерны, основываясь на типи токена или их последовательности.

Из полученных токенов в пункте 1, parser составит, примерно такое дерево (сокращенная запись):

{
  type: 'ROOT', // Основная нода нешего дерава
  nodes: [{
    type: 'VARIABLE', // a = true
    id: {
      type: 'IDENTIFIER',
      value: 'a'
    },
    init: {
      type: 'LITERAL',
      value: true
    }
  }, {
    type: 'IF_STATEMENT', // Условное выражение
    test: {
      type: 'IDENTIFIER',
      value: 'a'
    },
    consequent: {
      type: 'BLOCK_STATEMENT',
      nodes: [{
        type: 'EXPRESSION_STATEMENT', // Вызов console.log
        expression: {
          type: 'CALL_EXPRESSION',
          callee: {
            type: 'MEMBER_EXPRESSION',
            object: {
              type: 'IDENTIFIER',
              value: 'console'
            },
            property: {
              type: 'IDENTIFIER',
              value: 'log'
            }
          },
          arguments: [{
            type: 'LITERAL',
            value: 'Hello, lexer'
          }]
        }
      }]
    }
  }]
}

Не стоит пугаться объема дерева, на деле он генерируется рекурсивно и его создание не вызывает трудностей.

3) Compiler

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

Компилятор (читай транслятор) преобразует Абстрактно-Синтаксическое Дерево в JavaScript код:

var a = true;

if (a) {
  console.log('Hello, lexer');
}

Вот и все. Большинство компиляторов работают именно по такому принципу (с незначительными изменениями. Иногда добавляют процесс стримминга исходного текста в поток символов, иногда напротив объединяют парсинг и компиляцию в один этап, но не нам их судить).

Habrlang

Итак, разобравшись с теорией, нам предстоит собрать свой язык программирования, у которого будет примерно следующий синтаксис (что-бы не особо париться, мы будем делать смесь из Ruby, Python и CoffeeScript):

#!/bin/habrlang
# Hello habrlang

def hello
  <- "world"
end

console.log(hello())

В следующей главе вы реализуем все основные классы нашего транслятора, и научим его транслировать комментарии Habrlang'а в JavaScript.

Github Repo: https://github.com/SuperPaintman/habrlang

Автор: SuperPaintman

Источник