Лексер, парсер, интерпретатор и все такое

Ну перегоняете его в AST каким нить стандартным средством (например тем же питоньим модулем ast), это сразу п1-3. А потом делаете с ним че хотите, что в итоге то надо получить?

Каких-то странных проблем ты себе придумал. Просто отсортируй проходы _по убыванию_ приоритета (т.е. плюс самый первый, скобки — последние) и при нисходящем парсинге это всё само разрешится без «нормализации».

Если интересно, у меня где-то валяется подобный пример на parsec.

При чем тут нормализация? Смысл АСТ как раз в том, что ты игнорируешь семантически не нужные вещи, как раз подобные скобочки. По сути нода такого даже нету как скобки, ты просто правильно строишь синтаксическое дерево. Совутею вот это почитать: http://llvm.org/docs/tutorial/index.html мне в сове время очень помог стартовать. Конкретно про бинарные выражения есть тут: http://llvm.org/docs/tutorial/LangImpl02.html#basic-expression-parsing

Каких-то странных проблем ты себе придумал

Вот потому что мне так показалось тоже — я и спрашиваю тут. Да, интересно.

Спс. Ушел читать.

1. Если вынесешь валидтор отдельно, по сути получишь два парсера одного и того же.

2. Скобки—не отдельное выражение, не надо для них строить специальных узлов в дереве.

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

Пунктов 1-3, как отдельных стадий, не существует, это всё выполняется в разборе текста за один проход одновременно (в общем случае) на выходе которого может получиться AST или сразу пригодное для вычислений дерево. Простая нормализация, вроде уничтожения тривиальных конструкций как в твоём примере, может быть выполнена сразу во время построения дерева.

Например ... Алгоритм_сортировочной_станции не подходит (она тупо берет по токену и «гори оно огнем»).

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

В приведенном примере — да. Но у меня есть ветвления. Если представить что ветвление задаёт прямая палка, то самый простой пример как-то так: a+(b|c) должно раскрыться в два дерева: a+b и a+c. Поэтому выражение в скобках как узел мне нужнО, или нет?

Сообщение сразу под твоим.

Лучшая краткая статья о разборе: http://effbot.org/zone/simple-top-down-parsing.htm

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

Годно и с примерами. Сенкс!

Поэтому выражение в скобках как узел мне нужнО, или нет?

Не нужен, тебе нужен будет нод для оператора «|». т.е. к примеру: ExprAST - общий нод для всех выражений, BinaryAST(ExprAST) - нод для бинарных выражений который хранит в себе 2 ссылки на ExprAST, которые так же могут быть либо бинарным нодом либо нодом OrAST(ExprAST) - для твоего оператор «|».

Рекурсивно, да. Т.е. проблема со скобками у меня действительно надуманная. Ок.

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

Читать это следует как BNF, только здесь он представлен в виде DSL. <|> — то же, что | в BNF, do нотация означает последовательность лексем. try здесь делает бэктрекинг (parsec весьма древний, поэтому try надо явно вызывать).

import Text.Parsec
import qualified Text.Parsec.Token as P
import Text.Parsec.Language
import Control.Applicative hiding ((<|>))
import Control.Arrow

-- AST: please note that there are no parentheses
data T = N Double -- Numbers
       | T :* T | T :/ T | T :+ T | T :- T -- Arithmetic operations
       | B Bool  -- Booleans
       | T :> T | T :< T | T :== T -- Logic operations
       | If T T T -- If clause
  deriving (Show)

-- Helper function, don't mind it.
a --> b = (a, b <$ rOp a)

-- Operators grouped by precedence: from lowest to highest
ops = [ [">" --> (:>), "<" --> (:<), "==" --> (:==)]
      , ["+" --> (:+), "-" --> (:-)]
      , ["*" --> (:*), "/" --> (:/)]
      ]

-- Don't mind the stuff below, just defining lexemes
myL = P.makeTokenParser $ javaStyle {
		  P.reservedOpNames = map fst $ concat ops
		, P.reservedNames = ["if", "else", "true", "false"]
        }
rOp = P.reservedOp myL
rW = P.reserved myL
parens = P.parens myL
braces = P.braces myL
bool = B <$> ((True <$ rW "true") 
         <|> (False <$ rW "false"))
