f# - F# 中的上下文敏感数据处理

Question

我最近完成了一个生成字符串列表的项目，我想知道执行此操作的最佳方法。

字符串生成是上下文敏感的，以确定它是否可以接受(这是游戏中的一系列游戏，所以你必须知道最后一次游戏是什么)

我这样做的方法是使用一个传递上下文参数和术语的函数，如果它是可接受的，它递归地继续，如果不是它终止(因为没有更多的字符串可以接受。)函数还收到一个“长度”参数以确保它最终终止

基本上这是生成语言接受的每个可能的字符串(一定长度)。

现在，我已经开始工作了，甚至相当干净利落，但我想知道是否有更好的方法来做到这一点。具体来说，“状态机”monad 能否很好地生成上下文相关语法？或至少类似的东西？这个问题似乎很简单，想要启动类似 parsec 的东西，是否有其他结构可以有效地操纵语言？

如有任何想法，我们将不胜感激。

Answer 1

我觉得这个问题看起来很有趣，所以我尝试了几种不同的实现方法。下面的代码是最有前途的方法。我认为它解决了所描述的问题，尽管我不确定一些细节。

基本上它允许一种形式的上下文相关语法，但只是一种非常简单的形式，其中每个产生式只能依赖于前一个符号。下面的代码构建了一些组合器，这些组合器允许将产生式非常直接地编码为“生成器”，并在幕后处理长度限制。

type sym = Xa | Xb | Xc          // The terminal symbols 
type word = sym list             // A string of terminals

type gen = int -> sym list seq   // Generate words up to the given length

/// Passes the previous symbol to a generator, after checking the length.
let (+>) : sym  -> (sym -> gen) -> gen = 
    fun x g l -> if l<=0 then Seq.empty 
                         else seq { for xs in g x (l-1) -> x :: xs }

let nil _ = seq { yield [] }                    // Generate just the empty word            
let (|||) xs ys l = Seq.append (xs l) (ys l)    // Union of two generators
let notAccepted _ = Seq.empty                   // Don't generate anything

let tryAll g = Xa +> g ||| Xb +> g ||| Xc +> g  // Run g starting with any sym

// Generators for non-terminals.  Each takes the previous symbol as an argument,
// and generates a (possibly empty) sequence of lists of symbols.
let rec gR = function Xa ->  Xb +> gS ||| Xc +> gR  ||| nil  
                    | Xc ->  Xb +> gS                        | _ -> notAccepted
    and gS = function Xb ->  Xa +> gR                        | _ -> notAccepted


let genTop = tryAll gR  // The top level generator begins with gR with any sym

let words = genTop 4    // Generate words up to length 4
// val words : seq<sym list> 
//           = seq [[Xa; Xb; Xa]; [Xa; Xc; Xb; Xa]; [Xa]; [Xc; Xb; Xa]]