左结合算子能否以一种自顶向下的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()做同样的事情。