Comments 52
a := '{'; b:='}', для этого уже надо знать, что скобочки эти это не часть строки, а именно комментарий. Моё понимание технологий сильно тормозили именно фразы «разбивает на токены, выделяет ключевые слова», фактически же — маркирует любые сигнатуры, а потом парсер уже старается выкинуть всё что не подходит.
'{bla-bla} ;' — на втрой скобочке КА лексера должен зарезать комментарий, потому что он его распознал, а строку ещё нет. На практике же это корректная строка.
Давайте сначала разъясним, что в вашем языке является комментарием и строкой? Текст между фигурными скобочками — коментарий, а между одинарными кавычками — строка? Если так, то лексер без проблем распознает в вашем примере '{bla-bla} ;' строку, и никакой комментарий не зарежется, потому что комментария никакого и не будет. Более того, лексер будет корректно работать и в том случае, если началом и концом строки будут произвольные последовательности символов. Например, пусть началом и окончанием строки будут маркеры <( и )>. Тогда строка вида
<(aaaa ) bbbb)>также корректно будет распознаваться несмотря на одиночную ) в середине.
Не совсем корректный пример со строкой, куда интереснее как мне кажется строки со вставками кода:
str = "this is a #{true ? "string" : "number"} !"Т.е. тут " в начале строки не заканчивается на "string.
Я когда-то писал подобный лексер на JavaCC: он просто получает контекстное состояние, которое описывается перечислимым типом и хранится стек текущих состояний. Если мы попали в контекст подстановочного выражения, то в нём действуют просто другие правила (не те, которые действуют в контексте строки). В принципе это не сильно усложняет лексер и довольно гибко. У меня был адский язык, который стихийно формировался и до меня совершенно коряво парсился набором регулярных выражений, но это всё вполне неплохо удалось превратить в лексер с примерно пятью состояниями.
Вдохновлялся реализацией лексера во FreeMarker'е, кстати. Там та же проблема и похожее решение.
'{bla-bla} на данный момент КА показывает что комментарий готов, никаких строк нет, потому что для этого надо съесть ещё несколько символов.
А теперь не надо мне рассказывать своё виденье лексера, я прекрасно знаю как он работает. Перечитайте ещё раз вот это:
«разбивает на токены, выделяет ключевые слова»
я спорю именно с этой фразой. а не с тем как работает настоящий лексер.
Токен комментария есть? Есть, до парсера лексер должен вырезать — должен! Ну и пусть режет. Цитирую: «Лексер выделяет ключевые слова, строковые литералы, выкидывает комментарии». Если уж вы отвечаете за чужой комментарий то учитывайте контекст.
- лексер, встретив первую кавычку, будет считать дальнейший ввод строкой, если не будет иных указаний
- лексер, встретив открывающую скобку, будет считать дальнейший ввод комментарием, если не будет иных указаний
- читаем ввод
- встретив закрывающую скобку, лексер выдает токен комментарий, и дальнейшее считает строкой (из стека состояний)
таким образом парсер получит следующий список токенов:
- начало строки
- комментарий: bla-bla
Если комментарии внутри строки не поддерживаются, то лексер выдаст ошибку «не найден конец строки», либо запихнет в строку все до следующей кавычки.
Токен комментария есть? Есть, до парсера лексер должен вырезать — должен! Ну и пусть режет.
Ничего он не должен вырезать в данном случае.
А теперь не надо мне рассказывать своё виденье лексера, я прекрасно знаю как он работает.
Видимо не так уж и прекрасно.
И лексическим анализом, который не разбивает и выделяет, а просто маркирует все сигнатуры, которые найдёт, поэтому участок текста будет помечен обоими маркерами и их может быть хоть сотня на симовол, а вот парсер уже может разрулить такие ситуации имея правило, что комментария не может быть посреди строки, что начало самой строки было не в другом комментарии и т.п.
При этом, я так же не отрицаю, что для простых случаев можно построить единый КА на весь язык, который сразу учитывает все ветки, но там и парсер не нужен будет тогда.
Я смотрел исходники реальных компиляторов, и писал их сам, и нигде такие сложности не требовались. Обычно на входе лексера поток символов из файла, внутри машина состояний, на выходе поток токенов-лексем. Все ситуации с кавычками внутри комментариев и комментариями внутри кавычек разруливаются автоматически, мне даже не приходило в голову что это может представлять какую-то сложность и тем более предмет для спора.
Пример скрипт-кода
Сам интерпретатор, построенный ла базе Coco/R -LL(1)
Из-за наличия функций первый раз сканирование идет в холостом режиме (без выполнения): сбор имен функций, проверка кода на валидность, генерация потока лексем. Второй раз — уже выполнение конкретной функции путем просмотра потока лексем с определенной позиции.
Основное назначение — api-glue для интеграции пользовательских действий, поток непрерываем и выполняется сразу и до конца (самый близкий пример — node.js), поэтому все возможности завесить основной поток исполнения убраны (отсутствуют прямые вызовы скрипт-функций, только в отложенном виде в следующий тик / через таймаут, отсутствуют циклы), отсутствуют вложенные скоупы за исключением скоупа самой функции, апи методы должны возвращать управление максимально быстро, в случае отложенной реакции требуется использовать колбеки.
Если не трогать строки (не создавать новые), то все работает с нулевым memory allocation после первого холостого прохода.
Я сталкивался со следующими случаями, когда с токенизацией тяжело:
Контекстно-зависимые конструкции.
- Интерполяция строк. В этом случае не так просто определить, в каком состоянии находится лексер: "строка" или "интерполируемое выражение", которое обособляется фигурными скобками. Проблема в том, что фигурные скобки могут также быть частью самого выражения:
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` — идея неплохая.
А чем вам Книга Дракона не угодила на русском языке?:-)
Да вроде как раз в КД можно к каждой главе сэмплы писать, которые к концу книги превратятся во что-то похожее на компилятор)
Ну тогда как-то так ;-)
Кстати говоря, можно еще почитать на тему (именно для практиков) отличные туториалы к LLVM
з.ы. а еще когда-то был довольно забавный художественный рассказ в компьютерре )
А как вы предлагаете без лексера и парсера написать язык? Не регулярками же
Чисто для справки. Безлексерный способ разбора с неограниченным бэктрекингом https://en.wikipedia.org/wiki/Parsing_expression_grammar
http://www.vestnik.vsu.ru/pdf/analiz/2008/02/2008_02_09.pdf
Вот, например, можно потыкать онлайн — http://pegjs.org/online.
При помощи, например, flex/bison как раз и создаются генераторы кода для llvm. Да и почему им не быть актуальными? Очень удобно какой-то DSL быстренько сделать или анализатор конфигурационных файлов в каком-то хитром формате.
А что касается меня, то я и сам уже долгое время вынашиваю идею создания своего ЯП, но с синтаксисом и логикой PHP, но без баксов этих и дурной репутации как для школоты, клепающие сайтики игровых кланов на досуге, но логика там действительно для людей, плюс динамическая типизация меня просто сводит с ума) Нет, я не хвалю свое болото, я пробовал множество ЯП, в том числе и Питон в плане динамических, однако в его синтаксисе реально черт ногу сломит, ну а динамическая типизация — это как нестись по шоссе на кабриолете, ибо лично мне хочется наслаждаться именно самой ездой, а не дерганьем рычага коробки передач каждую минуту, особенно в пробках. Так что такие вот думы… Скилы все имеются, но только нужно хотя-бы в общем теорию подтянуть…
Пишем свой язык программирования без мам, пап и бизонов. Часть 0: теория