Comments 52
В древние времена памяти было мало, и введение прохода лексического анализа позволяло превратить «много символов» в «мало токенов», что серьезно экономило память.
В современных условиях эта экономия бессмысленна.
Наоборот, в современных языках есть множество контекстов, в каждом из которых действуют разные ключевые слова и разные правила токенизации (см оператор ">>" с++ vs ">" как терминатор параметров шаблонов).
Это приводит к усложнению лексера и парсера и введению сложного промежуточного токенного синтаксиса.
Решение — исключить фазу токенизации.
Синтаксический анализатор может напрямую работать с потоком символов.
Лексический анализ ведет к упрощению архитектуры компилятора. Дело тут не в древних временах, а именно в архитектуре. Лексер выделяет ключевые слова, идентификаторы, операторы, строковые и числовые литералы, выкидывает комментарии и пробельные символы, превращая хаос текстового ввода в упорядоченную структуру однотипных объектов-токенов. Это очень сильно упрощает работу парсера именно архитектурно.
Проблема в том, что идентификаторы и операторы могут означать разное, нашли что-то, а это может быть просто часть строки константы (a := 'procedure delta'), или, к примеру, вы собрались вырезать комментарий:
a := '{'; b:='}', для этого уже надо знать, что скобочки эти это не часть строки, а именно комментарий. Моё понимание технологий сильно тормозили именно фразы «разбивает на токены, выделяет ключевые слова», фактически же — маркирует любые сигнатуры, а потом парсер уже старается выкинуть всё что не подходит.
Ну так лексер как раз и делает то что нужно. Машина состояний же — если встретили кавычку, переходим в режим «строка» и ждем закрывающую кавычку (возможно с учетом экранирующих символов). Встретили начало комментария — переходим в режим «ожидание конца комментария» и т.д.
Если вы встретили кавычку, это не значит, что вы встретили вторую, а комменатрий уже после этого мог начаться и закончиться: a := '{; b:='}' (я удалил одну кавчку). У нас строка равана этому '{; b:=', или мы вырезали комментарий и получили ''? Отвечать не надо, я просто иллюстрирую свою мысль.

Исправить не успел, но я думаю вы поняли о чём я говорю:
'{bla-bla} ;' — на втрой скобочке КА лексера должен зарезать комментарий, потому что он его распознал, а строку ещё нет. На практике же это корректная строка.

Давайте сначала разъясним, что в вашем языке является комментарием и строкой? Текст между фигурными скобочками — коментарий, а между одинарными кавычками — строка? Если так, то лексер без проблем распознает в вашем примере '{bla-bla} ;' строку, и никакой комментарий не зарежется, потому что комментария никакого и не будет. Более того, лексер будет корректно работать и в том случае, если началом и концом строки будут произвольные последовательности символов. Например, пусть началом и окончанием строки будут маркеры <( и )>. Тогда строка вида


<(aaaa ) bbbb)>

также корректно будет распознаваться несмотря на одиночную ) в середине.

Не совсем корректный пример со строкой, куда интереснее как мне кажется строки со вставками кода:


str = "this is a #{true ? "string" : "number"} !"

Т.е. тут " в начале строки не заканчивается на "string.

Я когда-то писал подобный лексер на JavaCC: он просто получает контекстное состояние, которое описывается перечислимым типом и хранится стек текущих состояний. Если мы попали в контекст подстановочного выражения, то в нём действуют просто другие правила (не те, которые действуют в контексте строки). В принципе это не сильно усложняет лексер и довольно гибко. У меня был адский язык, который стихийно формировался и до меня совершенно коряво парсился набором регулярных выражений, но это всё вполне неплохо удалось превратить в лексер с примерно пятью состояниями.


Вдохновлялся реализацией лексера во FreeMarker'е, кстати. Там та же проблема и похожее решение.

