如何在纯R中从BNF上下文无关文法生成完整词性序列

问题背景 #

我需要从以巴科斯-诺尔范式（Backus-Naur Form，BNF）编写的上下文无关文法中生成词性序列的完整列表。此前测试了gramEvol包的CreateGrammar、GrammarRandomExpression函数，但该方法仅能随机生成序列，无法输出全量结果。希望能在纯R中实现更规范优雅的对应功能，现有参考代码如下：

sequences <- GenerateSequencesFromBnf()
 
GenerateSequencesFromBnf <- function(){
  library(gramEvol)
  rules <- list(expr = gsrule("<det>.<adj>.<noun>.<core>"),
                core = gsrule("NOUN"),
                det = gsrule("", "DET"),
                adj = gsrule("", "ADJ", "<adj>.ADJ"),
                noun = gsrule("", "NOUN", "<noun>.NOUN")
                )
  grammar <- CreateGrammar(rules)
  sequences <- unique(unlist(GrammarRandomExpression(grammar, 10)))
  return(sequences)
}

实现方案 #

注意事项 #

你给出的文法中<adj>和<noun>为递归规则，不加限制的前提下会生成无限长的序列，因此实现时需要指定最大展开深度，避免程序进入死循环。

纯R全量生成代码 #

# 全量生成BNF序列的主函数，max_depth为递归展开的最大深度
GenerateFullBnfSequences <- function(max_depth = 3) {
  # 定义BNF规则，键为非终结符，值为对应展开选项列表
  rules <- list(
    expr = list(c("<det>", ".", "<adj>", ".", "<noun>", ".", "<core>")),
    core = list("NOUN"),
    det = list("", "DET"),
    adj = list("", "ADJ", c("<adj>", ".", "ADJ")),
    noun = list("", "NOUN", c("<noun>", ".", "NOUN"))
  )
  
  # 递归展开辅助函数
  expand_symbol <- function(symbol, depth_left) {
    # 到达最大深度、或者是终结符（不在规则键中）直接返回
    if (depth_left <= 0 || !symbol %in% names(rules)) {
      return(list(symbol))
    }
    results <- c()
    # 遍历该非终结符的所有展开规则
    for (rule in rules[[symbol]]) {
      parts_expanded <- list(c())
      # 展开规则中的每一个符号
      for (part in rule) {
        part_results <- expand_symbol(part, depth_left - 1)
        # 做笛卡尔积拼接所有可能的组合
        new_parts <- c()
        for (p in parts_expanded) {
          for (pr in part_results) {
            new_parts <- c(new_parts, list(c(p, pr)))
          }
        }
        parts_expanded <- new_parts
      }
      # 拼接成完整字符串
      for (pe in parts_expanded) {
        results <- c(results, paste0(pe, collapse = ""))
      }
    }
    # 去重后返回
    return(unique(results))
  }
  
  # 从起始符号expr开始展开
  all_sequences <- expand_symbol("expr", max_depth)
  # 过滤掉空序列（如果有需要可以调整）
  all_sequences <- all_sequences[all_sequences != ""]
  return(all_sequences)
}

# 调用示例，最大展开深度设为3
full_seqs <- GenerateFullBnfSequences(max_depth = 3)
print(full_seqs)

代码说明 #

• 核心采用递归回溯+笛卡尔积组合的逻辑，遍历所有符合展开深度限制的规则组合
• 自带去重逻辑，无需额外处理重复序列
• 可通过调整max_depth参数控制生成序列的最大长度，适配不同的文法规则需求
• 不依赖gramEvol等第三方包，纯R实现可直接运行

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