parsing - 左关联运算符能否以自上而下的 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()不吃就返回下一个 token ，match()吃下一个 token 。你会对 B() 做同样的事情。