Прошло уже почти 30 лѣтъ послѣ публикацiи этой статьи. Ну и гдѣ это всё? Кажется, никто не пользуется этимъ методомъ для созданiя компиляторовъ новыхъ языковъ. У всѣхъ парсеры, intermediate representation и backend пишутся руками, а не генерируются изъ высокоуровневыхъ спецификацiй.
Было на эту тему нѣкое объясненiе - почему парсеры до сихъ поръ приходится дѣлатъ руками, а не генерировать автоматически. https://tratt.net/laurie/blog/2011/parsing_the_solved_problem_that_isnt.html А именно - грамматики трудно комбинировать (и значитъ трудно развивать языкъ), грамматики неоднозначны и съ этимъ трудно бороться.
Тулы не прижились: добавляют лишний уровень сложности. Автоматическая генерация большого количества кода приводит к неприятным проблемам в отладке. Но сама концепция ASDL оказалась полезной. К примеру, в книжке: https://vak.dreamwidth.org/1369172.html
> Автоматическая генерация большого количества кода приводит к неприятным проблемам в отладке.
Вотъ это очень интересно. Откуда берутся проблемы отладки кода?
Почему-то мы компилируемъ огромное количество софта изъ самыхъ разныхъ языковъ въ машинные коды или въ байтъ-коды (JVM, .NET), и это тоже "автоматическая генерацiя большого количества кода" - очень большого количества кода! - но это не приводитъ къ проблемамъ отладки.
А вѣдь отлаживать сгенерированный байтъ-кодъ или ассемблерный кодъ на порядокъ тяжелѣе, чѣмъ отлаживать, скажемъ, сгенерированный кодъ высокаго уровня на Java или С++.
Какъ же такъ получается, что мы генерируемъ мегабайтами и гигабайтами машинный кодъ, который потомъ практически невозможно будетъ отлаживать, и это насъ не смущаетъ. А генерировать гораздо меньшее количество кода высокаго уровня для парсинга, это почему-то проблематично.
Очевидно, тутъ есть какая-то коренная разница. Для языковъ высокаго уровня мы пользуемся отладчиками, которые показываютъ намъ проблемы на уровнѣ исходнаго кода. Мы сегодня больше не отлаживаемъ ассемблеръ или байтъ-коды.
Можетъ, дѣло въ томъ, что нужны особыя средства отладки, которыя работали бы прямо на уровнѣ декларативной грамматики, но такихъ отладчиковъ нѣтъ?
Есть разница между компиляцией процедурного кода (в процедурный же) и декларативного (в процедурный).
В первом случае мы знаем, что код выполняется как нами задумано, хоть и на другом языке (машинном коде). Зная в каком месте ошибка, нетрудно найти соответствие в исходном высокоуровневом коде.
В случае же декларативного языка мы часто понятия не имеем, как оно выполняется. И соответствие порождённого кода исходному может быть весьма отдалённым. Я неоднократно имел опыт отладки кода от YACC, и это малоприятное занятие. 😀
Но это всё объяснения, а медицинский факт тот, что активность вокруг asdlGen прекратилась двадцать лет назад. Очевидно, невостребовано.
Когда я писалъ кодъ на Скалѣ, мнѣ очень рѣдко нуженъ былъ отладчикъ. А вѣдь это JVM + JIT compiler, тамъ довольно трудно было бы найти соотвѣтствiе кода на Скалѣ и выполняемаго машиной кода. Но когда отладчикъ былъ нуженъ, то просто ставилъ breakpoint въ кодѣ и потомъ вычислялъ выраженiя и смотрѣлъ на текущiя значенiя аргументовъ и все. Почему то же самое нельзя сдѣлать для декларативныхъ грамматикъ?
Въ случаѣ YACC отвѣтъ можетъ быть въ томъ, что алгоритмъ LALR-парсинга генерируетъ нѣкiй сложный push-down автоматъ. Послѣ чего непонятно, какiе фрагменты кода этого автомата соотвѣтствуютъ грамматикѣ, и что дѣлать, если результатъ парсинга неправильный. Ошибки парсинга тоже тамъ очень плохо сообщаются, потому что алгоритмъ LALR хорошъ лишь для случаевъ, когда входной текстъ парсится безъ ошибокъ.
Замѣтимъ, что генерируемый YACC кодъ автомата никогда не вызоветъ сбоевъ типа segmentation fault, тамъ никогда не будетъ забыта иницiализацiя перемѣнныхъ. Тамъ не будетъ примитивныхъ ошибокъ. Ошибки будутъ болѣе высокаго уровня, на уровнѣ спецификацiи.
Можно ли было бы рѣшить проблемы съ YACC, если бы:
- Существовалъ бы отладчикъ, который показывалъ бы, гдѣ въ декларативной грамматикѣ "мы сейчасъ находимся" во время парсинга, - Если бы ошибки парсинга сообщались въ терминахъ декларативной грамматики, - Если бы никогда не было бы непонятныхъ "shift/reduce conflict", а проблемы декларативной грамматики сообщались бы пользователю въ терминахъ этой грамматики? ("входной текстъ XYZ неоднозначенъ изъ-за правилъ такихъ-то")
Есть нѣсколько декларативныхъ системъ, гдѣ вродѣ какъ нѣтъ такихъ проблемъ.
Первый основной примѣръ - синтаксисъ для ариѳметики. Мы пишемъ кодъ "a + b * c - d" и не задумываемся. Мы больше не пишемъ тестовъ для такого кода, чтобы провѣрить, что b * c было вычислено сперва, и лишь потомъ сумма; или что память была вовремя распредѣлена и освобождена; или что первый былъ плюсъ, а второй минусъ, а не наоборотъ. Мы не отлаживаемъ такой кодъ, мы не ставимъ тамъ breakpoint и не дѣлаемъ логи. Такой кодъ просто очевидно работаетъ и все. Мы уже привыкли, что это такъ во всѣхъ языкахъ. Но это было не всегда такъ. Это на самомъ дѣлѣ всеобъемлющая декларативная система для ариѳметики. Она порождаетъ ассемблерный кодъ или байтъ-кодъ, который не всегда прямо соотвѣтствуетъ написанному декларативному коду. Но это не вызываетъ почему-то проблемъ.
Второй примѣръ - языкъ SQL. Тамъ пишется декларативный кодъ "select blah from foo where bar = qux" и дальше это конвертируется очень сложнымъ образомъ въ "планы запросовъ" (query plan), индексированiе и т.д. Но мы никогда не отлаживаемъ такой кодъ путемъ декомпилированiя. Почему-то это не требуется.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
vak
no subject
Date: 2025-03-31 07:48 (UTC)Прошло уже почти 30 лѣтъ послѣ публикацiи этой статьи. Ну и гдѣ это всё? Кажется, никто не пользуется этимъ методомъ для созданiя компиляторовъ новыхъ языковъ. У всѣхъ парсеры, intermediate representation и backend пишутся руками, а не генерируются изъ высокоуровневыхъ спецификацiй.
Было на эту тему нѣкое объясненiе - почему парсеры до сихъ поръ приходится дѣлатъ руками, а не генерировать автоматически.
https://tratt.net/laurie/blog/2011/parsing_the_solved_problem_that_isnt.html
А именно - грамматики трудно комбинировать (и значитъ трудно развивать языкъ), грамматики неоднозначны и съ этимъ трудно бороться.
Предлагалось такое рѣшенiе - научиться парсить любую контекстно-свободную грамматику
https://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2012/08/the-solved-problem-that-isnt-is.html
Опять-таки, не вижу широкаго примѣненiя этому.
no subject
Date: 2025-03-31 18:44 (UTC)https://github.com/plgeek/asdlGen
Тулы не прижились: добавляют лишний уровень сложности. Автоматическая генерация большого количества кода приводит к неприятным проблемам в отладке. Но сама концепция ASDL оказалась полезной. К примеру, в книжке: https://vak.dreamwidth.org/1369172.html
no subject
Date: 2025-04-01 07:42 (UTC)Вотъ это очень интересно. Откуда берутся проблемы отладки кода?
Почему-то мы компилируемъ огромное количество софта изъ самыхъ разныхъ языковъ въ машинные коды или въ байтъ-коды (JVM, .NET), и это тоже "автоматическая генерацiя большого количества кода" - очень большого количества кода! - но это не приводитъ къ проблемамъ отладки.
А вѣдь отлаживать сгенерированный байтъ-кодъ или ассемблерный кодъ на порядокъ тяжелѣе, чѣмъ отлаживать, скажемъ, сгенерированный кодъ высокаго уровня на Java или С++.
Какъ же такъ получается, что мы генерируемъ мегабайтами и гигабайтами машинный кодъ, который потомъ практически невозможно будетъ отлаживать, и это насъ не смущаетъ. А генерировать гораздо меньшее количество кода высокаго уровня для парсинга, это почему-то проблематично.
Очевидно, тутъ есть какая-то коренная разница. Для языковъ высокаго уровня мы пользуемся отладчиками, которые показываютъ намъ проблемы на уровнѣ исходнаго кода. Мы сегодня больше не отлаживаемъ ассемблеръ или байтъ-коды.
Можетъ, дѣло въ томъ, что нужны особыя средства отладки, которыя работали бы прямо на уровнѣ декларативной грамматики, но такихъ отладчиковъ нѣтъ?
no subject
Date: 2025-04-01 20:59 (UTC)В первом случае мы знаем, что код выполняется как нами задумано, хоть и на другом языке (машинном коде). Зная в каком месте ошибка, нетрудно найти соответствие в исходном высокоуровневом коде.
В случае же декларативного языка мы часто понятия не имеем, как оно выполняется. И соответствие порождённого кода исходному может быть весьма отдалённым. Я неоднократно имел опыт отладки кода от YACC, и это малоприятное занятие. 😀
Но это всё объяснения, а медицинский факт тот, что активность вокруг asdlGen прекратилась двадцать лет назад. Очевидно, невостребовано.
no subject
Date: 2025-04-02 07:10 (UTC)Въ случаѣ YACC отвѣтъ можетъ быть въ томъ, что алгоритмъ LALR-парсинга генерируетъ нѣкiй сложный push-down автоматъ. Послѣ чего непонятно, какiе фрагменты кода этого автомата соотвѣтствуютъ грамматикѣ, и что дѣлать, если результатъ парсинга неправильный. Ошибки парсинга тоже тамъ очень плохо сообщаются, потому что алгоритмъ LALR хорошъ лишь для случаевъ, когда входной текстъ парсится безъ ошибокъ.
Замѣтимъ, что генерируемый YACC кодъ автомата никогда не вызоветъ сбоевъ типа segmentation fault, тамъ никогда не будетъ забыта иницiализацiя перемѣнныхъ. Тамъ не будетъ примитивныхъ ошибокъ. Ошибки будутъ болѣе высокаго уровня, на уровнѣ спецификацiи.
Можно ли было бы рѣшить проблемы съ YACC, если бы:
- Существовалъ бы отладчикъ, который показывалъ бы, гдѣ въ декларативной грамматикѣ "мы сейчасъ находимся" во время парсинга,
- Если бы ошибки парсинга сообщались въ терминахъ декларативной грамматики,
- Если бы никогда не было бы непонятныхъ "shift/reduce conflict", а проблемы декларативной грамматики сообщались бы пользователю въ терминахъ этой грамматики? ("входной текстъ XYZ неоднозначенъ изъ-за правилъ такихъ-то")
no subject
Date: 2025-04-03 07:40 (UTC)Первый основной примѣръ - синтаксисъ для ариѳметики. Мы пишемъ кодъ "a + b * c - d" и не задумываемся. Мы больше не пишемъ тестовъ для такого кода, чтобы провѣрить, что b * c было вычислено сперва, и лишь потомъ сумма; или что память была вовремя распредѣлена и освобождена; или что первый былъ плюсъ, а второй минусъ, а не наоборотъ. Мы не отлаживаемъ такой кодъ, мы не ставимъ тамъ breakpoint и не дѣлаемъ логи. Такой кодъ просто очевидно работаетъ и все. Мы уже привыкли, что это такъ во всѣхъ языкахъ. Но это было не всегда такъ. Это на самомъ дѣлѣ всеобъемлющая декларативная система для ариѳметики. Она порождаетъ ассемблерный кодъ или байтъ-кодъ, который не всегда прямо соотвѣтствуетъ написанному декларативному коду. Но это не вызываетъ почему-то проблемъ.
Второй примѣръ - языкъ SQL. Тамъ пишется декларативный кодъ "select blah from foo where bar = qux" и дальше это конвертируется очень сложнымъ образомъ въ "планы запросовъ" (query plan), индексированiе и т.д. Но мы никогда не отлаживаемъ такой кодъ путемъ декомпилированiя. Почему-то это не требуется.