Тема написания своего ЯПа не дает мне покоя уже около полугода. Я не ставил перед собой цель "убить" 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
Комментарии (47)
KvanTTT
29.11.2016 19:36+5И это все? Чем эта статья отличается от большого количества других парсерных "Hello world"?
Парсер составляет AST из токенов (лексем). Он обходит весь массив и рекурсивно подбирает подходящие паттерны, основываясь на типи токена или их последовательности.
Если быть точным, то парсер строит дерево разбора (parse tree), а не AST. AST — это дерево разбора, из которого удалены все не значимые токены. Эти токены используется для того, чтобы код можно было разобрать (скобки, запятые и т.д.), но не нужны для дальнейших преобразований.
Ну и правильно, что термин "лексема" обособлен в скобки, поскольку парсеру по сути важен только тип лексемы, а нее ее значение (за исключением контекстно-зависимых конструкций, например, Heredoc в PHP, в которой значение токена используется на этапе парсинга).
SuperPaintman
29.11.2016 23:51+1И это все?
Это краткая вводная часть, которая знакомит новичков с базовыми понятиями, которыми мы будем оперировать в данной серии.
Чем эта статья отличается от большого количества других парсерных "Hello world"?
Данная серия и не рассчитана на людей наизусть помнящих Dragon Book (хотя может и они чего подчерпнут), а скорее адресована новичкам чтобы они тоже вошли в курс дела.
Если быть точным, то парсер строит дерево разбора (parse tree), а не AST. AST — это дерево разбора, из которого удалены все не значимые токены
Ни разу не встречал унифицированный компилятор, который бы все делал так-же, как и его собраться. Подходы разные, разные и этапы. Как я писал некоторые составляют стримы из исходников, другие же выбрасывают лексеры.
В данной серии, мы используем именно такой подход, что из токенов сразу строит AST, выбрасывая все лишнее.
Ну и правильно, что термин "лексема" обособлен в скобки, поскольку парсеру по сути важен только тип лексемы, а нее ее значение
Опять же вопрос архитектуры. Но в нашем синтаксисе, я полагаю, без значений лексем не выйдет, так как иначе прийдется плодить уйму типов.
KvanTTT
30.11.2016 02:21-2Данная серия и не рассчитана на людей наизусть помнящих Dragon Book (хотя может и они чего подчерпнут), а скорее адресована новичкам чтобы они тоже вошли в курс дела.
Таких статей только на хабре десятки. А некоторые понятия не совсем корректно определены.
Ни разу не встречал унифицированный компилятор, который бы все делал так-же, как и его собраться. Подходы разные, разные и этапы.
Речь шла не о компиляторе, а о парсинге. Например в Roslyn результатом парсинга является достоверное (fidelity) дерево разбора, которое может быть преобразовано обратно в код символ в символ, включая пробелы, комментарии и директивы препроцессора, даже если в нем будут синтаксические ошибки. Да и ANTLR возвращает сырое дерево разбора, которое с помощью визиторов можно преобразовать в другую форму.
Опять же вопрос архитектуры. Но в нашем синтаксисе, я полагаю, без значений лексем не выйдет, так как иначе прийдется плодить уйму типов.
Это вопрос терминологии. Значение токена и есть лексема. Почему без значений не выйдет? У вас какой-нибудь sql-подобный язык с кучей инструкций на каждый чих?
handicraftsman
29.11.2016 19:38-6Статья годная, учитывая, что на русском нет почти ничего подобного. Жду продолжения ;)
P. S. `<-` вместо `return` — идея неплохая.VaalKIA
29.11.2016 23:57На русском, как раз, много годного, но статья — ни о чём. Я при написании компилятора очень долго не мог понять зачем разделены терминалы и нетерминалы, чем лексер от парсера отличается и много подобных штук, хотя книгу дракона читал. И, кстати, про вырезание комментариев: строки-константы это те же комментарии, так что де факто — можно ничего и не резать.
BelBES
30.11.2016 00:01+5А чем вам Книга Дракона не угодила на русском языке?:-)
VaalKIA
30.11.2016 00:15Мне не понравилась, слишком много лишнего, это скорее раздельное описание технологий, чем туториал о том, как написать компилятор, голова от неё пухнет, пока всё в комплексе не осознаешь приходится просто запихивать в себя всю ту информацию и это извращение. Фактически, надо сначала показать как сделать компилятор, потом прямо в процессе вводить всякие расширения нотаций, АСТ, лексеры, парсеры и тому подобное, тогда очень чётко начинаешь осознавать что умные дядечки целые теоремы выводили и математический базис разработали специально для этих штук, которые вдруг резко обрели смысл и стали черезвычайно важными и требующими как раз научного подхода.
BelBES
30.11.2016 00:22Да вроде как раз в КД можно к каждой главе сэмплы писать, которые к концу книги превратятся во что-то похожее на компилятор)
Ну тогда как-то так ;-)VaalKIA
30.11.2016 01:13А если глава выглядит заумным бредом, где талдычат какую-то элементарную фигню, но подкреплённую схемами на которые даже смотреть не хочется? Ты это пропускаешь и дальше опач-ки в целом всё понятно. но при попытке конкретизировать в коде, получаешь парадокс, где змея ест свой хвост и тут же вообще не понятно как в принципе это может работать. Поэтому никакого поэтапнго не будет. Нужно послойно, а не поэтапно.
BelBES
30.11.2016 21:24Кстати говоря, можно еще почитать на тему (именно для практиков) отличные туториалы к LLVM
з.ы. а еще когда-то был довольно забавный художественный рассказ в компьютерре )
SerKOS
30.11.2016 22:00В защиту книги дракона — в конце книги в приложении приводится пример (код на Java) для простейшего компилятора с хорошими пояснениями. Если не изменяет память тот пример доходит до генерации синтаксического дерева и трехадресного кода. Оптимизации в том примере еще не рассматриваются. Глава небольшая, но при этом содержит достаточно комментариев к каждому этапу.
pengyou
29.11.2016 21:40+2Наконец-то, habralang. Правда, первенький пока получается уродцем, да что ж сделать, лексер, токены, тяжелое наследие, нищета и собаки.
SuperPaintman
29.11.2016 23:55+1А как вы предлагаете без лексера и парсера написать язык? Не регулярками же
TargetSan
30.11.2016 00:33+1Чисто для справки. Безлексерный способ разбора с неограниченным бэктрекингом https://en.wikipedia.org/wiki/Parsing_expression_grammar
Rulexec
01.12.2016 12:39О да. Я не особо осилил лексеры/парсеры, а как увидел PEG — влюбился в них.
Вот, например, можно потыкать онлайн — http://pegjs.org/online.
6opoDuJIo
30.11.2016 00:56+1Прошу прощения за то что врываюсь, но разве с появлением LLVM все эти LEXX/YACC/BISON остаются актуальны?
masai
30.11.2016 01:28При помощи, например, flex/bison как раз и создаются генераторы кода для llvm. Да и почему им не быть актуальными? Очень удобно какой-то DSL быстренько сделать или анализатор конфигурационных файлов в каком-то хитром формате.
6opoDuJIo
30.11.2016 01:45+1ЕМНИП, в LLVM есть свой механизм указания грамматик.
EDIT: впрочем, согласен, для парсера конфигов LLVM это overkill.
potan
30.11.2016 18:14+2А можно ссылочку на поддержку парсеров в LLVM? Я считал что LLVM отвечает только на backend компилятора, а для frontend и так хватает инструментов.
6opoDuJIo
30.11.2016 23:02Не будет ссылочки, ошибся. Таки да, конкретно под парсинг там ничего нет (кроме встроенного парсера C/C++). Беру свои слова обратно.
Lex20
01.12.2016 13:49Разделите код на модули, хотя бы на лексер, парсер, кодогенератор.
SuperPaintman
01.12.2016 15:06source code -(Lexer)-> tokens -(Parser)-> AST -(Compiler)-> js code
Так и есть, будет написано 3 модуля: Lexer, Parser и Compiler.
Kroleg
В древние времена памяти было мало, и введение прохода лексического анализа позволяло превратить «много символов» в «мало токенов», что серьезно экономило память.
В современных условиях эта экономия бессмысленна.
Наоборот, в современных языках есть множество контекстов, в каждом из которых действуют разные ключевые слова и разные правила токенизации (см оператор ">>" с++ vs ">" как терминатор параметров шаблонов).
Это приводит к усложнению лексера и парсера и введению сложного промежуточного токенного синтаксиса.
Решение — исключить фазу токенизации.
Синтаксический анализатор может напрямую работать с потоком символов.
NeoCode
Лексический анализ ведет к упрощению архитектуры компилятора. Дело тут не в древних временах, а именно в архитектуре. Лексер выделяет ключевые слова, идентификаторы, операторы, строковые и числовые литералы, выкидывает комментарии и пробельные символы, превращая хаос текстового ввода в упорядоченную структуру однотипных объектов-токенов. Это очень сильно упрощает работу парсера именно архитектурно.
VaalKIA
Проблема в том, что идентификаторы и операторы могут означать разное, нашли что-то, а это может быть просто часть строки константы (a := 'procedure delta'), или, к примеру, вы собрались вырезать комментарий:
a := '{'; b:='}', для этого уже надо знать, что скобочки эти это не часть строки, а именно комментарий. Моё понимание технологий сильно тормозили именно фразы «разбивает на токены, выделяет ключевые слова», фактически же — маркирует любые сигнатуры, а потом парсер уже старается выкинуть всё что не подходит.
NeoCode
Ну так лексер как раз и делает то что нужно. Машина состояний же — если встретили кавычку, переходим в режим «строка» и ждем закрывающую кавычку (возможно с учетом экранирующих символов). Встретили начало комментария — переходим в режим «ожидание конца комментария» и т.д.
VaalKIA
Если вы встретили кавычку, это не значит, что вы встретили вторую, а комменатрий уже после этого мог начаться и закончиться: a := '{; b:='}' (я удалил одну кавчку). У нас строка равана этому '{; b:=', или мы вырезали комментарий и получили ''? Отвечать не надо, я просто иллюстрирую свою мысль.
VaalKIA
Исправить не успел, но я думаю вы поняли о чём я говорю:
'{bla-bla} ;' — на втрой скобочке КА лексера должен зарезать комментарий, потому что он его распознал, а строку ещё нет. На практике же это корректная строка.
KvanTTT
Давайте сначала разъясним, что в вашем языке является комментарием и строкой? Текст между фигурными скобочками — коментарий, а между одинарными кавычками — строка? Если так, то лексер без проблем распознает в вашем примере
'{bla-bla} ;'строку, и никакой комментарий не зарежется, потому что комментария никакого и не будет. Более того, лексер будет корректно работать и в том случае, если началом и концом строки будут произвольные последовательности символов. Например, пусть началом и окончанием строки будут маркеры<(и)>. Тогда строка видатакже корректно будет распознаваться несмотря на одиночную
)в середине.SuperPaintman
Не совсем корректный пример со строкой, куда интереснее как мне кажется строки со вставками кода:
Т.е. тут
"в начале строки не заканчивается на"string.lany
Я когда-то писал подобный лексер на JavaCC: он просто получает контекстное состояние, которое описывается перечислимым типом и хранится стек текущих состояний. Если мы попали в контекст подстановочного выражения, то в нём действуют просто другие правила (не те, которые действуют в контексте строки). В принципе это не сильно усложняет лексер и довольно гибко. У меня был адский язык, который стихийно формировался и до меня совершенно коряво парсился набором регулярных выражений, но это всё вполне неплохо удалось превратить в лексер с примерно пятью состояниями.
Вдохновлялся реализацией лексера во FreeMarker'е, кстати. Там та же проблема и похожее решение.
VaalKIA
Вы всё правильно поняли, но не объяснили почему не будет комментария, вы не путаете лексер и парсер? Согласно лексеру:
'{bla-bla} на данный момент КА показывает что комментарий готов, никаких строк нет, потому что для этого надо съесть ещё несколько символов.
А теперь не надо мне рассказывать своё виденье лексера, я прекрасно знаю как он работает. Перечитайте ещё раз вот это:
«разбивает на токены, выделяет ключевые слова»
я спорю именно с этой фразой. а не с тем как работает настоящий лексер.
Токен комментария есть? Есть, до парсера лексер должен вырезать — должен! Ну и пусть режет. Цитирую: «Лексер выделяет ключевые слова, строковые литералы, выкидывает комментарии». Если уж вы отвечаете за чужой комментарий то учитывайте контекст.
michael_vostrikov
Я так понимаю, КА на первой кавычке перейдет в состояние «началась строковая константа», и на последней фигурной скобке будет все еще находиться в этом состоянии. Если встретит конец файла, выдаст ошибку «незавершенная строка». Без комментариев, так сказать.
Deosis
Если язык поддерживает комментарии внутри строк (что немного странно), то
таким образом парсер получит следующий список токенов:
Если комментарии внутри строки не поддерживаются, то лексер выдаст ошибку «не найден конец строки», либо запихнет в строку все до следующей кавычки.
KvanTTT
Ничего он не должен вырезать в данном случае.
Видимо не так уж и прекрасно.
VaalKIA
Что бы не размусоливать тему, пояснюсь дополнительно. Есть огромная разница между разбивкой текста на токены, что подразумевает ИЛИ — ИЛИ, то есть должен быть однозначно сделан выбор, строка это или комментарий, чем, собственно будет заниматься парсер.
И лексическим анализом, который не разбивает и выделяет, а просто маркирует все сигнатуры, которые найдёт, поэтому участок текста будет помечен обоими маркерами и их может быть хоть сотня на симовол, а вот парсер уже может разрулить такие ситуации имея правило, что комментария не может быть посреди строки, что начало самой строки было не в другом комментарии и т.п.
При этом, я так же не отрицаю, что для простых случаев можно построить единый КА на весь язык, который сразу учитывает все ветки, но там и парсер не нужен будет тогда.
NeoCode
Простите, а в каких реальных компиляторах применяется это маркирование?
Я смотрел исходники реальных компиляторов, и писал их сам, и нигде такие сложности не требовались. Обычно на входе лексера поток символов из файла, внутри машина состояний, на выходе поток токенов-лексем. Все ситуации с кавычками внутри комментариев и комментариями внутри кавычек разруливаются автоматически, мне даже не приходило в голову что это может представлять какую-то сложность и тем более предмет для спора.
VaalKIA
Сливают карму, тред закончен.
Leopotam
А еще дает возможность быстро исполнять код в режиме интерпретатора без генерации байткода для своей VM-среды (реентерабельность без повторного анализа исходного кода и сильного усложнения всей скрипт-системы).
Siemargl
А в чем ускорение? Большинство кода исполняется один раз, да и генерация байткода после анализа — слезы.
Leopotam
Ускорение в том, что нет необходимости вообще иметь VM и дополнительную стадию генерации кода — можно исполнять прямо так и на языке хост-системы:
Пример скрипт-кода
Сам интерпретатор, построенный ла базе Coco/R -LL(1)
Из-за наличия функций первый раз сканирование идет в холостом режиме (без выполнения): сбор имен функций, проверка кода на валидность, генерация потока лексем. Второй раз — уже выполнение конкретной функции путем просмотра потока лексем с определенной позиции.
Основное назначение — api-glue для интеграции пользовательских действий, поток непрерываем и выполняется сразу и до конца (самый близкий пример — node.js), поэтому все возможности завесить основной поток исполнения убраны (отсутствуют прямые вызовы скрипт-функций, только в отложенном виде в следующий тик / через таймаут, отсутствуют циклы), отсутствуют вложенные скоупы за исключением скоупа самой функции, апи методы должны возвращать управление максимально быстро, в случае отложенной реакции требуется использовать колбеки.
Если не трогать строки (не создавать новые), то все работает с нулевым memory allocation после первого холостого прохода.
potan
Комбинаторные парсеры достаточно легко пишутся и без лексера. А вот на скорость разбора лексер сказывается хорошо.
0xd34df00d
Как раз сейчас пишу что-то вроде компилятора для одного язычка, для преобразования в AST там Attoparsec, и не очень понимаю, зачем мне лексер в этом случае. Особенно учитывая, что язык местами контекстно-зависимый.
KvanTTT
Я сталкивался со следующими случаями, когда с токенизацией тяжело:
Контекстно-зависимые конструкции.
EOT:Директивы препроцессора. Во время их обработки необходимо выяснять, а нужно ли разбирать на токены и парсить фрагменты кода после каждой директивы? Проблема заключается в том что сами директивы могут быть выражениями, которые необходимо разбирать и вычислять на этапе токенизации, например,
#if DEBUG && ALL_TESTS. Если же не вычислять значение директивы, то невалидный код может попасть в парсер и добавить ошибок. В качестве решения задачу можно разбить на два этапа: обработка директив препроцессора с их удалением и непосредственно парсинг чистого исходного кода.В лексерном ANTLR для ресолвинга данных случаев можно использовать семантические предикаты и экшены (вставки целевого кода в грамматику). Об этих вещах, кстати, я писал в статье о теории и практике исходного кода, в разделе C#-грамматика и других.
VaalKIA
А мне за подобное в карму -4, плюсануть не могу.