Можно ноду «|» указывать флаг, что я по этому пути уже ходил, и выбирать другой при следующем обходе. Пример:

class OrAST: public ExprAST {
    int passes = 0;
    ExprAST *lhs;
    ExprAST *rhs;

    Result *getValue() {
        ++passes;

        if (passes % 2 == 0)
            return rhs->getValue();
        else
            return lhs->getValue();
    }
}

Можно написать парсер и без конечного автомата, пример рекурсивный спуск.

Он и есть точно такой же автомат, только выполненный через задницу, на стеке. В случае состояния-дерева можно проще и более технологично делать разбор сложных грамматик.

Что мешает при этом не создавать нод, а просто написать что-то вроде... Вернул только выражение, скобки мне не нужны

Ты же сейчас про рекурсивны спуск пишешь, чем тогда в твоём примере является expr если не нодой дерева?

Ты же сейчас про рекурсивны спуск пишешь, чем тогда в твоём примере является expr если не нодой дерева?

Да я про рекурсивный спуск писал и expr - нода дерева. Что не так?

Не так то, что ты тоже на скобки заводишь отдельный узел:

Всё нужно, и отдельный узел на скобки тоже нужен.

Зачем?? если мне нужно просто посчитать, зачем мне хранить бесполезный мусор в виде скобочных узлов?

Да я про рекурсивный спуск писал и expr - нода дерева. Что не так?

это по сути не нода для скобки, это нода выражения, которое находится внутри скобок. Если учитывать скобки, то мне пришлось бы писать что-то вроде:

class ParenExprAST: public ExprAST {
    ExprAST *expr;
};

if (currentToken == '(') {
    nextToken(); // Пропускаю скобку
    expr = parseExpr();
    nextToken();

    if (currentToken != ')')
       throw ParserError("Ошибка!", pos, line);

    return new ParenExprAST(expr); // учел скобочки
}

Для ( a+(-b) ) | ( a+(-c) ) = два результата a-b и a-c

(a+b) равно ли (b+a) ? — да

a+(b|c)+d+(b|c)  — дубликаты зависит от ситуации, для этого примера так:

a+(b|c)+d+(b|c)
    => [a+b+d+b, a+b+d+c, a+c+d+b, a+c+d+c] // развернули в 4
    => [a+b+d, a+b+d+c, a+c+d+b, a+c+d] // удалили дубликаты (в 1 и в 4)
    => [a+b+d, a+b+d+c, a+c+d] // удалили третье как дубликат второго

Предугадываю насчет вопроса про разнознаковые:

a+(-b|-c)+d+(b|-c)
    => [a-b+d+b, a-b+d-c, a-c+d+b, a-c+d-c] // развернули в 4
    => [a+d, a-b+d-c, a-c+d+b, a-c+d] // -+ сожгли др друга, для -- просто убрали дубликаты
    // среди деревьев дубликатов нет

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

Все значения будут известны, на момент выполнения может «сгореть» какой-то результат по вине значений, но это уже другая история.

(a+b) равно ли (b+a) ? — да

(Значит это не последовательность из регулярок.) Похоже все всегда укладывается в список отсортированных списков из {x, -x}, и их можно считать по ходу чтения. Если и схлопывать одинаковые списки по ходу, то меньше клонировать. Или направленный граф, тогда еще хочется добавить 0, чтобы (a+c)|(a+b+c) = a+(0|b)+c

это по сути не нода для скобки, это нода выражения, которое находится внутри скобок

Это на самом деле вопрос реализации, именно для групповых скобок, конечно, отдельные ноды вводить не обязательно, достаточно как-то уточнить подвид в expr. Например, так

class IExpr {

};
class JustExpr: public IExpr {

};

class GrpExpr: public IExpr {

};

Я и предполагал схлопывать по ходу дела.

Ноль, я про него уже думал, вводить не хочется, ибо за монитором может сесть совсем обезьяна и ей лишняя специальная сущность будет не понятна, тем более с таким хитрым применением для сокращения выражения. Пусть лучше километровые формулы максимально близкие к школьной математике вводит. Да и чем проще ввод, тем проще его разбирать. И так проблем хватает. Может быть... когда нибудь...

А что до кол-ва ветвлений — можно будет установить ограничение в настройках. Сам алгоритм должен уметь неограниченное их кол-во, ну, до упирания в ресурсы/время, конечно.

Я сначала и думал вводить разные понятия для разных скобок. Но сейчас анон меня походу поставил на правильный путь. Кажись вообще скобки ака ноды-неноды будут не нужны в дереве. Щас осознаю это все и тогда точно скажу.

Но формально я с тобой больше согласен чем с инт64.

Я всеравно не вижу смысла в хранении полуфабриката. Говорю ж, что это сразу на запуск не пойдет. Поэтому я лучше разверну все в линейные действия (как плюс еще и тупо декларативные) во время парсинга один раз, а потом будет вызываться этот «список дел» сколько угодно раз когда попросят.

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

Эти выражения сосуществуют с некоторым окружением, которое тоже нужно обслуживать.

Поверхностный же смысл прост — приготовить выражение один раз и сохранить для дерганья в будущем.

Это называется «переписывание» ( https://en.wikipedia.org/wiki/Rewriting ), на лоре вроде уже обсуждалось.

Есть несколько стратегий, для твоего первого примера можно сделать вообще примитивнейшее строковое правило типа «две и больше парные скобки заменять на одну», то есть "((...))" заменятся на "(...)".

Тем, кто пишет про разбор AST, обход и модификацию дерева на каждое переписывающее правило - мое увожение. Все эти поиски шаблонов в деревьях, еще и с модификацией - просто адовый геморой.

Интересно, как ты это в итоге реализуешь. Если не сложно, напиши потом

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

Проще игнорить (если это возможно) их вложенность сразу при разборе.

напиши потом

Ну через некоторое время. Тут и без этого задач хватает. Надо разгрести.

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

на лоре вроде уже обсуждалось

Нашел этот тредик: dynamic_cast вреден — почему?

Похоже, вот такой https://github.com/intelfx/data-processing/blob/master/differentiator/visitor... и получился «упрощатель» формулы с несколькими rewrite-правилами. Ну, выглядит, конечно, серьезно. Непонятно, насколько просто это все расширяется, т.е. добавляются новые правила

Я в том тредике интересовался, почему вместо традиционных деревьев (с указателями на потомков и рекурсивным обходом) не используют какие-нибудь списки смежности, типа как при хранении деревьев в СУБД. Теоретически, матчить правила и переписывать их должно быть проще. Но похоже так никто и не пытался делать, или есть какие-то неочевидные сложности

Как именно ты себе представляешь манипуляцию упрощения через табличное представление древовидной структуры?

Короче да, скобок не будет вообще, будет просто выражение уровнем глубже.

Это же типичная задачка на применение рекурсивного нисходящего парсера.
Грамматика такого вида, напрямую перегоняется в парсер:

expression -> logical
logical -> relation { ( "and" | "or" | "xor" ) relation }
relation -> term [ ("<"|"<="|">"|">="|"="|"/=") term ]
term -> factor { ("+"|"-") factor }
factor -> primary { ("*"|"/") primary }
primary -> ([-|+] number) | "(" expression ")"

После получения parse tree делай оптимизации, в чем проблема?

Доброе утро! Как спалось?

У меня нет проблем с парсером. Есть проблема с раскрытием и сокращением.

Как?

Посмотри в грамматику. Какое сокращение? Последовательность скобок просто проваливается вниз до следующего выражения (в самой глубокой паре скобок)

Так ты не проснулся даже. Дочитай до конца.

Напиши грамматику своего языка. (Да, твои выражения - это язык).
Приведи грамматику к форме LL(1) ну или LR(1).
Дальше скармливаешь результат парсер-генератору (в случае LL(1) можно написать ручками рекурсивный спуск, но зачем?), который по твоей грамматкие будет на выходе выдавать именночто prase tree, после чего ты делаешь преобразования с этим prase tree (удаляешь скобочки ненужные, делаешь вычисления прямо на месте, и в итоге получаешь AST.

a+(b|c)+d+(b|c) — дубликаты зависит от ситуации

Заодно построив грамматику, ты можешь случайно для себя узнать, что у тебя уже не context-free язык, а context-sensitive и парсер ты не напишешь просто так.

prase tree

prase tree

praise же, ну.

по клаве спросонок плохо попадаю

Кажись вообще скобки ака ноды-неноды будут не нужны в дереве.

Да, просто как отдельные узлы внутри которых выражения они не нужны. А как подтипы узлов выражений (EXPR, GEXPR...) могут быть полезными для, например, дополнительной информации в сообщениях об ошибках. Типа, чувак, тут ты вероятно поставил лишнюю скобку или наоборот, забыл. В общем, я на самом деле подразумевал подтипы выражений, а не именно отдельный узел для скобок.

Как именно ты себе представляешь манипуляцию упрощения через табличное представление древовидной структуры?

Теоретически представляю, написал же.

Щас попробую раскрыть мысль. Допустим, мы распарсили выражение (a + b) * (c + d) и сложили дерево в такую таблицу

id  | parent | func | param | ...
---------------------------------
 1  |    0   |   *  |       |
 2  |    1   |   +  |       |
 3  |    2   | load |   a   |
 4  |    2   | load |   b   |
 5  |    1   |   +  |       |
 6  |    5   | load |   c   |
 7  |    5   | load |   d   |

У нас есть правило переписывания (rewrite rule) x * (y + z) = x * y + x * z

Как выбрать ветки, которые попадают под это правило? Очень просто (на псевдо-sql):

выбрать parent.id как mul_id, id как plus_id где ((func == '+') && (parent.func == '*'))

т.е. выбираем ветки с оператором '*' где есть прямые потомки с оператором '+'

Как переписать эти подветки? Ну, в теории тоже должно быть несложно (тоже псевдо-sql)

вставить узел с func = '+', new_plus_id

для всех подветок с родителем plus_id                                           
 вставить узел с func = '*' и родителем new_plus_id
 добавить к этому '*' подветку из plus_id
 для всех подветок с родителем mul_id и id != plus_id -- остальные операнды
  сделать новым родителем этот '*'

Если скорость разбора не очень критична, можно попробовать натурально держать это дерево в каком-нибудь SQLite и там его мусолить.

Но, повторюсь, это просто размышления, проверять будет ли это красиво работать на практике, прямо сейчас не хочется

Для указанной тобой структуры таблицы и первого запроса где-то внутри «SQL движка» произойдет нечто такое:

resultSet = [];
for (s = 0; s < t1.length; s += 1) {
    // select
    if (t1[s].func == '+') {
        // inner join
        for (j1 = 0; j1 < t2.length; j1 += 1) {
            if (t2[j1].func == '*' && t2[j1].id == t1.parent_id) {
                resultSet.push({
                    id        : t1[s],
                    parent_id : t2[j1].parent_id
                });
                break;
            }
        }
    }
}

Чот, как-то не очень

Ну, не очень так не очень.

Пойнт был не в том, что это должно работать быстро, а в наглядности и простоте. Вот у intelfx'а переписывающее правило занимает 500 строк, а так можно уложиться строк в 50 с комментариями (наверное).

А если нужно применить какое-то более сложное правило? Типа сокращение одинаковых членов в числителе и знаменателе? На SQL такое может написать за день даже не особо продвинутый быдлокодер типа меня. С рекурсией - ну хз, хз. Вроде кажется просто, а когда доходит до реализации - видим простыни в пол-тыщи строк на простое правило.

То есть это конечно зависит от разработчика. Лично мне рекурсия дается с трудом. На каких-то сложных задачах моск вскипает. Итерациями кажется в разы проще, тык-тык и перестроил дерево

забыть об однопроходном принципе

Не факт. Какую-то нормализацию можно добавить на этапе «кусок готов, сохраняем его во внешний кусок и уходим отсюда».

Бизоний исходник:

%{
#include <stdio.h>
int ns, ne;
%}
%token  N CR
%start expr
%%
expr : | ex | alt
 | expr CR
 | expr CR ex
 | expr CR alt
;
op: '+'
 | '-'
 | op '+'
 | op '-'
;
e: N
 | '(' ex ')'
 | '(' alt ')'
;
ex: e
 | op e
 | ex op e
;
alt: ex '|' ex
 | alt '|' ex
;
%%
int yylex()
{
    char c;
    do {
        c = getc(stdin);
        fprintf(stderr, "(c=0x%02x '%c')\n", c, c);
        if (c == '|' || c == '+' || c == '-' || c == '(' || c == ')')
            return c;
        if ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z')) {
            return N;
        }
        if (c == '\n') {
            ns++;
            return CR;
        }
        fprintf(stderr, "ignored\n");
    } while (c != EOF);
    return 0;
}
int yyerror(const char *s)
{
    fprintf(stderr, "err:%d: '%s'\n", ns + 1, s);
    return 0;
}
int main()
{
    ns = ne = 0;
    return yyparse();
}

Тестовый файл:

a
+a
-a
+++++a
-+-+--++a
a+b
a-b
a++b
a--b
a+(b)
a+((b))
(((a)))
-(+a-b|c|-c|(b+e))


-(a+b|-(b+c|d))

a+(b|c)+d+(b|c)
a+(-b|-c)+d+(b|-c)

Интересная задача. Не придумаю куда ее приделать.

Сам парсер я уже в двух вариантах написал, причем еще до постинга треда )) Тут вопрос все еще — как их потом нормализовывать.

