不确定在涉及 () 时如何解析树？

Question

我有以下语法：

  E -> E+T | E-T | T
  T -> T*F | T/F | F
  F -> i | (E)

这个字符串：

(i+i)*i

让我困惑的是我将如何合并 ()'s？

尝试：

E -> T

T的左支 = T -> F -> i

中支 = *

右分支 T = F -> (E) -> E + T ..... (E -> i, T -> i)

我不确定这是否可以理解，但我不确定在这里还可以如何编写解析树。任何帮助都感激不尽！谢谢！

Answer 1

一种常见的解析树表示方式是树图（通常根在顶部），其中树中的每个节点都是一个符号，树的 'child' 关系反映了步骤在推导中。

例如，对于 i*(i+i)，解析树可能如下所示：

    E
    |
    T
    |
+---+---+
|   |   |
T   *   F
|       |
F   +---+---+
|   |   |   |
i   (   E   )
        |
    +---+---+
    |   |   |
    E   +   T
    |       |
    T       F
    |       |
    F       i
    |
    i

或者像这样：

        E
        |
        T
        |
+---+-----------+
|   |           |
T   |           F
|   |           |
F   |   +-------+-------+
|   |   |       |       |
|   |   |       E       |
|   |   |       |       |
|   |   |   +---+---+   |
|   |   |   |   |   |   |
|   |   |   E   |   T   |
|   |   |   |   |   |   |
|   |   |   T   |   F   |
|   |   |   |   |   |   |
|   |   |   F   |   |   |
|   |   |   |   |   |   |
i   *   (   i   +   i   )

如您所见，括号不会造成特殊问题。

不确定在涉及 () 时如何解析树？

Not sure how to do parse tree when a ()'s is involved?

grammar

context-free-grammar