Можно ли выразить левый ассоциативный оператор таким образом, чтобы синтаксические анализаторы LL(1) могли его понять?

Question

Я пытался реализовать нисходящий синтаксический анализатор LL(1) для языка калькулятора. Это позволяет нам только суммировать, вычитать, делить и умножать числа. Нет скобок.

S -> A

A -> B + A
   | B - A
   | B

B -> int * B
   | int / B
   | int

Поскольку эта грамматика не подходит для парсера LL(1), мне пришлось немного ее изменить:

S -> A

A -> B A'
A'-> + A
   | - A
   | λ

B -> int B'
B'-> * B
   | / B
   | λ

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

Answer 1

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

function A() {
   val = B();
   t = peek();
   while (t=='+' || t=='-') {
     match(t);
     val1 = B();
     if (t=='+')
       val = val + val1;
     else
       val = val - val1;
     t = peek();
   }
   return(val)
}

где peek() возвращает следующий токен, не съев его, и match() ест следующий токен. Вы бы сделали то же самое для B().