Вот такую скорми: (a+(c|d)|b+(c|d)) но судя по — оно должно схавать.

Съела. Присваивание еще есть.

Выходит, я должен забыть об однопроходном принципе и разделить парсинг на задачи:

не обязательно. можно и использовать совмещённый лексер+парсер+синтаксические предикаты и действия+семантические, в чём-то типа PEG парсера.

4) нормализатор — вот это вот все про перестроение дерева.

для "(a+b+(((c-d))))" необходимо вынести «бессмысленно вложенный» кусок на самый возможно высокий уровень и привести к виду "(a+b+(c-d))" еще ДО запуска. Т.е. нормализовать.

ещё прочитай Брусенцова про Сетунь, например. и одна из его работ — про ПОЛИЗ (обратную польскую нотацию) и нормализованый ПОЛИЗ с минимальным стеком.

в тех его работах описан алгоритм нормализации. ЕМНИП, там и AST строить целиком не обязательно было.

нормализованый ПОЛИЗ с минимальным стеком

поищи в районе публикаций о Сетунь-70 с троичным форт-процессором и ДССП, системе «Наставник» на основе ДССП

вот это глянь

Жоголев Е.А. Интерпретатор ПОЛИЗ-63. ЖВМ и МФ, 5, №1, 1965. Аmdаhl G.M., Blaaum G.А., Вrооks F.Р. Architecture of the IBM System/360. «IBM Journ. Research and Development», 8, №2, 87 - 101, 1964.

