Приоритет правил и дерево разбора

Question

С учетом такой грамматики

test: x;

x  : x '+' x
   | x '*' x
   | INT
   ;

INT: [0-9]+ 

(переключение приоритета сделано специально)

Входные данные следующие: 6 + 7 * 8 * 9

Когда я смотрю на дерево разбора, оно выглядит так, как будто оно вычислено (((6 + 7) * 8) * 9).

Я не понимаю, как строится дерево разбора. Мне кажется, что так оно и было построено:

                       Rules applied

test                   test: x
x                      x '*' x
(x * x)                x '*' x
((x * x) * x)          x '+' x
(((x + x) * x) * x)

Но почему он не пытается сначала применить x : x '+' x. Это первая альтернатива правила, и входные токены будут совпадать. Но если бы это было так, дерево разбора выглядело бы так:

                       Rules applied

test                   test: x
x                      x '+' x
(x + x)                x '*' x
(x + (x * x))          x '*' x
(x + (x * (x * x)))

Я прочитал, что оно сначала пытается найти соответствие первой альтернативе, но здесь это не так. Какова причина? И что на самом деле означает приоритет?

Answer 1

Давайте начнем с последнего вопроса: приоритет (в данном контексте) - это термин, описывающий, в каком порядке должны выражаться подвыражения. Существуют довольно распространенные правила приоритетов, такие как: * и / имеют одинаковый приоритет и оцениваются слева направо, но перед любым выражением + или -, et c.

В ANTLR4 это реализуется простым подходом «сначала alt first» - и чем раньше вычисляется выражение, тем выше его приоритет. В вашем правиле x вы сначала перечислили подвыражение +, поэтому оно имеет самый высокий приоритет. Неудивительно, что вы получаете дерево разбора, которое показывает + на самом низком уровне. Сделав * главным оператором и + секунду, вы получите ожидаемый результат, как показывает это дерево разбора: