Использование шаблона интерпретатора в составной структуре

Question

Меня попросили составить оценщик выражений, используя Composite, Recursive Descendent Parser и Interpreter.

Вот грамматика:

<cond> → <termb> [OR <termb>]*
<termb>→<factb>[AND <factb>]*
<factb>→<expr> RELOP <expr> | NOT <factb> | OPAR <cond> CPAR
<expr> → [PLUS | MINUS] <term> [(PLUS <term>) | (MINUS <term>)]*
<term> → <termp> [(MULT <termp>) | (DIV <termp>) | (REM <termp>)]*
<termp> → <fact> [POWER <fact>]*
<fact> → ID | NUM | OPAR1 <expr> CPAR1
----TERMINALS----
ID → ("A" | ... | "Z" | "a" | ...| "z") [("A"| ... | "Z" | "a" | ...| "z" | "0" | ... | "9")]*
NUM → ("0" | ... | "9") [("0" | ... | "9")]*
OPAR → "("
CPAR → ")"
OPAR1 → "["
CPAR1 → "]"
RELOP → EQ | NEQ | GT | GE | LT | LE
EQ → "= ="
NEQ → "!="
GT → ">"
GE → ">="
LT → "<"
LE → "<="
POWER → "^"
DIV → "/"
REM → "%"
MULT → "*"
MINUS → "−"
PLUS → "+"
AND → “and” or “&&”
OR → “or” or “||”
NOT → “not” or “!”

Назначение:

Цель проекта, основанного на Composite, Recursive Builder и Interpreter, состоит в том, чтобы получить условное выражение, выполнить синтаксический анализ и построить его составное дерево. Начиная с дерева, вы должны оценить результат условия, основываясь на внешнем контексте (считанном из файла свойств), который содержит значение внутренних переменных.

Теперь, первое, что я заметил, это то, что Interpreter использует составную структуру, поэтому было неплохо расширить мою составную структуру с помощью метода оценки (:Context).

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

Итак, я построил свое дерево с помощью Composite + Recursive Builder, он распознает входные данные и создает дерево без каких-либо проблем.

Но вопрос в том, как мне применить Interpreter к моей структуре?

Вот моя диаграмма классов (что-то итальянское, но это вполне понятно)

Если я правильно понял, Interpreter использует класс для каждого правила грамматики, поэтому мне нужно создать класс cond, затем termb и так далее.

Но как мне связать их с моим композитом?

Answer 1

Не уверен, почему вам сказали не использовать ту же древовидную структуру. Я думаю, что я бы добавил метод valu () в мой интерфейс выражения. Это имеет смысл для меня. Выражение должно знать, как оценивать себя.

Я бы сказал, что ваш текущий интерфейс выражения предоставляет слишком много (например, операнды). Как клиент выражения, мне нужно только 1) вызвать его и 2) прочитать результат, и я думаю, что, возможно, 3) распечатать его. На самом деле, я бы предпочел использовать toString() вместо прямой печати.

Вы, наверное, уже заметили, но не все выражения принимают 2 операнда (например, NOT или NEGATE). Это уже создает некое расхождение с вашим интерфейсом. Я бы упростил это до:

 public interface Expression {
   int evaluate();
 }

Тогда каждая из ваших операций и терминалов знает, как оценить себя (и преобразовать себя в строку).

Таким образом, у меня могут быть конкретные операции, такие как:

 public class Terminal implements Expression {
   private final int value;

   public Terminal(int value) { this.value = value; }

   public int evaluate() { return value; }

   public String toString() { return String.valueOf(value); }
 }

 public class Add implements Expression {
   private final Expression left;
   private final Expression right;

   public Add(Expression left, Expression right) {
     this.left = left;
     this.right = right;
   }

   public String toString() {
     return left.toString() + " + " + right.toString();
   }

   // leave the rest for you
 }

Теперь я могу построить дерево довольно легко

Expression expr = new Add(new Terminal(1), new Subtract(new Terminal(2), new Terminal(3)));

int result = expr.evaluate();
System.out.print(expr.toString() + " = " + result);

И мне даже не нужен прямой доступ к отдельным операндам.

Answer 2

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

Если Expression - ваша основная композиция, тогда:

Выражение: Термин Выражение: OperandTerm

Условие: выражение выражения BinOperand Условие: выражение UnaryOperand

Срок: Int | Foat | ...

,,,

Answer 3

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

Возможно, вам не нужно создавать один класс для элемента notTerminal и терминала, используйте атрибуты наподобие (operatorType, expressionType) в предложениях NonTerminal/Terminal, чтобы отличаться от ваших грамматических символов.

Учитывая и выражение, сгенерированное с вашей грамматикой как [ A = 0 ], дерево объектов, сформированное с помощью классов шаблонов интерпретатора, будет выглядеть следующим образом (пожалуйста, простите за плохое качество и ошибки синтаксиса UML, но у меня сейчас нет подходящего редактора UML):

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

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

Надеюсь, это поможет.