什么是解析树（派生树）？

  • Z时代
  • 2024-01-10
  • 分类：综合

推导意味着用生产规则的右侧替换给定字符串的非终结符。从起始符号生成完整的终端字符串的规则应用序列称为推导。解析树是推导的图形表示。因此，它也被称为派生树。派生树独立于使用产生式的另一棵树。

解析树是一种有序树，其中节点用产生式左侧标记，其中节点的子节点定义其等效的右解析树，也称为语法树、生成树或产生式树。

CFG G =(V,∑, P,S) 的解析树是满足以下条件的树 -

  • Root 具有标签 S，其中 S 是开始符号。

  • 解析树的每个顶点都有一个标签，该标签可以是变量 (V)、终端 (Σ) 或 ε。

  • 如果 A → C 1 ,C 2 …….C n是一个产生式，则 C 1 ,C 2 …….C n是标记为 A 的节点的子节点。

  • 叶节点是终端节点（Σ），内部节点是变量(V)。

  • 内部顶点的标签始终是一个变量。

  • 如果一个顶点 A 有 k 个标签为 A 1 ,A 2 …….A k的孩子，那么 A →

A 1 ,A 2 …….A k将是上下文无关文法 G 的产生式。

产量- 派生树的产量是从左到右排序的叶子标签的串联。

Example1 - 如果 CFG 有产品。

S → a A S | a
S → Sb A | SS | ba

证明 S ⇒ *aa bb aa & 构造分析树，其产量为 aa bb aa。

解决方案

S ⇒ lm lm a $\下划线{A}$S

⇒ $\下划线{S\:b}$AS

⇒ aa b $\下划线{A}$S

⇒ aa bba $\下划线{S}$

∴ S ⇒ * aa bb aa

派生树

产量 = 叶子从左到右排序 = aa bb aa

示例 2

考虑 CFG

S → bB | aA
A → b | bS | aAA
B → a |aS | bBB

查找 (a) 最左侧

  • 字符串 b aa baba 的最右边推导。另外，找到派生树。

解决方案

  • 最左推导

S⇒b $\下划线{B}$

⇒ bb $\下划线{B}$B

⇒ bba$\下划线{B}$

⇒ bbaa$\下划线{S}$

⇒ bb aa$\下划线{bB}$

⇒ bb aa b $\下划线{aS}$

⇒ bb aa bab $\下划线{B}$

⇒ bb aa ba ba

  • 最右推导

S ⇒ b$\下划线{B}$

⇒ bb B$\下划线{B}$

⇒ bbBa$\下划线{S}$

⇒ bbBab$\下划线{B}$

⇒ bbBaba$\下划线{S}$

⇒ bbBabab$\下划线{B}$

⇒ bb$\下划线{B}$abab a

⇒ 巴巴巴巴

Example3 - 考虑下面给出的语法 -

E⇒ E+E|E $\ast$E|id

寻找

  • 最左边

  • 字符串的最右推导。

解决方案

  • 最左推导

E ⇒ $\下划线{E}$+E

⇒ $\下划线{E}$+E+E

⇒ id+E+E

⇒ 身份证+身份证+E

⇒ 身份证+身份证+身份证

  • 最右推导

E ⇒ E+$\下划线{E}$

⇒ E+E+$\下划线{E}$

⇒ E+E+id

⇒ E+id+id

⇒ 身份证+身份证+身份证

以上是 什么是解析树（派生树）？ 的全部内容， 来源链接： utcz.com/z/363292.html

回到顶部