Re: Написание своего DSL - Компьютерные священные войны

Здравствуйте!

Точнее — парсинг и построение AST

Запилил статейку на эту тему со своими практиками, предлагаю обсудить. Но — с конструктивом, а не просто: "ты лошара неграмотная, я тебя на работу не возьму". Хочу понять, как таки это делать правильно и быстро.

M> не просто: "ты лошара неграмотная

Только Java, только Antlr

Здравствуйте, Эйнсток Файр, Вы писали:

M>> не просто: "ты лошара неграмотная

ЭФ>Только Java, только Antlr

Он умеет строить AST за тебя? Плюшечный построить сможет?

M> Он умеет строить AST за тебя?
https://stackoverflow.com/questions/29971097/how-to-create-ast-with-antlr4

M> Плюшечный построить сможет?
https://github.com/antlr/antlr4/blob/master/doc/cpp-target.md

Здравствуйте, Marty, Вы писали:

M>Здравствуйте!

M>Точнее — парсинг и построение AST

M>Запилил статейку на эту тему со своими практиками, предлагаю обсудить. Но — с конструктивом, а не просто: "ты лошара неграмотная, я тебя на работу не возьму". Хочу понять, как таки это делать правильно и быстро.

Это очень зависит.
Нынешняя практика парсинга опирается на Хомского, дегенераивные грамматики и позиционные языки, похожие на английский.
Я в моей практике (не очень сложных парсеров) пришёл к противоположной методике.
Каждое слово языка имеет тэг. Первый символ (несколько символов) любой переменной — это тэг.
И этот тэг определяет в какой массив и какую структуру AST ты его записываешь.

Таким образом любой парсер пишется вот так:

   for( int i=0 ; i<n_Word ; i++ )
   {  switch( Word[i][0] )
      {
         case '$' : AllData.Array1[j1++]                  = func1( Word[i] ) ; break ;
         case '@' : AllData.Array2[j2++]                  = func2( Word[i] ) ; break ;
         case '&' : AllData.Array2[j2].Member[j_Member++] = func3( Word[i] ) ; break ;
      }
   }

Вместо [j_Mass1++] можешь push_back() писать.

И да, для этого надо иметь возможность самому создавать свой DSL, чтобы самому назначать тэги.

PS.
Вот тут один персонаж (еретик) рассказывает про подобную методику. Только он ещё "иероглифы" (это такие своеобразные тэги) делает:

https://youtu.be/LxMj6ZYfbpU?t=898

Здравствуйте, alpha21264, Вы писали:

A>Это очень зависит.
A>Нынешняя практика парсинга опирается на Хомского, дегенераивные грамматики и позиционные языки, похожие на английский.

Блин, старика Хомского не читал. А если и читал, то забыл

A>Я в моей практике (не очень сложных парсеров) пришёл к противоположной методике.
A>Каждое слово языка имеет тэг. Первый символ (несколько символов) любой переменной — это тэг.

Когда свой язык — ещё ладно, можно.
Когда чужой — уже никак.

Мне интересно, есть ли та волшебная пуля, которая за меня построит AST, опиши я язык в BNF или ещё каком виде.

Или вся эта шляпа с LL(X)/LR(X)б контекстно свободными/зависимыми грамматиками — просто псевдонаучно обоснованный развод для лохов, чтобы платили за то, что им вливают в уши?

Баксами, к слову, я тоже пользуюсь

Пример моего DSL

#!rdlc

$typedef u8 : bool

$include "sample_types.rdl"


