语法分析树？

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)。所以看看在LHS上有L的规则。在这些规则中，哪一个具有与a,(a,a)匹配的RHS

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。对于派生中的非终端符号的每次重写，在解析树中绘制相应的节点。此外，您的语法并不是最优的，而且还包含链式规则。删除它们将避免必须从L派生S才能派生a。