Скажу сразу — Я НЕ ПИШУ СВОЙ ЯП!
Задача у меня такая: есть выражение, которое нужно распарсить, оно, в принципе, лексически простое.
И тут есть одно «НО». Например для "(a+b+(((c-d))))" необходимо вынести «бессмысленно вложенный» кусок на самый возможно высокий уровень и привести к виду "(a+b+(c-d))" еще ДО запуска. Т.е. нормализовать. Это просто пример, сами же выражения могут быть монструозными, а вариантов нормализации больше одного, и эти выражения нужно как-то облагородить, сократить.
Например https://ru.wikipedia.org/wiki/Алгоритм_сортировочной_станции не подходит (она тупо берет по токену и «гори оно огнем»).
Выходит, я должен забыть об однопроходном принципе и разделить парсинг на задачи:
1) лексер — пройдет и соберет все токены, какие получилось.
2) валидатор — провалидирует синтаксис выражения.
3) парсер — построит АСД как есть (может быть объединен с валидатором, строим дерево сразу, и если ошибка, то прерываемся).
4) нормализатор — вот это вот все про перестроение дерева.
Все я правильно думаю? Есть что прокомментировать? Есть какой-то менее раздутый подход к решению этой задачи?
Кастую тех кто засветился на первой странице поиска ЛОРа по фразе «свой ЯП»:
holuiitipun,
true_admin,
Zubok,
Int64
и наверное intelfx, он вроде головастый.
Остальные так же приглашаются — еще одна голова свежих мыслей никогда не будет лишней.
UPD:
Для ( 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] // -+ сожгли др друга, для -- просто убрали дубликаты
// среди деревьев дубликатов нет
Порядок операндов не важен, важны их значения, дубликаты операндов в одном дереве и дубликаты деревьев (от перестановки слагаемых сумма не меняется) удаляются как показано выше.
Все значения будут известны, на момент выполнения может «сгореть» какой-то результат по вине значений, но это уже другая история.