$device "battery" - Батарейка

        $import "Motherboard" from <volk.rdl> as VolkMotherboard prefix vlk_

    $namespace rw

        power_off         : u8
        user_output_state : u8

    ro:
        
        $group "Напряжения"
        voltage_millivolts\
         : u16 \
         - "общее напряжение на выходе"
        cell_1_millivolts  : u16
        cell_2_millivolts  : u16
        cell_3_millivolts  : u16
        cell_4_millivolts  : u16 - "на самом деле этой ячейки тут нет, она оставлена для совместимости номеров регистров с другими батарейками"
        
        charge_percent                     : u8
        run_time_to_empty_minutes_u16      : u16 - "предполагаемое время работы на основе текущих данных"
        average_time_to_empty_minutes_u16  : u16 - "предполагаемое время работы на основе среднего тока"
        average_time_to_full_minutes_u16   : u16 - "предполагаемое время до полной зарядки"

        safety_status_u32                 : u32 - "битовое поле, см. SafetyStatusBits ниже"
        pf_status_u32                     : u32 - "битовое поле, см. PfStatusBits ниже"
                                          
        temperature_decikelvin_u16        : u16 - "это 0.1 Кельвина"
                                          
        current_milliamp_s16              : s16
                                          
        cycle_count_u16                   : u16
        state_of_health_percent           : u8
                                          
        operation_status_u32              : u32 - "битовое поле, см. OperationStatusBits ниже"
                                          
        is_voltage_ok                     : bool
                                          
        user_input_state                  : bool
        custom_error                      : u8 - "битовое поле, см. CustomErrorBits ниже"

        $type [generator=cpp:struct] SafetyStatusBits : u, 32 - "Биты внутреннего регистра Safety Status"
        
             CELL_UNDERVOLTAGE                    : 1 << 0  
             CELL_OVERVOLTAGE                     : 1 << 1  
             OVERCURRENT_DURING_CHARGE_1          : 1 << 2  
             OVERCURRENT_DURING_CHARGE_2          : 1 << 3  
             OVERCURRENT_DURING_DISCHARGE_1       : 1 << 4  
             OVERCURRENT_DURING_DISCHARGE_2       : 1 << 5  
             OVERLOAD_DURING_DISCHARGE            : 1 << 6  
             OVERLOAD_DURING_DISCHARGE_LATCH      : 1 << 7  
             SHORT_CIRCUIT_DURING_CHARGE          : 1 << 8  
             SHORT_CIRCUIT_DURING_CHARGE_LATCH    : 1 << 9  
             SHORT_CIRCUIT_DURING_DISCHARGE       : 1 << 10 
             SHORT_CIRCUIT_DURING_DISCHARGE_LATCH : 1 << 11 
             OVERTEMPERATURE_DURING_CHARGE        : 1 << 12 
             OVERTEMPERATURE_DURING_DISCHARGE     : 1 << 13 
             CELL_UNDERVOLTAGE_COMPENSATED        : 1 << 14 

             OVERTEMPERATURE_FET                  : 1 << 16 

             PRECHARGE_TIMEOUT                    : 1 << 18 

             CHARGE_TIMEOUT                       : 1 << 20 

             OVERCHARGE                           : 1 << 22 
             OVERCHARGING_CURRENT                 : 1 << 23 
             OVERCHARGING_VOLTAGE                 : 1 << 24 
             OVER_PRECHARGE_CURRENT               : 1 << 25 
             UNDERTEMPERATURE_DURING_CHARGE       : 1 << 26 
             UNDERTEMPERATURE_DURING_DISCHARGE    : 1 << 27
        
        $end_type

        safetyStatusBits : SafetyStatusBits - "Status"

Пример (рабочий) на моём DSL из последнего. DSL изначально был рождён как построчный парсер инишки, потом, по мере взросления, фичи добавлялись. Но не по науке, а как пришлось. Зато первая версия заработала уже через пару-тройку дней.

Тема зашла, коллеги пишут генераторы кода по моему AST'у. Но front я тяну сам. В рукопашную. А хочется описать BNF и какая-то тулза всё сделает за меня. AST, в том числе.

A>PS.
A>Вот тут один персонаж (еретик) рассказывает про подобную методику. Только он ещё "иероглифы" (это такие своеобразные тэги) делает:

