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

Question

考虑语法：E-> 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

关于实现，您必须指定要实现的位置和目的。