на сайте RSDN есть статьи:
https://rsdn.org/article/alg/nka.xml

Автор(ы): Сергей Холодилов
Дата: 30.07.2007
В статье описан маленький, но всё равно интересный кусочек теории вычислений. Предназначение статьи – послужить наживкой, заглотив которую, читатели уже сами продолжат изучение этой теории.

https://rsdn.org/article/alg/regular.xml

Автор(ы): Михаил Купаев

к сожалению, они описывает простые регулярные выражения.

А ещё бывают регулярные выражения с операциями пересечения ^ и отрицания !

Цитируя википедию

generalized regular expression denotes a possibly infinite set of finite-length strings of symbols from A. It may be built of:

∅ (denoting the empty set of strings),
ε (denoting the singleton set containing just the empty string),
a symbol a from A (denoting the singleton set containing the single-symbol string a),
R∨S (where R and S are, in turn, generalized regular expressions; denoting their set's union),
R∧S (denoting the intersection of R 's and S 's set),
¬R (denoting the complement of R 's set with respect to the set of all strings of symbols from A),
RS (denoting the set of all possible concatenations of strings from R 's and S 's set),
R* (denoting the set of n-fold repetitions of strings from R 's set, for any n≥0, including the empty string).

In an ordinary regular expression, neither ∧ nor ¬ is allowed.

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

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

AS>Ну вот, нижайше прошу написать статью по нормальным регулярным выражениям, а не по ущербным, как сейчас.
AS>Англоязычный мир сделал это в 1964 году, пора немного сократить отставание.
Как человек написавший движок ДКА который умеет объединять N ДКА при помощи любой N'арной булевой функции могу сказать, что:
1)Пересечение автоматов не нужно. Не знаю ни одного жизненного примера.
2)А отрицание откровенно вредно. У людей крышу сносит. Я его сначала добавил, а потом убрал. Ибо люди путались и бред писали.
3)Более полезно на практике оказалось вычитание автоматов.
В выражении NotEscs из всего множества не пустых строк вычитаются все строки, которые содержат кавычки, символ начала специальной последовательности и переводы строк.

    [SpanClass(String)]
    token StringLiteral1 = Quote StringPart* Quote
    {
      regex Quote   = '\"';
      regex Esc     = '\\' (Quote | EscChar);
      regex Escs    = Esc+;
      regex NotEscs = Any+ - (Any* (Quote | '\\' | NewLine) Any*);

      token StringPart
      {
        | Escs;
        | NotEscs;
      }
    }

WH> написавший движок ДКА который умеет объединять N ДКА при помощи любой N'арной булевой функции

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

WH> полезно на практике оказалось вычитание автоматов

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

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


AS>А ещё бывают регулярные выражения с операциями пересечения ^ и отрицания !
А еще бывают с просмотром вперед-назад и с условиями ))

AS>>А ещё бывают регулярные выражения с операциями пересечения ^ и отрицания !
S>А еще бывают с просмотром вперед-назад и с условиями ))

Специально для тебя скажу, что ещё бывают контекстно-свободные грамматики.
Ты ведь наверняка этого не знаешь и тебе будет интересно!
А я знаю! Знаю! и горю желанием тебя просветить. Вот какой я умный!

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

AS>>А ещё бывают регулярные выражения с операциями пересечения ^ и отрицания !
S>А еще бывают с просмотром вперед-назад и с условиями ))
Не бывают. Просто по определению регулярных выражений.

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


AS>>>А ещё бывают регулярные выражения с операциями пересечения ^ и отрицания !
S>>А еще бывают с просмотром вперед-назад и с условиями ))
WH>Не бывают. Просто по определению регулярных выражений.
Ага

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

AS>>>>А ещё бывают регулярные выражения с операциями пересечения ^ и отрицания !
S>>>А еще бывают с просмотром вперед-назад и с условиями ))
WH>>Не бывают. Просто по определению регулярных выражений.
S>Ага

То, что ты показываешь, относится к разнообразным видам так называемых _extended_ regular expressions, которые включили кучу фич, которые в "обычных" регулярных выражениях не водятся.
Например, там есть возможность сослаться на ранее матченое через \n, где n — число.
Введение этих фич сбило понятие регулярных выражений до грамматики, которая никак не регулярная по классикам вроде Хомского.