A>https://youtu.be/LxMj6ZYfbpU?t=898

Спс, посмотрю

A> Нынешняя практика парсинга опирается на Хомского, дегенераивные грамматики и позиционные языки

Это знания, полученные тобой 30 лет назад, опираются ...

А сейчас есть системы грамматик, покрывающие натуральные языки (со сложностью разбора O(N^6))
— вот это нынешняя практика.

Классический учебник по теме — https://www.springer.com/gp/book/9783642148453

Здравствуйте, Marty, Вы писали:

Я бы искал готовый инструмент

Здравствуйте, Marty, Вы писали:

Нафига в ЖЖ?

Ты бы еще в контактике запилил.

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Классический учебник по теме — https://www.springer.com/gp/book/9783642148453

Отбой, она платная. Я люблю только всё на безвозмедной основе.

Здравствуйте, Мёртвый Даун, Вы писали:

МД>Здравствуйте, Marty, Вы писали:

МД>Нафига в ЖЖ?

Ты бы еще в контактике запилил.

не, всё правильно, с таким:

А по факту — я наелся говна.

Но это так, не говно на самом деле.

Накушавшись говна с flex/bison, я потрогал ещё кучу разного.

там этому и место.

Здравствуйте, Marty, Вы писали:

M>Запилил статейку на эту тему со своими практиками, предлагаю обсудить. Но — с конструктивом, а не просто: "ты лошара неграмотная, я тебя на работу не возьму". Хочу понять, как таки это делать правильно и быстро.
Всегда писал разбор руками, методом рекурсивного спуска. Другие методы даже не пробовал. Ну крутил в руках всякие yacc и подобные, но не более. Обычно собственно разбор — это очень быстро по сравнению с остальной работой по использованию полученного AST.

Здравствуйте, Эйнсток Файр, Вы писали:

A>> Нынешняя практика парсинга опирается на Хомского, дегенераивные грамматики и позиционные языки

ЭФ>Это знания, полученные тобой 30 лет назад, опираются ...

Я говорю на современную практику, которую используют программисты. lex/yacc, GCC и всё такое.

ЭФ>А сейчас есть системы грамматик, покрывающие натуральные языки (со сложностью разбора O(N^6))
ЭФ>- вот это нынешняя практика.

Я не знаю, что такое "сложность разбора натурального языка O(N^6)".
Вообще, цифра 6 в скобочках после O() приводит меня в ужас.
Это что, действительно полином шестой степени?! А в чём польза?

ЭФ>Классический учебник по теме — https://www.springer.com/gp/book/9783642148453

А что там такого? Покупать книжку за 50 долларов, чтобы убедиться, что там лажа я не буду.
Это лучше или хуже, чем вот это? Тут вся грамматика английского языка умещается на одной странице:

https://www.youtube.com/watch?v=lqL45eVcGIg

И напоминаю — мы обсуждаем DSL. Натуральные языки — это совершенно другая тема.

Здравствуйте, Marty, Вы писали:

M>Запилил статейку на эту тему...
Вам не нужен DSL. Вам для кодогенерации нужен шаблонизатор и готовый скриптовый язык.
Из коробки в нормальных системах из коробки есть perl или доставляется php.
ps: лично я бы предпочел lua.

МД> Я люблю только всё на безвозмедной основе.

Ищи, в интернете есть пиратская, только по правилам форума RSDN на неё нельзя давать ссылку.

Здравствуйте, Рома Мик, Вы писали:

РМ>Всегда писал разбор руками, методом рекурсивного спуска. Другие методы даже не пробовал. Ну крутил в руках всякие yacc и подобные, но не более. Обычно собственно разбор — это очень быстро по сравнению с остальной работой по использованию полученного AST.

Ну совсем руками — это имхо перебор, но в целом — совершенно с тобой согласен

Здравствуйте, Marty, Вы писали:

