Comments 44
это классно, что серия продолжается )
Я обещал, что она будет окончена, и она будет окончена!
Hidden text
(Сказал я с совершенно невинным видом, не упоминая долгостроя с троичным вычислителем)
Троичный вычислитель, впрочем, абсолютно точно будет закончен, слишком уж мне нравится тема. Только вот даты назвать не могу :(
Это в качестве начального введения хорошо, конечно, но на контекстно-свободной грамматике далеко не уедешь.
Вы как-то уж больно буквально хотите всё понимать. Во-первых, Тьюринг-полное, можно уехать так далеко, как хотите. Во вторых, теория компиляторов, а тем более, теория формальных языков меня не интересуют совсем. Я хочу, чтобы люди программировать научились.
В практическом отношении это довольно бесполезный опыт. Любой реально применимый язык потребует контекстно-зависимую грамматику, а это гораздо более сложное устройство компилятора, не дюжина регэкспов.
Хм. Мне всё ещё кажется, что вы не поняли моей цели. Я смею надеяться, что написав даже такой простейший компилятор, человек окончательно усвоит, как работает стек. И я бы не назвал это бесполезным опытом в практическом отношении.
Я думаю, что для понимания работы стека это сильно избыточная задача.
А вот то, что из чтения статьи у неподготовленного читателя может создаться впечатление, что так и строится реальный компилятор - нехорошо. Путь-то тупиковый.
Когда используются такие радикальные упрощения задачи, лучше об этом явно писать.
Я думаю, что для понимания работы стека это сильно избыточная задача.
стек - это программа-минимум, вы всё же прочитайте, что я пишу.
А вот то, что из чтения статьи у неподготовленного читателя может создаться впечатление, что так и строится реальный компилятор - нехорошо. Путь-то тупиковый.
Реальный компилятор чего? Вы себе реально представили читателя, увидевшего описание проекта на пятьсот строк кода, и подумавшего, что создателей gcc надо отправить на мороз? Или любой компилятор обязан обрабатывать грамматики нулевого типа?
Ну контекстно-свободных языков-то нет на практике. Даже Лисп, где по сути всего две лексические формы - атом и список - и тот контекстно-зависим за счёт макросов и областей видимости.
Я вообще не специалист в этой теме о чём написал прямо в первом параграфе первой же статьи, но а) какой-нибудь json-то уж наверняка контекстно-независим и б) это вообще out of scope. Моей целью не является научить людей писать компиляторы. И даже если бы у меня была такая цель, то в) я слишком много в своей жизни видел примеров того, как у ученика отбили наглухо желание что-то делать, показав всю красоту теории теормеха до того, как он в первый раз взял в руки отвёртку.
Люди, берите отвёртки, и ковыряйте ими где только вам захочется!
Golang такой: ну да, ну да, пошёл я нафиг... (Ну ладно, он совсем чуточку не дотянул, но максимально близок к context free).
Я не знаю языка Go, но слово context даже в его спецификации встречается 12 раз. А неявных обращений к контексту обычно гораздо больше.
В сети встречается утверждение, что грамматика Go разбирается по алгоритму LALR(1), как и у большинства других языков.
Мне кажется, мы говорим о разном. Настолько я понимаю понятие контекстно-свободной грамматики - это грамматика, в описании которой в левой части правил всегда один нетерминальный символ. И грамматика го этому вполне соответствует. Есть например случаи типа вызов функции vs приведение типа. На уровне грамматики отличить одно от другого не выйдет, поэтому в процессе построения AST понадобится таблица символов. Но можно в принципе обойтись и без неё на этапе парсинга и отдать дальнейшие проблемы на уровень семантического анализа, где проверяются типы и всё такое.
Когда вы начнёте расписывать грамматику Go или другого практически используемого языка по-честному, для yacc или bison, а не в виде полуформальных определений, перемежаемых пояснениями на естественном языке, как в Language Reference, то вам не удастся её расписать контекстно-свободным образом. Конкретно, возникнут продуктивные правила, зависящие от контекста, из которого изначально был выведен нетерминал. И у вас либо выдаст ошибку bison, либо возникнут странные результаты компиляции. Как вы совершенно верно заметили, это можно решать на уровне семантического анализа. Но в этой ситуации именно и заключается вся фишка фронтенда настоящего компилятора, которая не нашла никакого отражения и даже упоминания в искусственном примере в статье.
Ну справедливости ради, я упомянул, что в менее искусственных случаях могут понадобиться более сложные вещи, например, итерации между лексером и парсером :)
Но ещё раз, конкретно компилятор меня не очень интересует, мне нужно объяснить моим студентам, как работает компьютер.
вам не удастся её расписать контекстно-свободным образом
Любой более менее состоявшийся и используемый язык невозможно описать не то что контекстно-свободно, а вообще формально, т.к. слишком много всего нужно учитывать, а со временем еще накапливаются всяческие костыли для поддержки обратной совместимости. Исходный код компилятора и будет спецификацией.
Выделение AST в отдельный слой абстракции - это разумно, т.к. парсер можно написать на основе лаконичной контекстно-свободной грамматики (с некоторыми исключениями), с другой стороны AST скрывает более низкоуровневые детали, которые не нужны семантической подсистеме.
Это еще почему?
Ух и порнография этот ваш мандельброт.
В каком смысле? Вам сам исходник не нравится? :)
Ну, вы маленько прищурьтесь и посмотрите на картинку. Может даже точку особенную найдёте.
Mein gott. Как я был далёк от такой интерпретации :)
Hidden text
Приходит пациент к психиатру:
— Доктор, все говорят, что я сексуальный маньяк.
Доктор: — Любопытно, сейчас проверим.
Достает листок, на котором нарисован квадрат. Что здесь нарисовано?
Пациент: — Это просто. Это кровать. На ней сексом занимаются!
Доктор достает следующий листок, с треугольником: — Ну а тут что нарисовано?
Пациент (хихикая): — Ну, доктор, тут же это… Мне даже говорить неудобно.
Доктор показывает листок с кругом: — А это что?
Пациент: — Ну это же вообще… Я стесняюсь произнести это вслух!
Доктор: — Что ж, все понятно. Вы действительно маньяк.
Пациент: — Но вы, доктор, тоже ведь сексуальный маньяк? Признайтесь?
Доктор: — С чего вы взяли?
Пациент: — А откуда у вас такие картинки?
inta=0
Это можно интерпретировать двояко, порождая разные потоки лексем
Конкретно для этого случая нет, для определения ключевых слов нужно учитывать пробелы и другие небуквенные символы. В int a оно не должно парситься. Вот с GT и GTEQ да, тут только по длине определять.
и выкидывать до конца строки всё, что начинается с двух слешей
Тут не всё так просто, это не будет работать для строковых литералов, которые содержат 2 слеша. Можно на строку проверять раньше комментария, но тогда вся строка это будет одна лексема, и для интерполяции строк "Message: ${str}" нужно будет делать отдельный парсинг.
Интуитивно понятное решение - использовать то правило, которое соответствует большему количеству символов в исходном коде
А правильное решение - не разбивать на лексемы первым шагом. Подумайте, что конкретно это дает? Ничего, мы просто заменяем одну последовательность байт на другую. Зато это создает много проблем, так как на уровне отдельной регулярки мы не знаем контекст, например, была ли уже открывающая кавычка или это комментарий, что и приходится решать заданием порядка.
При этом все равно приходится смотреть "на один токен вперёд". Вместо этого можно просто смотреть на несколько символов вперед. Будет чуть больше работы процессора на этапе парсинга, зато меньше на следующих этапах.
Конкретно для этого случая нет, для определения ключевых слов нужно учитывать пробелы и другие небуквенные символы. В
int aоно не должно парситься. Вот с GT и GTEQ да, тут только по длине определять.
Так в случае с int и inta тоже по длине определять. Если точный match с ключевым словом, то это ключевое слово, если хоть на один символ больше, то идентификатор.
для интерполяции строк
"Message: ${str}"нужно будет делать отдельный парсинг.
Не нужен тут отдельный парсинг - просто внутри интерполяционного выражения входим в режим "выражение" и нормально токенизируем все дальше, до тех пор пока не дойдем до закрывающей фигурной скобки.
А правильное решение - не разбивать на лексемы первым шагом.
Есть разные способ решения, и решение автор тоже является вполне правильным.
Подумайте, что конкретно это дает? Ничего, мы просто заменяем одну последовательность байт на другую.
Дает - последовательность токенов намного короче последовательности символов, а значит быстрей в обработке. Также она имеет больше смысла с точки зрения парсинга.
Зато это создает много проблем, так как на уровне отдельной регулярки мы не знаем контекст, например, была ли уже открывающая кавычка или это комментарий, что и приходится решать заданием порядка.
Лексер имеет общие черты с регулярками, но это не регулярки. Открывающую кавычку, комментарий и другие вещи также можно детектить на уровне лексера (а еще там есть разные режимы).
При этом все равно приходится смотреть "на один токен вперёд". Вместо этого можно просто смотреть на несколько символов вперед.
Смотреть на один токен вперед (в случае лексера - на один символ) - это очень быстрая операция, и она оптимизируется компилятором в быструю jump table с O(1) скоростью. В то время как смотреть на несколько символов вперед медленней.
Будет чуть больше работы процессора на этапе парсинга, зато меньше на следующих этапах.
Это на каких этапах? На этапах после парсинга не нужно ничего, кроме получившегося дерева.
Так в случае с int и inta тоже по длине определять.
Если int это отдельное ключевое слово, которое должно давать T_INT, то его надо определять по выражению r'int(?=[^\w])'. Правило WHITESPACE: [ \t\r\n]+ -> skip в ANTLR примерно это и делает, вызывает завершение текущего токена, оно должно быть определено до ключевых слов.
просто внутри интерполяционного выражения входим в режим "выражение"
Это и есть отдельный парсинг. В статье указаны эти регулярные выражения, я говорил про них.
ignore_comment = r'\/\/.*'
STRING = r'"[^"]*"'
Есть разные способ решения, и решение автор тоже является вполне правильным.
Можно и так сказать, но на мой взгляд правильное решение это то, которое устраняет причину проблемы. Проблемы с неоднозначностью разбиения на лексемы идут из-за первоначального разбиения на лексемы. И вообще определять int как ключевое слово не совсем корректно, оно ничем не отличается от названия класса. Лучше сделать одно выражение TypeName VariableName ?Init ';' и специальную проверку на встроенные типы при обработке дерева.
намного короче последовательности символов, а значит быстрей в обработке
В то время как смотреть на несколько символов вперед медленней.
Я бы не сказал, что намного. Большинство строк это названия классов, переменных и методов, их значения все равно надо хранить. Операторы короче 4 байт, только некоторые ключевые слова длиннее.
Это конкретно сравнение быстрее, но из-за решения неоднозначностей обработка в целом может быть дольше. Собственно, обработка строк в компиляторе PHP хороший пример.
Это на каких этапах?
Построения дерева из потока лексем и его анализа, например рекурсивная обработка арифметических выражений или та же обработка строк в PHP.
Тут не всё так просто, это не будет работать для строковых литералов, которые содержат 2 слеша.
Может, я чего-то не понимаю, но давайте просто проверим?
Если int это отдельное ключевое слово, которое должно давать T_INT, то его надо определять по выражению
r'int(?=[^\w])'.
Если говорить про ANTLR и другие лексеры, то там все работает пооптимальней - строится конечный автомат, который одновременно матчит и INT и ID и в конце приходит к единственному возможному состоянию. Вот это отрицание пробельного символа на конец выглядит несколько избыточно.
Правило
WHITESPACE: [ \t\r\n]+ -> skipв ANTLR примерно это и делает, вызывает завершение текущего токена, оно должно быть определено до ключевых слов.
Конкретно WHITESPACE в большинстве случаев не важно где объявлять, т.к. другие токены не начинаются с пробела. А вот ключевые слова как раз надо объявлять до объявление идентификатора, чтобы он не захватывал все последовательности из символов.
Можно и так сказать, но на мой взгляд правильное решение это то, которое устраняет причину проблемы. Проблемы с неоднозначностью разбиения на лексемы идут из-за первоначального разбиения на лексемы.
Чтобы понять, проблема это или нет, надо сначала посмотреть на формальное описание, грамматику языка. Если там написано, что int - это ключевое слово, которое нельзя использовать в качестве идентификатора, значит это не проблема.
И вообще определять int как ключевое слово не совсем корректно, оно ничем не отличается от названия класса.
Зависит от языка, но в большинстве случаев int это именно ключевое слово. А то, что вы имеете в виду это soft-keywords - когда токен может быть как идентификатором, так и ключевым словом. Таким токеном, например, является var в C#. Обычно soft-keyword используются при введении нового синтаксиса, при сохранении обратной совместимости.
Я бы не сказал, что намного. Большинство строк это названия классов, переменных и методов, их значения все равно надо хранить. Операторы короче 4 байт, только некоторые ключевые слова длиннее.
Ну так эта инфа достается из инфы про токен. Парсеру почти во всех случаях неинтересно какое значение принимает ID (за исключением вышеупомянутых soft-keyword).
Построения дерева из потока лексем и его анализа, например рекурсивная обработка арифметических выражений или та же обработка строк в PHP.
Я детально не знаю как работает интерпретатор PHP, но в этом случае может быть оправдано двигаться по символам, потому что PHP - динамический язык и может работать почти построчно. Но в компилируемых языках типа C#, Java, Kotlin и других вся информация содержится в дереве, никакого повторного парсинга там нет. А еще там есть несколько проходов по дереву, и повторный парсинг бы ухудшил производительность.
Вот это отрицание пробельного символа на конец выглядит несколько избыточно.
В ANTLR-то да, я говорил в контексте статьи.
Конкретно WHITESPACE в большинстве случаев не важно где объявлять
Возможно я что-то перепутал, лень проверять) Я говорю о том, что пробел должен учитываться, хоть в виде отдельного правила, хоть в регэкспе для 'int', тогда 'inta' никогда не распарсится в [int a].
Если там написано, что int - это ключевое слово, которое нельзя использовать в качестве идентификатора, значит это не проблема.
Проблемы с неоднозначностью лексем это в любом случае проблемы, и их надо решать, иначе компилятор работать не будет.
Зависит от языка, но в большинстве случаев int это именно ключевое слово
Мы же говорим про новый язык, в котором необязательно так делать.
Парсеру почти во всех случаях неинтересно какое значение принимает ID
Ну и пусть, копирование строки целиком все равно нужно для дальнейшей обработки, и так для всех ID. На этом фоне то что вы где-то сравнили 2 инта вместо 2 строк не дает большой экономии. Причем большинство ключевых слов различаются в первых байтах.
никакого повторного парсинга там нет
В этой части комментария я не говорил про отдельный парсинг. Отдельный парсинг был про определение строковых констант с помощью регулярных выражений.
Я говорю о том, что пробел должен учитываться, хоть в виде отдельного правила
Это верно.
Мы же говорим про новый язык, в котором необязательно так делать.
Может необязательно, но это не очевидно (не известно какие это неоднозначности может порождать).
Ну и пусть, копирование строки целиком все равно нужно для дальнейшей обработки, и так для всех ID. На этом фоне то что вы где-то сравнили 2 инта вместо 2 строк не дает большой экономии.
Не совсем так - сырые строки из исходного кода нужно процессить, чтобы избавиться от возможных escape последовательностей (и зарепортить ошибки, если они есть). К тому же строки сравнивать дольше - сначала проверяется хеш, а затем производится посимвольное сравнение. Это может повлиять на пефоманс, если это делать на этапе парсера и дальнейших.
Не очень понятно, зачем сравнивать хеш, без лексера мы будем сравнивать строки побайтово. И escape-последовательностей в идентификаторах обычно не бывает.
Чтобы проверить ключевое слово, достаточно сравнить несколько первых байт. Например, правило accessModifier = 'private' | 'protected' | 'public', и в исходном коде указано 'public'. Для определения ветки без лексера, с побайтовым сравнением и откатом текущей позиции на исходную, надо проверить 2 байта в первой ветке, 2 во второй, и 6 в третьей, после этого возвращаем токен Public. Это выглядит дешевле, чем вычислять хеш для 6 символов.
С определением токенов в лексере для замены 'public' на числовой T_PUBLIC нужно сделать те же 6 сравнений байт, это лишь на 4 сравнения меньше. Ну или сделать 6 переходов по таблице переходов, что примерно то же самое. Плюс один переход в парсере для определения ветки. К тому же организация потока токенов дополнительно к исходному потоку байт и проход по нему тоже требуют ресурсов и строковых операций.
А если учесть, что в исходном коде написано public SomeClass methodName(AnotherClass arg), и в любом варианте нам надо побайтово скопировать для компилятора 4 ID общей длиной 34, то замена 'public' на T_PUBLIC мало влияет на общую производительность.
inta=0можно интерпретировать двояко
Это же проблема только из-за регекспов, где у вас требование пробела после зарезервированных слов отсутствует. Ну и - а почему регекспы-то? Классический вариант разбора через конечный автомат с предпросмотром на пару символов и проще, и нагляднее, и разметку кода можно сразу получить для подсветки синтаксиса. Буквально пару дней назад писал очередной лексер - чуть более 300 строк кода получилось, причём основная часть ушла на разбор чисел с плавающей запятой и строк с escape-символами.
Было бы интересно посмотреть на лексер для wend, у вас не найдётся немного времени? Можно было бы попробовать избавиться от зависимости. Парсер там тоже не должен быть суперсложным.
Можно попробовать - но не уверен, что результат поместится в поля комментария. И на шарпе будет, не питон.
Я на шарпе не умею, но, надеюсь, сумею перевести потом на питон. Буду очень благодарен!
Вот так я вижу лексический анализатор здорового человека бывшего курильщика. Шарп си-подобный, не должно возникнуть проблем с пониманием, и комментарии тоже есть. Токен "новая строка" оставил для отладки. Также оставил строку с escape-символами и число с плавающей точкой и суффиксом (типа 1.2е-3km) - просто чтобы попытаться сделать это же регэкспами и сравнить сложность. В типе Lexem помимо токена также присутствует категория (для упрощения дальнейшего разбора) и координаты (чтобы сообщения об ошибках адресно выводить).
Следующий этап будет посложнее (разбор мат.выражений с учётом приоритетов), но тоже посильный для самостоятельного выполнения. Раньше я его делал рекурсивно (что просто и интуитивно понятно), но на это раз решил построить постфиксное дерево алгоритмом сортировочной станции. Преимущество его в том, что вычисляется выражение просто перебором узлов в цикле (в режиме интерпретации, компилировать ещё не пробовал). Ну и самое главное - смог наконец реализовать неявное умножение, а аргументы функций писать без скобочек:
y = a sin x pi + b cos x pi
z = (a+b)(c+d)Эта часть тоже примерно 300 строк кода заняла, если не считать инфраструктуру для функций.
Разбор выражений - это только часть парсера. Действительно, надо хорошо подумать, как делать парсер.
Я вдохновился вашим шарпом, и накатал простейший лексер, который подключается вместо лексера sly. Как делать парсер - пока ещё не знаю.
А я наоборот, вдохновился вашим примером, и просто калькулятора на гиперкомплексных числах стало уже недостаточно) Когда все данные одного типа и нету массивов, циклов и вызовов определяемых пользователем функций - то всё намного проще. Самое сложное здесь это не сам парсер, а продуманная архитектура классов, в которую всё парсится.
Так, я не зря пропал со статьями на некоторое время :)
Я слегка упоролся, но всё же написал полностью рабочий парсер, который, к тому же, позволит мне слегка переделать синтаксис, поскольку тот синтаксис, который я хотел изначально, оказался не LR(1), и уж тем более не LALR(1). Полный парсер чуть больше сотни строк кода оказался.
https://github.com/ssloy/tinycompiler/blob/6f9752566ac4f6f1e62dfe47598081dc8b4394d8/earley.py
Надо его ещё отполировать-подрихтовать, и можно будет снова текст писать с описанием всего этого добра. Спасибо за толчок!
Компилятор за выходные: лексер и парсер