语法分析树？

发布于 2024-12-12 11:22:49 字数 229 浏览 2 评论 0原文

这道题是我的CS作业，我不知道该怎么做。

考虑语法

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

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

我尝试遵循该结构，最终得到 (L,(L,L)) code> 但这似乎并不正确。有人能把我推向正确的方向吗？

原文

This question is on my CS homework and I have no idea how to do it.

Consider the grammar

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

Draw a parse tree for the sentence ( a , ( a , a ) )

I tried following the structure and I end up with (L,(L,L)) That doesn't seem to be correct though. Could anyone push me in the right direction?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

小镇女孩 2024-12-19 11:22:51

看一下句子(a, (a, a))。它可能匹配哪一个右侧（RHS）？只有第一个，S ← ( L )。因此，树的根将是一个带有三个子节点的 S 节点：一个 ( 节点、一个 L 节点和一个 <代码>)-节点。

现在您需要弄清楚 L 节点的子节点是什么，并且它们必须与其余输入匹配：a,(a,a)。所以看看LHS上有L的规则。在这些规则中，哪一条的 RHS 可以匹配 a,(a,a)？

回复收藏 0 原文

悲念泪 2024-12-19 11:22:51

(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。

The parse tree for (a,(a,a)) is obtainable from a leftmost derivation of (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  ]

The root of your parse tree is S. For each rewrite of a nonterminal symbol in the derivation, draw the appropriate node in the parse tree. Also, your grammar isn't optimal and among other things, contains chain rules. Removing them would prevent having to derive S from L in order to derive a.

回复收藏 0 原文