M>Запилил статейку на эту тему со своими практиками, предлагаю обсудить. Но — с конструктивом, а не просто: "ты лошара неграмотная, я тебя на работу не возьму".

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

Делайте тупой построчный разбор. В 90 процентов случаев этого достаточно для DSL

На прочтение и освоение чего то вроде драконов нужно потратить пару недель один раз в жизни, коли уж с профильным образованием не срослось. После этого пугаться лексеров и парсеров не будешь.
Теперь про создание DSL в частности и языков в общем.
Главный критерий языка — удобство его использования человеком. Непонимание этого — одна из самых частых ошибок неопытных изобретателей языков. Начинать его проектирование нужно не с подбора технологий и алгоритмов, а с описания на нем реальных кейсов и коридорного тестирования результатов. При этом нужно включать зануду по полной — любое сомнение или шероховатость должно подвергаться нещадному анализу. А поскольку у тебя в этот момент еще ничего не написано — не будет возникать посознательного нежелания кардинально все менять.
Когда ты этим позанимаешься определенный срок, хотя бы дней несколько — тебя начнет посещать дао. Ты немного по другому начнешь мыслить, не так как обычно при проектировании софта для решения определенных проблем.
В какой то момент твой язык в голове начнет превращаться во что то осязаемое и цельное. И именно здесь от тебя требуется по максимуму инженерный талант, то что отличает тебя от кучи сереньких кодеров. А так же хорошее знакомство с современными примерами удачных DSL, потому что некоторые красивые велосипеды не так то просто придумать с нуля.
Когда появится что то законченное — надо зафиксировать результат в любом понятном тебе виде.
Теперь можно написать ... нет, не код а тесты. Тесты для парсеров/компилеров обычно представляют собой коротенкий кусочек с одной фичей на исходном языке набор голдов, т.е. дампов промежуточных и конечных структур — разных стадий AST и конечного кода или исходников. Результат этого этапа — это самое ценное и сложное, что нужно сделать при разработке DSL.
Ну а дальше остается только реализовать это — написать парсер, генератор, компилятор, интерпретатор или что там тебе нужно. На этом этапе можно слегка подрихтовать грамматику, чтобы не создавать лишних сложностей, например чтобы запихнуть ее в LL(1). Пишешь ли ты руками или используешь генераторы лексеров/парсеров при этом — совершенно не принципиально. Разница в скорости реализации обычно десяток-другой человекодней.

... << RSDN@Home 1.3.17 alpha 5 rev. 62>>

Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>Только Java, только Antlr

antlr это не только java

... << RSDN@Home 1.3.17 alpha 5 rev. 62>>

Здравствуйте, Marty, Вы писали:

M>Он умеет строить AST за тебя?

Этот — умеет. Но, имхо, лучше руками.

... << RSDN@Home 1.3.17 alpha 5 rev. 62>>

Здравствуйте, Ночной Смотрящий, Вы писали:

НС>Здравствуйте, Эйнсток Файр, Вы писали:

ЭФ>>Только Java, только Antlr

НС>antlr это не только java

Я его трогал, тогда была только джава. Но это было давно, да

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	09.09.20 20:49
Оценка:	2 (2) +1 -2

От:	Эйнсток Файр	Странный реагент
Дата:	09.09.20 21:00
Оценка:	+1 -2

От:	Marty	https://www.youtube.com/channel/UChp5PpQ6T4-93HbNF-8vSYg
Дата:	09.09.20 21:02
Оценка:

От:	Эйнсток Файр	Странный реагент
Дата:	09.09.20 21:04
Оценка:

	От:	alpha21264
	Дата:	09.09.20 21:18
	Оценка:	2 (1)

	От:	Мёртвый Даун
	Дата:	10.09.20 08:35
	Оценка:	-1

От:	Рома Мик	http://romamik.com
Дата:	10.09.20 10:15
Оценка:	+1

	От:	Ночной Смотрящий
	Дата:	10.09.20 20:28
	Оценка:	2 (1) +2