Похоже, не удается разрешить двусмысленность в грамматике Antlr

#parsing #antlr4 #arithmetic-expressions

#разбор #antlr4 #арифметические выражения

Вопрос:

Я создаю максимально простую грамматику, которая в основном распознает арифметические выражения. Грамматика должна правильно следовать правилам приоритета арифметических операторов (PEMDAS), и для этого я поставил expr ('*'|'/') term перед expr (' '|'-') term тем, чтобы обеспечить этот приоритет. Это файл арифметики.g4, который у меня есть:

  /*Productions */   expr: expr ('*'|'/') term  | expr (' '|'-') term  | term  ; term: '('expr')'  | ID  | NUM  ;  /*Tokens */ ID: [a-z] ; NUM: [0-9] ;  WS: [trn] -gt;skip;

Однако вывод грамматики не такой, каким он должен быть. Например, для арифметического выражения 4 * (3 10) я получаю приведенное ниже дерево разбора (что абсолютно неверно):

Любые предложения о том, как я могу изменить грамматику, чтобы получить то, что я ищу. Я новичок в antlr и не уверен, какую ошибку совершаю. (jbtw моя ОС-Windows)

1. Что неверного в этом дереве разбора? Приоритет даже не вступает в игру для этого выражения, учитывая круглые скобки? На самом деле нет другого способа проанализировать это выражение. Может быть, вы хотели использовать входные 4 * 3 10 данные ? Но для этого вы действительно должны получить правильное дерево синтаксического анализа. Примером того, как ваша грамматика приведет к неправильному дереву синтаксического анализа, может быть 4 3 * 10 .

2. Пожалуйста, уточните, чего вы ожидали. Я не являюсь пользователем ANTLR, но мне кажется, что дерево семантически соответствует входным данным. Здесь у вас есть явные круглые скобки, поэтому приоритет оператора, похоже, на самом деле не применим к этому примеру. Вас беспокоят избыточные expr узлы или что-то еще?

Ответ №1:

(Я предполагаю , что вы допустили ошибку в своем примере (который выглядит нормально), и вы действительно имели в виду, что вы получаете неправильное дерево для ввода 4 3 * 10 , так что я собираюсь ответить на этот вопрос. Если это не то, что вы имели в виду, пожалуйста, поясните.)

Вы правы в том, что ANTLR разрешает двусмысленности на основе порядка правил, но это не относится к вашей грамматике, потому что ваша грамматика не является двусмысленной. Для такого ввода 4 3 * 10 есть только один способ проанализировать его в соответствии с вашей грамматикой: * быть внешним оператором , с 4 3 его левым и 10 правым операндом. Правильный способ ( как внешний оператор с 3 * 10 правильным операндом) не работает с вашей грамматикой, потому 3 * 10 что он недействителен term , и правильный операнд должен быть в term соответствии с вашей грамматикой.

Чтобы получить двусмысленность, разрешенную так, как вы хотите, вам нужно будет сделать оба операнда ваших операторов expr s.