如何将CNF范式解析树转换为原始文法的解析树？

核心思路：转换阶段保留双向映射轨迹 #

不要等生成CNF解析树后再逆向推导，必须在EBNF转CNF的每一步操作中，同步记录转换的反向映射关系：

• 处理EBNF的{B}（重复）时，生成的临时非终结符（比如A_REP，规则为A_REP → B | B A_REP），要标记它对应原始文法中A规则下的{B}结构；
• 拆分长规则（比如A → B C D拆为A → B X1、X1 → C D）时，记录X1是A规则中C D片段的临时替代节点；
• 处理空产生式、单非终结符替换时，同样为每个临时非终结符绑定对应的原始文法元素。

基于这个映射表，遍历CNF解析树时可直接反向还原：

1. 用DFS遍历CNF树，遇到临时非终结符节点时，根据映射表替换为对应的原始EBNF结构（比如把A_REP节点展开为{B}的重复序列）；
2. 对于拆分出的中间节点（如X1），直接将其子节点合并到父节点的原始规则位置，扁平化临时节点。

歧义问题的针对性处理 #

重复结构的区分 #

针对你提到的A→B {B} {B}这类场景，转换时要为每个重复块生成唯一标识的临时非终结符：

• 比如第一个{B}对应A_REP1，第二个对应A_REP2，同时在映射表中标记它们各自归属原始规则的哪个重复块；
• 还原解析树时，根据临时非终结符的唯一标识，将B节点准确归到对应的重复组中，避免混淆。

消歧规则的适配 #

如果原始文法带有消歧规则（优先级、结合性等），要在CNF转换阶段就嵌入消歧逻辑：

• 比如处理左结合表达式时，生成的临时非终结符要标记结合方向（如EXP_LEFT），CYK解析时优先选择符合消歧规则的解析树分支；
• 还原解析树时，根据消歧标记保留正确结构，丢弃不符合规则的歧义分支。

间接左递归的兼容方案 #

你选择CNF方案规避LL(k)的间接左递归问题是合理的，转换时需注意：

• 处理间接左递归（如A→B→C→A）生成的临时非终结符，要记录其与原始递归链的映射关系（比如A_LOOP对应原始的递归结构）；
• 还原解析树时，将临时递归节点替换回原始的非终结符递归结构，保持与原始文法的一致性。

具体实现步骤 #

1. 扩展转换模块：在EBNF转CNF的每个步骤（处理重复、可选、选择、拆分长规则、消除左递归）中，维护ConversionMap字典，键为临时非终结符，值为包含原始文法元素、父规则、结构类型（重复/可选/拆分）的元组；
2. CNF解析树后处理：
   • 遍历CNF解析树，逐个节点查询ConversionMap；
   • 若为临时重复节点，递归收集所有子节点的B，打包成原始的{B}结构；
   • 若为拆分的中间节点，将子节点直接合并到父节点对应位置，删除临时节点；
   • 若为单非终结符替换节点，直接替换为原始非终结符；
3. 歧义分支过滤：若CYK生成多棵解析树，依据原始文法的消歧规则（如优先级表）筛选出符合要求的树后再进行还原。

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