Выходное условие для AST с DFS - PullRequest
Новая
       11

Выходное условие для AST с DFS

1 голос
/ 30 марта 2019

Я пытаюсь написать универсальный сборщик AST с подходом DFS.

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

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

Если я определю грамматику следующим образом: 

expr := addExpr;

addExpr := NUMBER
         | NUMBER OPERATOR expr
         ;

Проходит. Структура семантически верна, но при прохождении будет давать неправильные результаты. "4 - 2 + 2" оценивается как "4 - (2 + 2)" вместо желаемого "(4 - 2) + 2".

Мне нужно определить грамматику следующим образом: 

expr := addExpr;

addExpr := NUMBER
         | expr OPERATOR NUMBER
         ;

Проблема здесь в том, что это приводит к бесконечной итерации: 

expr -> addExpr -> expr -> addExpr -> ...

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

Думаю, стек, который мне нужен, будет выглядеть примерно так: 

expr (against 4 - 2 + 2)
  addExpr (against 4 - 2 + 2)
    0: NUMBER -> matches 4, won't finish.
    1: expr OPERATOR NUMBER
      expr (against 4 - 2 + 2) -> I cannot break yet.
        addExpr (against 4 - 2 + 2) -> I cannot break yet.
          0: NUMBER -> matches 4, won't finish.
          1: expr OPERATOR NUMBER
            expr (against 4 - 2 + 2) -> I cannot break yet.
              addExpr (against 4 - 2 + 2) -> I cannot break yet.
                0: NUMBER -> matches 4, will resolve in the end.
                1: expr OPERATOR NUMBER
                  expr (against 4 - 2 + 2) -> BREAK!

Кажется, что-то произвольно, когда ломаться. Есть ли какое-то хорошее правило или условие для достижения этого?

Я действительно не хочу просто устанавливать "случайную" максимальную глубину, если я могу избежать этого. Может быть, я должен рассмотреть подход BFS (совсем другой набор проблем), но я бы хотел придерживаться DFS, если это возможно.

...