num = N <$> P.float myL
if_ = If <$> (rW "if" *> expr) 
         <*> (braces expr) 
         <*> (rW "else" *> braces expr)

-- Parse infix operator:
infix_ x@(l:t) = do
  a <- operand t          -- Operand
  f <- choice $ map snd l -- One of the operators from group 
  b <- operand x          -- Second operand
  return $ f a b

-- Match expression enclosed in parentheses:
operand' = parens $ operand ops

-- Match any operand
operand [] = try num <|> try bool <|> parens expr
operand l@(_:t) =   try operand'    -- Try matching brackets
                <|> try (infix_ l)  -- Try infix operator
                <|> operand t       -- No luck here, proceed to the next operator precedence

test1 = "1.3 + 1.0 * (2.1 + 3.1) + 1.5"

test2 = "if (2.0 + 2.0 * 1.5== 4.0) { \
        \  if(true == false) {        \ 
        \    true                     \
        \  } else {                   \ 
        \    2.1                      \
        \  }                          \ 
        \} else {                     \ 
        \  1.0                        \ 
        \}                            "

-- This is the top-level parser
expr = try if_ <|> try bool <|> math ops

-- Main function, run tests
main = mapM (print . parse (expr <* eof) "") [test1, test2, "2.1 == 1.1"]

https://ideone.com/vxP6lr

Оператор «|» должен заставить превратиться одно дерево в два независимых с клонированием всех узлов выше.

a+(b|(c|d)) это в итоге три независимых дерева: a+b, a+c, a+d, причем скобки у (c|d) лишние и выражение может/должно быть нормализовано в: a+(b|c|d).

Да, на брутфорс-перебор смахивает.

Т.е. проблема со скобками у меня действительно надуманная. Ок.

Это зависит от того, что ты собрался делать с АСТ. Если интерпретировать, то узлы для скобок в самом деле не нужны. Если же анализировать - возможны варианты.

Спс!

Поэтому выражение в скобках как узел мне нужнО, или нет?

Всё нужно, и отдельный узел на скобки тоже нужен. После разбора выражение из примера должно превратиться вот в такое типизированное дерево

EXPR
  TOKEN(a)
  OP(+)
  TOKEN(b)
  OP(+)
  EXPR
    EXPR
      EXPR
        TOKEN(c)
        OP(-)
        TOKEN(d)

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

Анализировать. Некоторые куски из выражения выполнять.

Т.е. в итоге как я и писал в стартовом посте — нужно будет разделить парсинг и нормализацию (преобразование)?

Не понятно что в результате хочешь получить, можно просто задать определенное поведение узле «|», и 3 раза обходить дерево которое будет себя вести как 3 дерева.

Т.е. в итоге как я и писал в стартовом посте — нужно будет разделить парсинг и нормализацию (преобразование)?

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

Ну или так. Только я не могу въехать как это сделать ))

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

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

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

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

Мне не просто посчитать.

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

А можно просто взять и грамматику по уму составить. Вот это:

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

Называется «закат солнца вручную».

Т.е. в итоге как я и писал в стартовом посте — нужно будет разделить парсинг и нормализацию (преобразование)?

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

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

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

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

Че за язык то? логика? регулярки?

А на выходе что должно быть? (если таблицы переходов для регулярок - см. исходник flex-а)

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

Есть строка выражения на входе. Правила я в принципе все описал в этом треде. На выходе нужно получить дерево или деревья для последующей с ними работы совсем в другом месте. В каком «реальном» виде ты эти деревья себе представишь: сишные структуры или объекты жабоскрипта — какая разница?

В удалённом было то же самое, только по другому сформулировано.

понять как это работает под капотом

Ничего теоретически сложного. Весь парсер из примера построен из нескольких примитивных комбинаторов: один проверяет, удовлетворяет ли следующий символ какому-то условию и возвращает этот символ, <|> принимает на вход два комбинатора, и если первый не матчится, он применяет второй, плюс есть try, который принимает на вход комбинатор A, запоминает текущую позицию и возвращается на неё, если A не матчится. Собственно из этого нехитрого набора и складывается всё великолепие, остальное — технические детали.

Я должен быть водителем, а не наездником.

