构建字符串 aabbabba 的推导树。

问题

针对给定的上下文无关文法 (CFG)，推导出字符串 aabbabba 的推导树。

S->aB|bA
A->a|aS|bAA
B->b|bS|aBB

解决方案

推导是一系列产生式规则，用于获取输入字符串。

推导树

它是给定 CFG 的给定产生式规则推导的图形表示。它也称为语法树。

属性

推导树包含一些属性，如下所示：

  • 根节点始终是表示起始符号的节点。
  • 推导是从左到右读取的。
  • 叶节点始终是终结符节点。
  • 内部节点始终是非终结符节点。

给定的 CFG 如下：

S->aB|bA
A->a|aS|bAA
B->b|bS|aBB

要绘制语法树，首先尝试获取字符串 aabbabba 的推导。

让我们以如下所示的最左推导为例：

S-> aB
 ->aaBB
 ->aabSB
 ->aabbAB
 ->aabbaB
 ->aabbabS
 ->aabbabbA
 ->aabbabba which is our final string

现在，为给定的语法构建推导树。

如果语法生成多种类型的树，则称给定的语法为二义性语法。

更新于： 2021年6月12日

12K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告