Я не знаю, кому тут отдать предпочтение в этом споре, особенно после того, как коллега Wolfhound проехался супертанком по всем теоретикам темы грамматик — если "драконщина" было самым мягким из терминов, то и иерархия Хомского для него никак не образец. Но в любом случае спор не по сути.

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

N>Введение этих фич сбило понятие регулярных выражений до грамматики, которая никак не регулярная по классикам вроде Хомского.
А что в данном вопросе есть другие классики?

N>Я не знаю, кому тут отдать предпочтение в этом споре, особенно после того, как коллега Wolfhound проехался супертанком по всем теоретикам темы грамматик — если "драконщина" было самым мягким из терминов, то и иерархия Хомского для него никак не образец. Но в любом случае спор не по сути.
Ты вообще ничего не понял из того что я говорил.
Моя претензия к книге дракона в том, что там куча убогих и в то же время сложных алгоритмов. И нет простых и качественных. Ибо по ним статьи в научные журналы писать нельзя. Тк там всё просто.
Например, где в книге дракона Top down operator precedence? А ведь это работа 1973 года. И это при том что это лучший алгоритм для разбора языков программирования. Собственно, нитра и построена вокруг TDOP посыпанного сахаром.

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

WH>Моя претензия к книге дракона в том, что там куча убогих и в то же время сложных алгоритмов.

Нет там никакой кучи алгоритмов, ты не читал ни один из 3-х "драконов", вестимо.
Эта книга о принципах построения компиляторов, т.е. об их архитектуре, а не о конкретных алгоритмах.
Одна из самых важных глав в каждом издании "дракона" — это про синтаксически управляемую трансляцию.
Это просто принцип и вся книга написана ради этой главы, собсно.
А в кач-ве алгоритмов лексера и парсера взяты наиболее общие алгоритмы в минимальном их кол-ве.


WH>И нет простых и качественных.

У Ахо полно публикаций по конкретным алгоритмам, на которых сейчас живет всё современное IT.
В общем, мухи отдельно, котлеты отдельно.


WH>Например, где в книге дракона Top down operator precedence? А ведь это работа 1973 года.

В этой книге много еще чего нет, потому что дракон не об этом совершенно.

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

WH>>Например, где в книге дракона Top down operator precedence? А ведь это работа 1973 года.
V>В этой книге много еще чего нет, потому что дракон не об этом совершенно.
Нет самого практичного алгоритма разбора языков программирования. Следовательно, это книга не про то как писать компиляторы, а про чёрт знает что. Собственно, из-за этого нельзя взять дракона и написать по нему нормальный компилятор.

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

WH>>>Например, где в книге дракона Top down operator precedence? А ведь это работа 1973 года.
V>>В этой книге много еще чего нет, потому что дракон не об этом совершенно.
WH>Нет самого практичного алгоритма разбора языков программирования. Следовательно, это книга не про то как писать компиляторы, а про чёрт знает что. Собственно, из-за этого нельзя взять дракона и написать по нему нормальный компилятор.

Чтой-то как смотришь в реальные примеры (чего-то активно используемого) — так куда ни плюнь, везде самописный нисходящий парсер.
В книге дракона такой парсер есть, глава 2.
Значит, писать по нему нормальный компилятор можно
Q.E.D.

А по поводу TDOP — это, конечно, очень вкусный вариант, но по сути это всего лишь событийно-управляемое таблично-организованное представление нисходящего рекурсивного парсера
Из идеи вида "надо обобщить код разбора, сведя выбор хэндлера в таблицу" выводится просто на один чих. Не умаляю Пратта, для 1973 идея гениальная, но для сейчас ничего особого в этом нет.

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

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

WH>>>Например, где в книге дракона Top down operator precedence? А ведь это работа 1973 года.
V>>В этой книге много еще чего нет, потому что дракон не об этом совершенно.
WH>Нет самого практичного алгоритма разбора языков программирования. Следовательно, это книга не про то как писать компиляторы, а про чёрт знает что. Собственно, из-за этого нельзя взять дракона и написать по нему нормальный компилятор.

Я ХЗ чего ты упираешься.
Дракон не запрещает взять любой алгоритм лексического или синтаксического анализа и написать компилятор.
Потому что книга эта не об алгоритмах парсинга грамматик, а о применении этих алгоритмов в компиляторостроении.
Плохо верится, что эту принципиальную разницу ты не видишь в упор.

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

