Контекстно-зависимая обработка данных в F # - PullRequest
Новая
       15

Контекстно-зависимая обработка данных в F #

3 голосов
/ 15 сентября 2010

Я недавно закончил проект, в котором я генерировал списки строк, и мне было интересно, как лучше всего это сделать.

Генерация строки была контекстно-зависимой, чтобы определить, является ли она приемлемой (это была последовательность игр в игре, поэтому вы должны были знать, какой была последняя игра)

То, как я это сделал, было с функцией, которой был передан параметр контекста и термин, и если это было приемлемо, то рекурсивно продолжалось, если это не было завершено (так как никакая дальнейшая строка не могла быть приемлемой.) Функция также получил параметр "length", чтобы убедиться, что он в конце концов завершится

в основном это генерирует каждую возможную строку, принятую языком (определенной длины).

Теперь я получил это на работу, даже довольно хорошо и чисто, но мне было интересно, есть ли лучший способ сделать это. В частности, хорошо ли будет работать монада «конечного автомата» при генерации контекстно-зависимой грамматики? или что-то подобное хотя бы? Кажется, проблема состоит в простом желании запустить что-то вроде parsec. Существуют ли другие структуры, которые эффективны в манипулировании языками?

Любые мысли приветствуются.

1 Ответ

0 голосов
/ 02 апреля 2011

Мне показалось, что эта проблема выглядит интересной, поэтому я попробовал несколько разных способов ее реализации. Код ниже является подходом, который кажется наиболее перспективным. Я думаю, что это решает проблему, как описано, хотя я не был уверен в некоторых деталях.

По сути, он допускает форму контекстно-зависимых грамматик, но только довольно простую форму, где каждое произведение может зависеть только от предыдущего символа. Приведенный ниже код создает некоторые комбинаторы, которые позволяют кодировать произведения очень непосредственно как «генераторы», и которые заботятся об ограничении длины за сценой. 

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]]
...