Наmblin С. L. Translation to and from Polish notation. «Computer Journ.», 5, №3, 210 - 213, 1962.

Брусенцов Н.П. Усовершенствованная бесскобочная запись формул. ЖВМ и МФ, 12, №3, 1972.

Брусенцов Н.П., Руднева Т. Л. Алгоритм трансляции алгебраических выражений в почти совершенную бесскобочную запись. В сб.: «Вычислительная техника и вопросы кибернетики», вып. 9. Изд-во МГУ, 1972.

Брусенцов Н.П., Руднева Т.Л. Алгоритм трансляции алгебраических выражений в совершенную бесскобочную запись. В сб.: «Вычислительная техника и вопросы кибернетики», вып. 11. Изд-во МГУ, 1974.

Брусенцов Н.П. Устройство управления цифровой вычислительной машины с магазинной памятью. Авторское свидетельство #391562, кл. G 06f 9/10. Опубликовано 25.7.73. Бюллетень # 31.

про «совершенную бесскобочную запись» и нормализованный ПОЛИЗ

например

про Сетунь-70 и ДССП, язык РАЯ

Общая характеристика Сетунь-70:

tl;dr стековая машина, выражения в обратной польской нотации, троичный форт-процессор

История создания и развития ДССП: от «Сетуни-70» до троичной виртуальной машины

tl;dr ДСПП — это виртуальная троичная машина, троичный форт-процессор. используются выражения в нормализованном ПОЛИЗ (совершенная бесскобочная форма). это REPL. язык РАЯ — это DSL поверх ТВМ на форте. есть ООП и исключения. ДССП и ТВМ реализованы как виртуальные машины поверх обычной, «двоичной» машины. Сетунь-70 это аппаратный троичный форт-процессор.

кутриты вместо кубитов для квантовых компьютеров

можно ещё вспомнить про оптические компьютеры и RGB как -1, 0, +1.

(((c-d)))

Мусорные скобки обрабатываются без обхода списков этими правилами:

%%
e: '(' ex ')' {$$=$2;}
...
ex: e {$$=$1;}
...
%%

Аннотированный указатель программ для вычислительной машины «Сетунь» (первой, ещё не Сетунь-70):

в самом начале читаем:

Cистема автоматического кодирования (автокод) ПОЛИЗ для машины «Сетунь»

Система представляет собой автокод 1:1. В неё входят следующие компоненты:

- Входной язык СИМПОЛИЗ-64 для записи программ в символических обозначениях.

- Внутренний язык ИНПОЛИЗ, представляющий собой троично-кодированную пользскую инверсную запись.

- Программа автоматического кодирования АВТОКОДИР.

- Операционная система, включающая интерпретатор ПОЛИЗ и библиотеку подпрограмм.

1968 год

68-ой год, Карл!

пришла через пост в другом топике. вроде тут уже всё ясно сказали. AST скобок не имеет, это логика операндов. как его строить - зависит от личных предпочтений.

