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)
}

wherepeek()返回下一个令牌而不吃它，并match()吃下一个令牌。你会为 B() 做同样的事情。