Вы всё правильно поняли, но не объяснили почему не будет комментария, вы не путаете лексер и парсер? Согласно лексеру:
'{bla-bla} на данный момент КА показывает что комментарий готов, никаких строк нет, потому что для этого надо съесть ещё несколько символов.
А теперь не надо мне рассказывать своё виденье лексера, я прекрасно знаю как он работает. Перечитайте ещё раз вот это:
«разбивает на токены, выделяет ключевые слова»
я спорю именно с этой фразой. а не с тем как работает настоящий лексер.
Токен комментария есть? Есть, до парсера лексер должен вырезать — должен! Ну и пусть режет. Цитирую: «Лексер выделяет ключевые слова, строковые литералы, выкидывает комментарии». Если уж вы отвечаете за чужой комментарий то учитывайте контекст.
Я так понимаю, КА на первой кавычке перейдет в состояние «началась строковая константа», и на последней фигурной скобке будет все еще находиться в этом состоянии. Если встретит конец файла, выдаст ошибку «незавершенная строка». Без комментариев, так сказать.
Если язык поддерживает комментарии внутри строк (что немного странно), то
  1. лексер, встретив первую кавычку, будет считать дальнейший ввод строкой, если не будет иных указаний
  2. лексер, встретив открывающую скобку, будет считать дальнейший ввод комментарием, если не будет иных указаний
  3. читаем ввод
  4. встретив закрывающую скобку, лексер выдает токен комментарий, и дальнейшее считает строкой (из стека состояний)

таким образом парсер получит следующий список токенов:
  1. начало строки
  2. комментарий: bla-bla

Если комментарии внутри строки не поддерживаются, то лексер выдаст ошибку «не найден конец строки», либо запихнет в строку все до следующей кавычки.
Токен комментария есть? Есть, до парсера лексер должен вырезать — должен! Ну и пусть режет.

Ничего он не должен вырезать в данном случае.


А теперь не надо мне рассказывать своё виденье лексера, я прекрасно знаю как он работает.

Видимо не так уж и прекрасно.

Что бы не размусоливать тему, пояснюсь дополнительно. Есть огромная разница между разбивкой текста на токены, что подразумевает ИЛИ — ИЛИ, то есть должен быть однозначно сделан выбор, строка это или комментарий, чем, собственно будет заниматься парсер.
И лексическим анализом, который не разбивает и выделяет, а просто маркирует все сигнатуры, которые найдёт, поэтому участок текста будет помечен обоими маркерами и их может быть хоть сотня на симовол, а вот парсер уже может разрулить такие ситуации имея правило, что комментария не может быть посреди строки, что начало самой строки было не в другом комментарии и т.п.
При этом, я так же не отрицаю, что для простых случаев можно построить единый КА на весь язык, который сразу учитывает все ветки, но там и парсер не нужен будет тогда.
Простите, а в каких реальных компиляторах применяется это маркирование?
Я смотрел исходники реальных компиляторов, и писал их сам, и нигде такие сложности не требовались. Обычно на входе лексера поток символов из файла, внутри машина состояний, на выходе поток токенов-лексем. Все ситуации с кавычками внутри комментариев и комментариями внутри кавычек разруливаются автоматически, мне даже не приходило в голову что это может представлять какую-то сложность и тем более предмет для спора.
А еще дает возможность быстро исполнять код в режиме интерпретатора без генерации байткода для своей VM-среды (реентерабельность без повторного анализа исходного кода и сильного усложнения всей скрипт-системы).
А в чем ускорение? Большинство кода исполняется один раз, да и генерация байткода после анализа — слезы.
Ускорение в том, что нет необходимости вообще иметь VM и дополнительную стадию генерации кода — можно исполнять прямо так и на языке хост-системы:
Пример скрипт-кода
Сам интерпретатор, построенный ла базе Coco/R -LL(1)
Из-за наличия функций первый раз сканирование идет в холостом режиме (без выполнения): сбор имен функций, проверка кода на валидность, генерация потока лексем. Второй раз — уже выполнение конкретной функции путем просмотра потока лексем с определенной позиции.
Основное назначение — api-glue для интеграции пользовательских действий, поток непрерываем и выполняется сразу и до конца (самый близкий пример — node.js), поэтому все возможности завесить основной поток исполнения убраны (отсутствуют прямые вызовы скрипт-функций, только в отложенном виде в следующий тик / через таймаут, отсутствуют циклы), отсутствуют вложенные скоупы за исключением скоупа самой функции, апи методы должны возвращать управление максимально быстро, в случае отложенной реакции требуется использовать колбеки.
Если не трогать строки (не создавать новые), то все работает с нулевым memory allocation после первого холостого прохода.
Комбинаторные парсеры достаточно легко пишутся и без лексера. А вот на скорость разбора лексер сказывается хорошо.

Как раз сейчас пишу что-то вроде компилятора для одного язычка, для преобразования в AST там Attoparsec, и не очень понимаю, зачем мне лексер в этом случае. Особенно учитывая, что язык местами контекстно-зависимый.

Я сталкивался со следующими случаями, когда с токенизацией тяжело:


