已知共享终结符的两个确定上下文无关文法，如何构造满足L(G3)=L(G1){L(G2)}*的文法？

嘿，这个问题其实是上下文无关文法（CFG）语言组合里的经典场景，咱们一步步拆解来搞定它～

首先先明确前提：为了避免非终结符冲突，我们默认G1的非终结符集合N1和G2的N2是不相交的。如果它们有重叠（比如两个文法都有非终结符A），只需要把G2里的所有非终结符重命名（比如把X改成X'），同时把G2产生式里的对应非终结符也替换掉，就能保证N1和修改后的N2'不相交了，这一步很重要，不然会出现歧义。

接下来直接给出G3的构造方案：
G3 = (N3, T, P3, S3)，其中：

• N3 = N1 ∪ N2 ∪ {S3}，这里的S3是我们新增的起始非终结符
• 产生式集合P3由三部分组成：
  • 完全保留G1的所有产生式：P1 ⊆ P3
  • 完全保留G2的所有产生式：P2 ⊆ P3
  • 添加两个关键的组合产生式：
    1. S3 → S1：对应「只取G1的串，后面跟零个G2串」的情况
    2. S3 → S3 S2：递归实现闭包——每次在已有的结果（已经是L(G1)(L(G2))^k的串）后面拼接一个G2的串，重复这个过程就能得到任意多个G2串的组合

为什么这个构造是对的？ #

咱们从语言生成的角度看：

• 当我们只用S3 → S1时，生成的就是L(G1)的所有串，满足(L(G2))*里零个串的情况
• 当我们多次应用S3 → S3 S2时，比如先推导S3 → S3 S2 → S1 S2，这就生成了L(G1)L(G2)的串；再推一步就是S3 → S3 S2 → S1 S2 S2，对应L(G1)(L(G2))²，以此类推，递归下去就能覆盖所有n≥0的L(G1)(L(G2))^n，也就是我们要的L(G1)(L(G2))*

举个简单例子验证 #

假设：

• G1的产生式是S1 → a | b，L(G1) = {a, b}
• G2的产生式是S2 → c | d，L(G2) = {c, d}

按照上面的方法构造G3：

• 新增起始符S3
• 产生式包括：

  S3 → S1 | S3 S2
  S1 → a | b
  S2 → c | d
  

生成的语言就是{a, b, ac, ad, bc, bd, acc, acd, bcc, bdd, ...}，完全符合L(G1)(L(G2))*的要求。

内容的提问来源于stack exchange，提问作者de_dust