N>Чтой-то как смотришь в реальные примеры (чего-то активно используемого) — так куда ни плюнь, везде самописный нисходящий парсер.
А это по тому что про TDOP никто даже не слышал.
Просто сравни размер статьи в википедии.
https://en.wikipedia.org/wiki/Pratt_parser
https://en.wikipedia.org/wiki/LALR_parser
И это при том что LALR бесполезен.
А всё по тому что про LALR написано в книге дракона. И про книгу дракона усиленно распространяется миф что там написано про всё что нужно знать про построение компиляторов.

N>В книге дракона такой парсер есть, глава 2.
N>Значит, писать по нему нормальный компилятор можно
N>Q.E.D.
На брейнфаке тоже можно любую программу написать.

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

N>>Чтой-то как смотришь в реальные примеры (чего-то активно используемого) — так куда ни плюнь, везде самописный нисходящий парсер.
WH>А это по тому что про TDOP никто даже не слышал.
WH>Просто сравни размер статьи в википедии.
WH>https://en.wikipedia.org/wiki/Pratt_parser
WH>https://en.wikipedia.org/wiki/LALR_parser
WH>И это при том что LALR бесполезен.

$ find /usr/src/ | grep '\.y$' | fgrep -v /test/ | wc -l
     84

Это freebsd base sources. При том, что там не bison, а byacc, и у него чистый LALR(1) без вариантов. Так кто кому более бесполезен? С LALR мы имеем универсальный механизм, пригодный для реализации и сопровождения, с минимумом умственных вложений в тему грамматики (автор кода пишет по сути только свои хэндлеры), и ещё и встроенную проверку корректности грамматики (что критически важно для тех, кто )
Только не надо про нитру вспоминать — за пределами вашей песочницы про неё не слышно.

WH>А всё по тому что про LALR написано в книге дракона. И про книгу дракона усиленно распространяется миф что там написано про всё что нужно знать про построение компиляторов.

Так борись с этим мифом. С тем, что до определённого уровня пишут на LALR(1)-bound средствах, а затем вдруг резко переходят на самописку. Может, тому есть серьёзные причины?

Или хотя бы выложи (на двух языках) красивое описание TDOP без всех этих null denotation, которые сводят с ума при первом чтении. (Я знаю, что такие статьи уже есть. Но их мало.)

В ваших условиях ты мог бы запросто переломить это выкладыванием статьи на хабр. Дёшево и эффективно. А то сейчас даже для классического TDOP есть только простой сухой перевод Крокфорда.

N>>В книге дракона такой парсер есть, глава 2.
N>>Значит, писать по нему нормальный компилятор можно
N>>Q.E.D.
WH>На брейнфаке тоже можно любую программу написать.