я вообще для простоты брала ANTLR (там наглядно и очень удобно пишутся лексеры и парсеры) и генератор сишного кода, к которому я допилила плюсовые классы (это было несложно). но можно взять bison или yakk. левые или правые парсеры - это дело вкуса. на результат особого влияния не имеет, но в конкретной задаче могут быть свои особенности и предпочтения. к другим языкам есть порты этих библиотек.

а с минусами это уже операнды и отдельные узлы. их не редуцируешь на уровне парсера. но можно как раз «нормализатор» прикрутить, который схлапывает эти минусы потом в дереве.

Я думаю можно просто добавить UnaryExprAST и метод parseUnary(), где собственно и будет парситься минус или плюс или еще какой унарый оператор, а при парсинге бинарного выражения уже подставлять унарные.

или yakk

yacc

хаскель как метод трансляции "в железо" для троичной логики

вообще интересная тема. вот этот код на хаскеле можно рассматривать как зайчатки транслятора простого языка (типа Oberon-2) в простую ВМ (типа форт-машины, или ДССП, или троичной ТВМ).

а саму эту машину — можно либо исполнять как есть (существующая реализация ДССП) или реализовать интерпретатор ДССП на хаскеле (более композабельный и мобильный) либо реализовать сразу в железе.

для трансляции «в железо» тоже можно взять хаскель. например: хаскель и FPGA или сразу хаскель и реализация процессора 6502.

теперь можно получить из этих «композабельных технологий» на хаскеле композицию: троичный оберон-2 транслируемый в FPGA через ДССП через хаскель. и теоретически, весь софт под ДССП сразу заработает.

но можно пойти дальше, в суперкомпиляцию и частичные вычисления. вспомнить про проекции Футамуры-Турчина: «суперкомпиляция интерпретатора это компилятор», «специализация компилятора это интерпретатор» и получить сразу метакод времени компиляции.

можно пойти и ещё дальше, в многозначную логику. например, в троичную.

теперь если расписать «6502 на хаскеле» как комбинатор комбинаторов, специализированный частичными вычислениями — выделить эти основания вычисления явно. и расписать оттуда «двоичный сумматор» как adder 2 x y = ..., «двоичный умножатор», «двоичное УУ», «двоичную память» как карринг функций.

и поблочно переводить на троичные. реализуя, например, Сетунь первую или Сетунь-70 как форт-процессор (6502 тут хорош ибо прост: RISC процессор почти). или делая «троичный 6502».

то по аналогии нужно сделать лишь «перевод»: «троичный сумматор» как adder 3 x y = ..., «троичный умножатор»,«троичное УУ», «троичная память»(тут больше всего засады, ибо не всё ясно)

тогда: обобщая из реализации «двоичный 6502 на хаскеле» в двоичной логике в «троичный 6502 на хаскеле» как карринг ФВП из частичных вычислений в более общей металогике, многозначной логике — мы полуавтомагически получим этот «троичный 6502 на хаскеле».

теперь, суперкомпилируя получим перевод не просто из технологиии на технологию, с переносом ядра технологии (ср.: монадические внешняя переменная, внутреннее значение)

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

и весь старый код этих платформ сразу заработает. и книжка «Project Oberon» в троичном Обероне-2. и новый софт на троичном Обероне, с бриджем и гимназистками.

в троичной логике отрицание неоднозначно (не да = нет или «не знаю»), поэтому можно поисследовать различные формулы для более эффективной оптимизации, совмещением различных вариантов. то есть, пространство для оптимизаций в принципе больше.

то есть, мы не хотим «перестраивать дерево в изоморфное нормализацией», и цепочкой деревьев из AST. мы хотим катаморфизмов для обхода деревьев и изоморфизмов таких кото(мяу)морфизмов в виде более общей категории категорий формальной металогики и её, металогики, металогических законов.

частично вычисляя, суперкомпилируя и специализируя везде, где только можно. но двигаясь от инвариантов и синтезируя морфизмы таких инвариантов. при этом общий кот с кото-морфизмами будет продолжать работать.

типа компилятора на PEG Ian Piumatra и nanopass framework.

в троичной логике отрицание неоднозначно (не да = нет или «не знаю»)

нормализованный (-(-(c-d))) в (c-d)

Брусенцов про аристотелеву логику, несостоятельность двоичной арифметики и троичную функцию следования импликаций — материальной и формальной

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

не спроста это.

так так оно и есть. просто чтобы схлопнуть заранее ненужные итерации по унарным операндам, можно дополнительно пробежаться по дереву с целью вычислить двойные унарные минусы, например, и сократить количество узлов, таким образом.