不可达非终结符的文法语言推导方法及指定文法的左推导与推导树求解

首先得帮你澄清一个小误解：你提到的“S出现在产生式右部导致不可达”是混淆概念啦——这里的S是起始符号，它出现在右部属于递归产生式，用来生成重复结构，完全不是“不可达非终结符”（不可达是指从起始符号出发永远推导不到的非终结符，显然S自己肯定是可达的）。只要控制递归的次数，选择合适的产生式终止递归，就能得到目标串，不会残留非终结符~

先明确给定的文法G：

• 非终结符：{S, B, C}
• 终结符：{a, b, c}
• 产生式：
  • S → CSB | CSa | a
  • B → b | ε
  • C → c
• 起始符号：S

左推导过程（每次替换最左侧的非终结符） #

目标串是w₁=cccaab，我们一步步推导：

1. S ⇒ CSB （选第一个产生式，先引入C和递归的S，用来生成多个c）
2. CSB ⇒ cSB （用C→c替换最左的C）
3. cSB ⇒ cCSBB （替换最左的S为CSB，继续引入C）
4. cCSBB ⇒ ccSBB （用C→c替换C）
5. ccSBB ⇒ ccCSaBB （这里选S→CSa，不再递归S，因为后面需要生成a）
6. ccCSaBB ⇒ cccSaBB （用C→c替换C）
7. cccSaBB ⇒ cccaaBB （用S→a替换最后一个S，终止递归）
8. cccaaBB ⇒ cccaabB （用B→b替换第一个B）
9. cccaabB ⇒ cccaab （用B→ε替换最后一个B，消除剩余的非终结符）

完整的左推导链：

S ⇒ CSB ⇒ cSB ⇒ cCSBB ⇒ ccSBB ⇒ ccCSaBB ⇒ cccSaBB ⇒ cccaaBB ⇒ cccaabB ⇒ cccaab

推导树（文本结构模拟） #

用层级结构直观展示推导树的父子关系：

S
       / | \
      C  S  B
      |  |  |
      c  S  b
         /|\
        C S B
        | | |
        c S ε
           /|\
          C S a
          | |
          c a

或者用层级列表描述：

• 根节点：S
  • 子节点：C → c
  • 子节点：S
    • 子节点：C → c
    • 子节点：S
      • 子节点：C → c
      • 子节点：S → a
      • 子节点：a
    • 子节点：B → ε
  • 子节点：B → b

简单说下推导思路：目标串有3个c，所以需要3次应用C→c，对应三次通过S的递归产生式引入C；最后一次处理S时选择S→CSa+S→a来生成末尾的两个a；B分别选b和ε来匹配目标串的最后一个b，刚好消除所有非终结符得到最终串。

备注：内容来源于stack exchange，提问作者Sam Kiloz