На брейнфаке не пишут промышленные компиляторы. А на ручной самописке их полно (не буду вспоминать C++ с его тараканами в пол-неба, но C# и Go уже показательны).

Тебе, по-моему, все уже говорили, что дело не в академическом снобизме или в чём-то подобном, но твои разработки нужно переложить на что-то более пригодное к download-and-go.

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

WH>>>Например, где в книге дракона Top down operator precedence? А ведь это работа 1973 года.
V>>В этой книге много еще чего нет, потому что дракон не об этом совершенно.
WH>Нет самого практичного алгоритма разбора языков программирования. Следовательно, это книга не про то как писать компиляторы, а про чёрт знает что. Собственно, из-за этого нельзя взять дракона и написать по нему нормальный компилятор.

Что значит "самый практичный" ? Какой смысл ты в это вкладываешь ?

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

N>С LALR мы имеем универсальный механизм, пригодный для реализации и сопровождения, с минимумом умственных вложений в тему грамматики (автор кода пишет по сути только свои хэндлеры), и ещё и встроенную проверку корректности грамматики (что критически важно для тех, кто )
Это просто не правда.
Там шаг в сторону и привет. Айда грамматику переписывать. А чтобы её переписать нужно знать, как этот самый LALR работает.

N>Так борись с этим мифом. С тем, что до определённого уровня пишут на LALR(1)-bound средствах, а затем вдруг резко переходят на самописку. Может, тому есть серьёзные причины?
Так во всех институтах всем студентам этот LALR вдалбывают. Вот люди и думают, что ничего другого нет.
Но как только люди заходят достаточно далеко они понимают какое LALR говно.
И вынуждены начинать писать парсер руками. А тупой рекурсивный спуск единственное что можно написать руками если не знать про TDOP.

N>Тебе, по-моему, все уже говорили, что дело не в академическом снобизме или в чём-то подобном, но твои разработки нужно переложить на что-то более пригодное к download-and-go.
Я тут вообще не про мои разработки говорю. Я говорю про алгоритм, который старше меня.

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

N>>Чтой-то как смотришь в реальные примеры (чего-то активно используемого) — так куда ни плюнь, везде самописный нисходящий парсер.
WH>А это по тому что про TDOP никто даже не слышал.
WH>Просто сравни размер статьи в википедии.
WH>https://en.wikipedia.org/wiki/Pratt_parser
WH>https://en.wikipedia.org/wiki/LALR_parser
WH>И это при том что LALR бесполезен.
WH>А всё по тому что про LALR написано в книге дракона. И про книгу дракона усиленно распространяется миф что там написано про всё что нужно знать про построение компиляторов.

Это же чистой воды конспироложество. У тебя "написано в книге дракона" это эдакое универсальное объяснение для всего, с чем ты не согласен. Эдакий заговор против тебя и TDOP со стороны гражданина Ахо.

Скажем, я начинал безо всякого дракона — почитал Вирта. Вирт, по твоему, тоже драконом зомбирован ?

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

I>Это же чистой воды конспироложество. У тебя "написано в книге дракона" это эдакое универсальное объяснение для всего, с чем ты не согласен.
Наоборот. Я говорю, что книга дракона плохая по тому что там написано то с чем я не согласен.
И ещё хуже то что её всем впаривают как образец для подражания.

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

N>>С LALR мы имеем универсальный механизм, пригодный для реализации и сопровождения, с минимумом умственных вложений в тему грамматики (автор кода пишет по сути только свои хэндлеры), и ещё и встроенную проверку корректности грамматики (что критически важно для тех, кто )
WH>Это просто не правда.
WH>Там шаг в сторону и привет. Айда грамматику переписывать. А чтобы её переписать нужно знать, как этот самый LALR работает.

Для того, чтобы на нём сделать грамматику, нужно полдесятка простых правил. Разумеется, если не пытаться впрячь лебедя, рака и щуку, как сделали в C++.
Из названных мной 84 большинство этих грамматик просты, как угол дома. И, при этом, тотально декларативны, что скорее в плюс — хотя бы потому, что TDOP жёстко привязывает код парсинга, а BNF-like декларации с привешенным к ним кодом универсально ложатся под любой генератор парсера.

А вот то, что было бы полезно, так это подходы, как не впасть при расширении грамматики в ту же позу, куда попал C++. Но TDOP это тоже не решает, и Nitra не решает.

N>>Так борись с этим мифом. С тем, что до определённого уровня пишут на LALR(1)-bound средствах, а затем вдруг резко переходят на самописку. Может, тому есть серьёзные причины?
WH>Так во всех институтах всем студентам этот LALR вдалбывают. Вот люди и думают, что ничего другого нет.

"Во всех институтах" "вдалбывают" одновременно LL и LR. С разным набором специализаций, понятно, но дают оба.

WH>Но как только люди заходят достаточно далеко они понимают какое LALR говно.
WH>И вынуждены начинать писать парсер руками. А тупой рекурсивный спуск единственное что можно написать руками если не знать про TDOP.

Я знаю про TDOP, хотя никогда не зарабатывал написанием компиляторов. А те, кто всерьёз занялся, способны хотя бы пролистать список методов в википедии. Поэтому все, кому надо, давно про него знают. И если не используют, то причина не в LALR.

N>>Тебе, по-моему, все уже говорили, что дело не в академическом снобизме или в чём-то подобном, но твои разработки нужно переложить на что-то более пригодное к download-and-go.
WH>Я тут вообще не про мои разработки говорю. Я говорю про алгоритм, который старше меня.

OK, можно сократить тему только до TDOP. Но в таком случае она сильно пострадает. Насколько я успел увидеть в нитре, у тебя таки описательный подход, а TDOP требует руками выписывать код всех nud/led/etc.