parsing - 语法分析树？

Question

这个问题在我的 CS 作业上，我不知道该怎么做。

考虑语法

S ← ( L ) 
S ← a
L ← L , S 
L ← S 

为句子绘制解析树( a , ( a , a ) )

我尝试遵循结构，但最终结果(L,(L,L))似乎并不正确。谁能把我推向正确的方向？

Answer 1

这是您所追求的部分内容：

现在你可以做剩下的工作了:)

Answer 2

看句子(a, (a, a))。它可能匹配哪个右手边（RHS）？只有第一个，S ← ( L )。因此，树的根将是一个S具有三个子节点的 -node：一个(-node、一个L-node 和一个)-node。

现在您需要弄清楚L-node 的子节点是什么，它们必须匹配剩余的输入：a,(a,a)。因此，请查看LLHS 上的规则。在这些规则中，哪一个具有可以匹配的 RHS a,(a,a)？

Answer 3

的解析树(a,(a,a))可从 的最左推导获得(a,(a,a))：

S => (L)        [S -> (L)]
  => (L,S)      [L -> L,S]
  => (S,S)      [L -> S  ]
  => (a,S)      [S -> a  ]
  => (a,(L))    [S -> (L)]
  => (a,(L,S))  [L -> L,S]
  => (a,(S,S))  [L -> S  ]
  => (a,(a,S))  [S -> a  ]
  => (a,(a,a))  [S -> a  ]

解析树的根是S. 对于推导中非终结符号的每次重写，在解析树中绘制适当的节点。此外，您的语法不是最佳的，除其他外，还包含链式规则。删除它们将防止必须派生S才能L派生a。