星号规则场景下DFA转无扩展非终结符正则文法的算法问询

结论先行 #

既存在可以直接生成无扩展非终结符结果的形式化算法，这类消去多余非终结符的操作也属于可标准化的编译优化范畴，二者并不冲突。

具体说明 #

1. 为什么龙书的默认算法会生成额外非终结符 #

龙书给出的DFA转正则文法算法是严格面向标准右线性正则文法设计的，规则要求每个DFA状态必须对应一个独立的非终结符，且每个产生式右部最多包含一个非终结符且只能位于最末尾。
你给出的示例中DFA共有2个状态：

• State0 对应起始/终态非终结符Statements
• State1 作为中间状态，自然会被分配独立的非终结符Extend_NT，也就出现了你看到的额外非终结符结果。

2. 直接生成目标文法的算法逻辑 #

如果我们允许生成扩展右线性正则文法（产生式右部允许多个终结符拼接后接非终结符），可以直接调整生成逻辑跳过中间非终结符的分配：
当遍历状态转换链路时，若某个中间状态满足两个条件：

• 仅存在唯一的出边
• 出边跳转目标为已分配了非终结符的状态（起始/终态优先）
  则不需要为该中间状态分配独立非终结符，直接将前后两段转换序列合并为一个产生式即可。

对应到你的示例：

1. State0作为起始+终态，首先生成Statements -> ε
2. State0的转换输入Statement到State1，与State1的唯一转换输入;到State0直接合并，生成Statements -> Statement ';' Statements
   整个过程完全不会引入Extend_NT。

3. 消去额外非终结符属于标准化编译优化 #

如果严格遵循龙书的标准算法先生成带扩展非终结符的文法，也可以通过形式化的产生式替换规则消去多余非终结符，不属于自定义的工程trick：
对于任意非终结符X，如果满足：

• 仅存在唯一的产生式：X -> α Y（α为终结符序列，Y为固定非终结符）
• X不是起始非终结符，也不是终态对应的非终结符
  则可以直接把所有产生式中引用X的位置替换为α Y，再删除X的相关产生式即可。

你示例中的Extend_NT完全符合上述条件，直接替换就能得到目标结果。

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