compiler-construction - 如何为特定句子生成语法树，例如 a+b*c where id->a|b|c？

Question

考虑语法：E-> E+E|EE|E*E|E/E|(E)|id

我已经尝试了至少 5 个小时来解决这个问题，但失败了。请告诉我，

• 解决这个问题的想法是什么？

• 如何实施？

Answer 1

语法树是通过解析构建的，这在某种意义上是反向应用语法。所以你看到a、b和c只能来自id，而id又只能来自E。现在你在E+E*E。您可以先减少 E+E，也可以先减少 E*E，然后再减少另一个。结果 E 是树的根。两种可能的语法树之一（减少第一个 E*E 的那个）是这个

  E
 /| \
E +   E
|    /|\
id  E * E
|   |   |
a   id  id
    |   |
    b   c

关于实施，您必须指定要实施的地点和目的。