Пишемо свою мову програмування без мам, тат і бізонів. Частина 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
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.