Sup, /pr/. Пишу свой генератор парсеров на базе parsing expressions. И у меня возникла проблема: как разрешать левую рекурсию?Что у меня есть сейчас: DSL для описания грамматик, я могу его распарсить и построить по нему AST, могу пидорасить это AST, как угодно, могу построить по этому AST простенький recursive-descent parser.В принципе, мне этого уже хватает, но хочу сделать еще удобнее: в частности, я не хочу разруливать сам левую рекурсию. То есть, я хочу записать что-то такое:[code]expr <- expr '+' expr [priority 10] / expr '' expr [priority 20] / number ;[/code]А мой генератор чтоб сам преобразовывал его во что-нибудь такое:[code]expr <- expr1 ('+' expr1)+ / expr1 ;expr1 <- expr2 ('' expr2)+ / expr2 ;expr3 <- number ;[/code]Проблема в том, что это очень частный случай левой рекурсии. Это самое expr может быть зарыто еще в десятке правил, которые вызываются в самом expr. Так вот, как мне так перепидорасить AST моей грамматики? Или, может, генерируемый парсер как-то доработать (мемоизацию какую-нибудь прикрутить)?
>>760464 (OP)Бля, разметка проебалась. Вот, короче: https://spit.mixtape.moe/view/8f4601c1 .
>>760464 (OP)https://ru.wikipedia.org/wiki/Yacchttps://ru.wikipedia.org/wiki/Lex
>>760464 (OP)Дрэгонбук тебе в помощь, там все написано.https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%B8%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D1%8B:_%D0%BF%D1%80%D0%B8%D0%BD%D1%86%D0%B8%D0%BF%D1%8B,_%D1%82%D0%B5%D1%85%D0%BD%D0%BE%D0%BB%D0%BE%D0%B3%D0%B8%D0%B8_%D0%B8_%D0%B8%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%BC%D0%B5%D0%BD%D1%82%D1%8B
>>760473>>760509А вот и боты подтянулись. Но все равно отвечку.> parsing expressions> recursive-descent
>>760464 (OP)Первая ссылка из гугла: https://github.com/orlandohill/peg-left-recursion
Лавир младший?
>>760761Почитал. По сути, он предлагает преобразовывать `A <- A a / B` в `A <- B a`. Я примерно это же и думал делать. Но это как-то паскудно выглядит, алсо, я не разобрался с областями видимости в семантических действиях. `A <- A a { do_this } / B { do_that }` преобразовывается в `A <- (B a { ??? }`. Или мне надо просто отдохнуть и врубиться еще раз.
>>760831Да блин!A <- A a / B преобразовывать в A <- B a star.A <- A a { do_this } / B { do_that } преобразовывать в A <- B (a { ??? }) star.
>>760545Дегенерат, еще в старом издании дрэгонбука все написано и про рекурсивный спуск, и про разрешение этой твоей левой рекурсии. Но зачем тебе книги - лучше на двоще покрасоваться, пусть пионэры поахают.
>>760866О, точно! И там тоже самое написано. Значит, я движусь в верном направлении.Только там не написано, как быть с контекстами в семантических действиях. Я хочу, чтоб все куски кода вот здесь выполнялись в одном скоупе:expr = expr '+' expr { piece1 } / expr 'x' expr { piece2 } / number ;И там вроде не написано про левую и правую ассоциативность, но это уже тривиально делается.
>>760913>expr = expr '+' expr { piece1 } / expr 'x' expr { piece2 } / numberЗапиши нормально в ABNF грамматику, не понимаю твою писанину.
>>761089expr = expr "+" expr / expr "x" expr / 1DIGIT ;Это без семантических действий. А вот с семантическими действиями:expr = expr "+" expr { do_this } / expr "x" expr { do_that } / 1DIGIT ;
>>761093Ну блядство же!expr = expr "+" expr / expr "x" expr / 1✱ DIGIT ;Это без семантических действий. А вот с семантическими действиями:expr = expr "+" expr { do_this } / expr "x" expr { do_that } / 1✱ DIGIT ;
>>761094Твои ололо семантические действия относятся уже не к грамматике, а к узлу оператора в дереве разбора, полученном грамматикой из входящего текста. Или у тебя полная каша в голове, или ты не умеешь выражать свои мысли.Чтобы избавиться от левой рекурсии, тебе нужно ввести новые нетерминалы expr1, которые не будут начинаться с expr, а также воспользоваться эпсилон-продукцией eps:expr = digit expr1expr1 = "+" expr / "x" expr / epsdigit = 1 * DIGITЯ ответил на твой вопрос?
>>761111Ебучая макаба, * = звезда.
>>760464 (OP)Можно ещё перевести леволинейную грамматику в праволинейную грамматику через диаграмму состояний, тогда ты избавишься от левой рекурсии вообще.
>>761111Я то же самое и написал.И что ты предлагаешь с семантическими действиями делать? А, хотя я понял, это уже определяется реализацией. Надо подумать будет.>>761172По-подробней?
>>761560>Я то же самое и написал.Ни одной эпсилон-продукции у тебя не заметил.>И что ты предлагаешь с семантическими действиями делать?У тебя так и не вышло объяснить суть проблемы, которая с ними возникает.
>>761795> Ни одной эпсилон-продукции у тебя не заметил.Я дополнительно избавился от эпсилон-продукций. Какие эпсилон-продукции в PEG, поехавший?> У тебя так и не вышло объяснить суть проблемы, которая с ними возникает. Я хочу, чтобы все семантические действия, указанные в правиле, выполнялись в одном и том же контексте и ровно в тот момент, когда парсер до них доходит по тексту.
GLR
>>761908>Какие эпсилон-продукции в PEG, поехавший?Самые что ни на есть обыкновенные, милорд.>Using the PEG formalism, the terminals (parsing expressions that do not depend on other expressions) are:>...>eps (short for 'epsilon') is an expression matching 'the empty char': it always succeeds and does not consume anything.Пруфлинк:https://github.com/PhilippeSigaud/Pegged/wiki/PEG-BasicsТы мало того что дурачок, так еще и дурачок агрессивный. Нехорошо это. Это ж у тебя, дауна, не получается с простейшими алгоритмами совладать, а еще других ботами да поехавшими кроешь. Стыдись!>Я хочу, чтобы все семантические действия, указанные в правиле, выполнялись в одном и том же контексте и ровно в тот момент, когда парсер до них доходит по тексту.Странное желание, с учетом того, что порядок правил в тексте никак не связан с порядком их применения. Зачем тебе тогда вообще нужен парсер? Напиши лексер и всего делов, порядок операторов в тексте - задача лексического анализатора, а не синтаксического. Кроме того, не вполне понятно, что в твоём случае входит в понятие "контекст".
>>762344> Какие эпсилон-продукции в PEG, поехавший?Знаешь, в теории ты и Анджелину Джоли трахаешь. В теории. А практика обычно прозаичнее. Как ты по правилам с эпсилон-продукциями построишь парсер, который не будет зависать? Нет, понятно, что построить можно, но это будет нетривиальный процесс.> Странное желание, с учетом того, что порядок правил в тексте никак не связан с порядком их применения.Что в этом странного? Хочу, например, логгировать парсинг каждого оператора сложения. Парсер распарсил "5+6" - отлоггировался. Потом отпарсил еще "...+1" - еще отлоггировался. Все просто же!> Кроме того, не вполне понятно, что в твоём случае входит в понятие "контекст". Область видимости переменных. Хочу, чтобы все переменные, которые объявляются в семантических действиях в пределах одного правила, находились в одной области видимости. А переменные другого правила - в другой, отдельной.
>>762496>понятно, что построить можно, но это будет нетривиальный процесс.Нетривиальность зависит от того, кто строит. Для тебя, к примеру, и без эпсилон-продукций процесс явно нетривиален. Кроме того, прекращай вертеть жопой, маня - только что ты говорил, цитирую:>Какие эпсилон-продукции в PEG, поехавший?Ты не говорил о проблемах реализации таких грамматик, ты утверждал именно факт отсутствия эпсилон-продукций в PEG, так что не визжи теперь про Джоли, противно слушать.>Хочу, например, логгировать парсинг каждого оператора сложения.Вот одна только эта фраза уже многое говорит о содержимом твоей головы - там хаос. Какой, в частности, смысл ты вкладываешь в словосочетание "парсинг оператора сложения"? Навскидку это может быть: Считывание терминала "+" из входящего потока токенов. Предварительное обнаружение соответствия токенов из входящего потока некоему правилу грамматики, которое ты условно обозначил как "оператор сложения" (для парсеров с возвратом - окончательное обнаружение в них можно будет констатировать только по окончании работы). Окончательное обнаружение вышеупомянутого соответствия (для LL-парсеров).Так что же из вышеперечисленного в твоём понимании "парсер что-то распарсил", говна ты кусок?>Хочу, чтобы все переменные, которые объявляются в семантических действиях в пределах одного правила, находились в одной области видимости. А переменные другого правила - в другой, отдельной.А какого хуя ты там вообще* определяешь какие-то переменные? Что вообще у тебя представляет собой "семантическое правило"? Какая проблема лепить любые данные к узлу в дереве разбора и там с ними работать как угодно в ололо-контексте этого самого узла? Ты говорить-то научись уже, маня, а то всё из тебя приходится клещами вытягивать.
>>762562Ты из этих, из компуктер-сцайентистов-обосцайентистов, что ли? Зачем ты пишешь такие простыни для объяснения очевидных вещей?Неужели не понятно, что меня только проблема реализации и интересует?Какой, в частности, смысл ты вкладываешь в словосочетание "парсинг оператора сложения"?Смотри, есть правила:expr <- expr "+" expr / expr "." expr / number ;Дополним семантическими действиями:expr <- expr { print("Пробуем сложение") } "+" expr { print("Распарсили сложение!") } / expr { print("Пробуем умножение") } "." expr { print("Распарсили умножение!") } / number ;На вот таком тексте:5+10.1оно должно выдать:Пробуем сложениеПробуем сложениеПробуем умножениеРаспарсили умножение!Распарсили сложение!Так понятнее?> А какого хуя ты там вообще определяешь какие-то переменные?Хочу и определяю. Porblems, officer?Хочу вот так писать:expr <- expr { n:=1 } "+" expr { print(n) } / expr { n:=2 } "." expr { print(n) } / number ;> Какая проблема лепить любые данные к узлу в дереве разбораТакая, что у меня не строится дерево разбора. По крайней мере, оно не хранится в памяти. Действия при разборе целиком определяются вставками { ... }.
>>762744>Неужели не понятно, что меня только проблема реализации и интересует?О том, что тебя интересует, речи не шло. Цитировать не буду, заебало уже. Чем быстрее ты отучишься разговаривать с полным ртом говна, тем быстрее окружающие начнут тебя понимать.>у меня не строится дерево разбора.Ну и кто из нас поехавший? Так построй, или тебе мамка запрещает деревья разбора строить?Даже если построишь - ты чисто физически не сможешь задавать разные семантические значения одному и тому же нетерминалу. Тебе придется вводить в своей грамматике дополнительные промежуточные нетерминалы для каждого из своих семантических значений.
>>762748> Так построй, или тебе мамка запрещает деревья разбора строить?Про ограниченность памяти слышал, не? Я не могу с тобой больше разговаривать, ты очень тупой.> Даже если построишь - ты чисто физически не сможешь задавать разные семантические значения одному и тому же нетерминалу.expr <- e1:expr "+" e2:expr { return new Add(e1, e2); } /e1:expr "." e2:expr { return new Mul(e1, e2); } /n:number { return new Number(n); }1+5*10Add[Number["1"], Mul[Number["5"], Number["10"]]]
>>762812>Про ограниченность памяти слышал, не?От тебя - нет, не слышал. От тебя вообще хуй чего услышишь про твою задачу, одно нытьё и надувание щёк.>Я не могу с тобой больше разговаривать, ты очень тупой.Ну сиди тогда ЛОГИРУЙ свои грамматики один, лол. У тебя же отлично получается.
>>763234