Контекстно-зависимые конструкции.


  • Интерполяция строк. В этом случае не так просто определить, в каком состоянии находится лексер: "строка" или "интерполируемое выражение", которое обособляется фигурными скобками. Проблема в том, что фигурные скобки могут также быть частью самого выражения:
    s = $"{(p.Age == 2 ? $"{new Person { } }" : "")}";
  • Heredoc конструкции в PHP. Для того, чтобы выйти из режима строки, нужно сравнивать лексему с начальным маркером EOT:
    public $bar = <<<EOT
    bar
    EOT;

Директивы препроцессора. Во время их обработки необходимо выяснять, а нужно ли разбирать на токены и парсить фрагменты кода после каждой директивы? Проблема заключается в том что сами директивы могут быть выражениями, которые необходимо разбирать и вычислять на этапе токенизации, например, #if DEBUG && ALL_TESTS. Если же не вычислять значение директивы, то невалидный код может попасть в парсер и добавить ошибок. В качестве решения задачу можно разбить на два этапа: обработка директив препроцессора с их удалением и непосредственно парсинг чистого исходного кода.


В лексерном ANTLR для ресолвинга данных случаев можно использовать семантические предикаты и экшены (вставки целевого кода в грамматику). Об этих вещах, кстати, я писал в статье о теории и практике исходного кода, в разделе C#-грамматика и других.

И это все? Чем эта статья отличается от большого количества других парсерных "Hello world"?


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

Если быть точным, то парсер строит дерево разбора (parse tree), а не AST. AST — это дерево разбора, из которого удалены все не значимые токены. Эти токены используется для того, чтобы код можно было разобрать (скобки, запятые и т.д.), но не нужны для дальнейших преобразований.


Ну и правильно, что термин "лексема" обособлен в скобки, поскольку парсеру по сути важен только тип лексемы, а нее ее значение (за исключением контекстно-зависимых конструкций, например, Heredoc в PHP, в которой значение токена используется на этапе парсинга).

И это все?

Это краткая вводная часть, которая знакомит новичков с базовыми понятиями, которыми мы будем оперировать в данной серии.


Чем эта статья отличается от большого количества других парсерных "Hello world"?

Данная серия и не рассчитана на людей наизусть помнящих Dragon Book (хотя может и они чего подчерпнут), а скорее адресована новичкам чтобы они тоже вошли в курс дела.


Если быть точным, то парсер строит дерево разбора (parse tree), а не AST. AST — это дерево разбора, из которого удалены все не значимые токены

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


В данной серии, мы используем именно такой подход, что из токенов сразу строит AST, выбрасывая все лишнее.


Ну и правильно, что термин "лексема" обособлен в скобки, поскольку парсеру по сути важен только тип лексемы, а нее ее значение

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

Данная серия и не рассчитана на людей наизусть помнящих Dragon Book (хотя может и они чего подчерпнут), а скорее адресована новичкам чтобы они тоже вошли в курс дела.

Таких статей только на хабре десятки. А некоторые понятия не совсем корректно определены.


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

Речь шла не о компиляторе, а о парсинге. Например в Roslyn результатом парсинга является достоверное (fidelity) дерево разбора, которое может быть преобразовано обратно в код символ в символ, включая пробелы, комментарии и директивы препроцессора, даже если в нем будут синтаксические ошибки. Да и ANTLR возвращает сырое дерево разбора, которое с помощью визиторов можно преобразовать в другую форму.


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

Это вопрос терминологии. Значение токена и есть лексема. Почему без значений не выйдет? У вас какой-нибудь sql-подобный язык с кучей инструкций на каждый чих?

Статья годная, учитывая, что на русском нет почти ничего подобного. Жду продолжения ;)
P. S. `<-` вместо `return` — идея неплохая.
На русском, как раз, много годного, но статья — ни о чём. Я при написании компилятора очень долго не мог понять зачем разделены терминалы и нетерминалы, чем лексер от парсера отличается и много подобных штук, хотя книгу дракона читал. И, кстати, про вырезание комментариев: строки-константы это те же комментарии, так что де факто — можно ничего и не резать.
Мне не понравилась, слишком много лишнего, это скорее раздельное описание технологий, чем туториал о том, как написать компилятор, голова от неё пухнет, пока всё в комплексе не осознаешь приходится просто запихивать в себя всю ту информацию и это извращение. Фактически, надо сначала показать как сделать компилятор, потом прямо в процессе вводить всякие расширения нотаций, АСТ, лексеры, парсеры и тому подобное, тогда очень чётко начинаешь осознавать что умные дядечки целые теоремы выводили и математический базис разработали специально для этих штук, которые вдруг резко обрели смысл и стали черезвычайно важными и требующими как раз научного подхода.

