什么是衍生品？

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

推导意味着用生产规则的右侧替换给定字符串的非终结符。从起始符号生成完整的终端字符串的规则应用序列称为推导。

它可以通过用一些产生式重复替换变量来导出以开始符号开头的终端字符串。CFG 的语言是我们可以推导出的一组终端符号。这种语言称为上下文无关语言。

推导用 ⇒ 表示。

例如，考虑一个语法。

G=({S},{a,b},P,S)，其中，P 包含以下产生式 -

P={S→aSa |bSb | ∈}

在上面，S可以被aSa或bSb或ε代替。

推导类型

有两种类型的推导如下 -

  • 最左推导

如果我们在每一步仅对最左边的变量使用产生式，则推导 A⇒*w 称为最左推导。这里，* 表示 0, 1, 2,…………..n 个推导数。

  • 最右推导

如果我们在每一步对最右边的变量使用产生式，则推导 A⇒*w 是最右边的推导。它也称为规范推导。

示例 1 - 让 G 成为带有产品的 CFG。

S → AA
A → αB
B → b
B → ε

查找 (1) 最左侧

  • 字符串abab的最右边推导。

解决方案

  • 最左推导 -

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

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

⇒ lm ab $\下划线{A}$

⇒ lm aba $\下划线{B}$

⇒我阿巴布

  • 最右推导

S ⇒ rm A $\下划线{A}$

⇒ rm A a $\下划线{B}$

⇒ rm  $\下划线{A}$ab

⇒ rm a $\下划线{B}$ab

⇒ rm abab

Example2 - 为回文语言编写上下文无关语法。

L={wcw R | w ∈ {a,b}*} 具有中间符号 c。这里 R 表示字符串的反转。

解决方案

语言表示带有中间符号“c”的回文。

∴语法 G =(V,∑,P,S) 会有产生式。

S → a S a
S → b S b
S → c

例如，要生成回文 abcba，推导是

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

⇒ ab $\下划线{S}$ba

⇒ ABCBA

Example3 - 为生成二进制数回文的语言编写 CFG。

解决方案

S → 0 S 0 | 1 S 1
S → 0 | 1 | ε

例如，要生成字符串 0 1 1 0，推导是

S ⇒ 0 S 0
⇒ 0 1 S 1 0
⇒ 0 1 ε 1 0
⇒ 0 1 1 0

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

E → E+E|E * 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/363291.html

回到顶部