Кому-то не помешает сначала научиться трогаться.

Про язык спрашивал: не «на чем писать» , а «что описывает входной язык».

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

Во-первых, дерево во время разбора одновременно является и состоянием конечного автомата: пришла открывающая скобка - заводим новый узел EXPR и уходим в него; пришла закрывающая скобрка - смотрим в EXRP ли мы находимся и если да, то финализируем EXPR, иначе же имеем невалидный исходник. В более сложных грамматиках может понадобиться подниматься выше по ветке или смотреть соседей на своём уровне.

Во-вторых, если мы говоритм про группирующие скобки (я малось запутался о каких конкретно скобках идёт речь), то на стадии разбора нельзя избавляться от скобок в [a + b + (c + d)], это уже зада построения графа вычислений по ~AST.

Обычные ветвления означают куда пойти одним «потоком». Циклы — не знаю, еще не прочитал что ты скинул.

Как я себе представляю — палка же говорит парсеру: сигани-ка на самый верх, создай копии (кол-во копий = кол-во палок в скобках + 1) просчитанных ранее узлов и провались глубже для всех межпалочных выражений отдельно для каждой копии. Блин, наверное это похоже на форки и кол-во форков зависит от кол-ва ветвлений.

Попробуй объяснить как я могу вывернуть что-то вроде того что описал но без копирования узлов. Ведь мне не нужно это запускать СЕЙЧАС, а нужно построить структуру и отложить в сторонку для последующего запуска. Вернее, почему я должен думать куда мне там итти и что форкать во время работы, а не сразу получить прямые декларации к действию сохраненные ранее?

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

А можно просто взять и грамматику по уму составить. Вот это:

Намекаешь на языки с префиксной нотацией или что? Вроде ТС этого не хочет.

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

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

Что мешает при этом не создавать нод, а просто написать что-то вроде:

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

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

    return expr; // Вернул только выражение, скобки мне не нужны
}

Да у меня как всегда — не могу определиться, что могу рассказать, а что низя-низя. От этого страдает формулировка вопроса, появляется недосказанность.

Попробуй объяснить как я могу вывернуть что-то вроде того что описал но без копирования узлов. Ведь мне не нужно это запускать СЕЙЧАС, а нужно построить структуру и отложить в сторонку для последующего запуска. Вернее, почему я должен думать куда мне там итти и что форкать во время работы, а не сразу получить прямые декларации к действию сохраненные ранее?

Ты можешь сохранить одну ссылку на корень дерева, либо сделать обертку для дерева. Про форки я нифига не понял. Ты построил дерево, у тебя допустим есть какая-то таблица символов, ты пишешь tree->exec(); у тебя все дерево смотрт на эту таблицу символов и ее значения, и принимает решение, позже ты меняешь значения в таблице, и снова пишешь tree->exec(); но оно может уже себя вести по другому.

ну вот давай для примера a+(b|c) в итоге я должен вернуть ДВА результата работы: x1=a+b x2=a+c как мое дерево (или не знаю кто там) должно понять что по пути a->b оно уже ходило и теперь надо начать новый проход по пути a->c. А теперь представь что вложенных скобок и палок может быть много и в хрен знает каких бешеных (но корректных!) «отношения». Поэтому я и думаю клонировать сразу, и скармливать уже позднее просто массив деревьев, где каждое дерево заведомо известно вернет ОДИН результат.

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

Весь парсер из примера построен из нескольких примитивных комбинаторов: один проверяет, удовлетворяет ли следующий символ какому-то условию и возвращает этот символ, <|> принимает на вход два комбинатора, и если первый не матчится, он применяет второй, плюс есть try, который принимает на вход комбинатор A, запоминает текущую позицию и возвращается на неё, если A не матчится

P.S. Забыл про >> который принимает на вход два комбинатора и применяет их последовательно.

думаю клонировать сразу, и скармливать уже позднее просто массив деревьев, где каждое дерево заведомо известно вернет ОДИН результат

Если ты пишешь какой-то матчер, то массив из N деревьев может матчиться в N раз дольше :)

У вычитания a+(- (b|c)) какой смысл, такой:

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

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

a+(b|c)+d+(b|c) надо учетверить дерево? А если (b|c) повторится 10 раз, то 2**10 ?