Да вроде как раз в КД можно к каждой главе сэмплы писать, которые к концу книги превратятся во что-то похожее на компилятор)
Ну тогда как-то так ;-)

А если глава выглядит заумным бредом, где талдычат какую-то элементарную фигню, но подкреплённую схемами на которые даже смотреть не хочется? Ты это пропускаешь и дальше опач-ки в целом всё понятно. но при попытке конкретизировать в коде, получаешь парадокс, где змея ест свой хвост и тут же вообще не понятно как в принципе это может работать. Поэтому никакого поэтапнго не будет. Нужно послойно, а не поэтапно.
В защиту книги дракона — в конце книги в приложении приводится пример (код на Java) для простейшего компилятора с хорошими пояснениями. Если не изменяет память тот пример доходит до генерации синтаксического дерева и трехадресного кода. Оптимизации в том примере еще не рассматриваются. Глава небольшая, но при этом содержит достаточно комментариев к каждому этапу.
Наконец-то, habralang. Правда, первенький пока получается уродцем, да что ж сделать, лексер, токены, тяжелое наследие, нищета и собаки.

А как вы предлагаете без лексера и парсера написать язык? Не регулярками же

Прошу прощения за то что врываюсь, но разве с появлением LLVM все эти LEXX/YACC/BISON остаются актуальны?

При помощи, например, flex/bison как раз и создаются генераторы кода для llvm. Да и почему им не быть актуальными? Очень удобно какой-то DSL быстренько сделать или анализатор конфигурационных файлов в каком-то хитром формате.

ЕМНИП, в LLVM есть свой механизм указания грамматик.
EDIT: впрочем, согласен, для парсера конфигов LLVM это overkill.
А можно ссылочку на поддержку парсеров в LLVM? Я считал что LLVM отвечает только на backend компилятора, а для frontend и так хватает инструментов.
Не будет ссылочки, ошибся. Таки да, конкретно под парсинг там ничего нет (кроме встроенного парсера C/C++). Беру свои слова обратно.
Разделите код на модули, хотя бы на лексер, парсер, кодогенератор.
source code -(Lexer)-> tokens -(Parser)-> AST -(Compiler)-> js code

Так и есть, будет написано 3 модуля: Lexer, Parser и Compiler.

Будет, в черновике уже лежит заготовка для части "1", но сейчас у меня нет времени дописать ее (завал на работе).

Жалко, что тема не получила продолжения, так как автор перешел на Phazer(
Со мной та же история. Взялся писать C интерпретатор для javascript да так и не закончил, ибо никому это не нужно.
Ну как сказать не нужно, языков море, а если брать эзотерические, дак их и вовсе сотни (меня всегда интересовал вопрос на что живут их разрабы, которые имеют столько свободного времени на разработку чисто just for fun), другой вопрос, что в процентном соотношении тема определенно не популярна, это так, ибо требует большого числа свободного времени, которым располагают немногие, предпочитая налаживать скиллы уже в действующих языках. Ну и плюс созданием своих языков (а уж особенно полных по Тьюрингу) занимаются действительно продвинутые, которым точно не нужны статьи из цикла «Пишем свой язык программирования для домохозяек», хотя в свете этого как раз такие статьи и необходимы. Поэтому проблема в этом. Хотя шутки шутками, но на Хабре очень давно была действительно годная статья на подобии «Как бы я объяснил своей бабушке что такое язык программирования». Могу поискать, если интересно.

А что касается меня, то я и сам уже долгое время вынашиваю идею создания своего ЯП, но с синтаксисом и логикой PHP, но без баксов этих и дурной репутации как для школоты, клепающие сайтики игровых кланов на досуге, но логика там действительно для людей, плюс динамическая типизация меня просто сводит с ума) Нет, я не хвалю свое болото, я пробовал множество ЯП, в том числе и Питон в плане динамических, однако в его синтаксисе реально черт ногу сломит, ну а динамическая типизация — это как нестись по шоссе на кабриолете, ибо лично мне хочется наслаждаться именно самой ездой, а не дерганьем рычага коробки передач каждую минуту, особенно в пробках. Так что такие вот думы… Скилы все имеются, но только нужно хотя-бы в общем теорию подтянуть…
Only those users with full accounts are able to leave comments. Log in, please.