Это разумное основание для библиотеки комбинатора синтаксического анализатора? - PullRequest
Новая
       14

Это разумное основание для библиотеки комбинатора синтаксического анализатора?

2 голосов
/ 11 ноября 2010

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

open LazyList 

type State<'a, 'b> (input:LazyList<'a>, data:'b) =
    member this.Input = input
    member this.Data = data

type Result<'a, 'b, 'c> =
| Success of 'c * State<'a, 'b>
| Failure of string * State<'a, 'b>

type Parser<'a,'b, 'c> = State<'a, 'b> -> Result<'a, 'b, 'c>

let (>>=) left right state =
    match left state with
    | Success (result, state) -> (right result) state
    | Failure (message, _) -> Result<'a, 'b, 'd>.Failure (message, state)

let (<|>) left right state =
    match left state with
    | Success (_, _) as result -> result
    | Failure (_, _) -> right state

let (|>>) parser transform state =
    match parser state with
    | Success (result, state) -> Success (transform result, state)
    | Failure (message, _) -> Failure (message, state)

let (<?>) parser errorMessage state =
    match parser state with
    | Success (_, _) as result -> result
    | Failure (_, _) -> Failure (errorMessage, state)                     

type ParseMonad() =
    member this.Bind (f, g) = f >>= g
    member this.Return x s = Success(x, s)
    member this.Zero () s = Failure("", s)                           
    member this.Delay (f:unit -> Parser<_,_,_>) = f()

let parse = ParseMonad()

Возврат

Удивительно, но для реализации чего-либо не потребовалось слишком много кодаВы описываете.Это немного неаккуратно, но, кажется, работает довольно хорошо. 

let (>>=) left right state =
    seq {
        for res in left state do
            match res with
            | Success(v, s) ->
                let v  = 
                    right v s 
                    |> List.tryFind (
                        fun res -> 
                            match res with 
                            | Success (_, _) -> true 
                            | _ -> false
                    ) 
                match v with
                | Some v -> yield v
                | None -> ()
    } |> Seq.toList

let (<|>) left right state = 
    left state @ right state

Backtracking Part 2

Переключение кода для использования отложенных списков и оптимизированной рекурсии по хвостовому вызову. 

let (>>=) left right state =
    let rec readRight lst =
        match lst with
        | Cons (x, xs) ->
            match x with
            | Success (r, s) as q -> LazyList.ofList [q]                     
            | Failure (m, s) -> readRight xs
        | Nil -> LazyList.empty<Result<'a, 'b, 'd>>
    let rec readLeft lst =
        match lst with
        | Cons (x, xs) ->
            match x with
            | Success (r, s) -> 
                match readRight (right r s) with 
                | Cons (x, xs) ->
                    match x with
                    | Success (r, s) as q -> LazyList.ofList [q]                     
                    | Failure (m, s) -> readRight xs
                | Nil -> readLeft xs   
            | Failure (m, s) -> readLeft xs
        | Nil -> LazyList.empty<Result<'a, 'b, 'd>>
    readLeft (left state)

let (<|>) (left:Parser<'a, 'b, 'c>) (right:Parser<'a, 'b, 'c>) state = 
    LazyList.delayed (fun () -> left state) 
    |> LazyList.append 
    <| LazyList.delayed (fun () -> right state)

1 Ответ

2 голосов
/ 11 ноября 2010

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

Backtracking. В вашей реализации синтаксический анализатор может либо потерпеть неудачу (случай Failure), либо выдать ровно один результат (случай Success). Альтернативный вариант - сгенерировать ноль или более результатов (например, представить результаты как seq<'c>). Извините, если это то, что вы уже рассмотрели :-), но в любом случае ...

Разница в том, что ваш парсер всегда следует за первым возможным вариантом. Например, если вы напишите что-то вроде следующего: 

let! s1 = (str "ab" <|> str "a")
let! s2 = str "bcd"

Использование вашей реализации приведет к сбою для ввода "abcd". Он выберет первую ветвь оператора <|>, которая затем обработает первые два символа, и следующий синтаксический анализатор в последовательности не удастся. Реализация, основанная на последовательностях, сможет вернуться и следовать по второму пути в <|> и проанализировать ввод.

Объединение. Другая идея, которая приходит мне в голову, заключается в том, что вы также можете добавить Combine член к вашему компоновщику вычислений синтаксического анализатора. Это немного неуловимо (потому что вам нужно понять, как переводятся выражения вычислений), но иногда это может быть полезно. Если вы добавите: 

member x.Combine(a, b) = a <|> b
member x.ReturnFrom(p) = p

Затем вы можете красиво написать рекурсивные парсеры: 

let rec many p acc = 
  parser { let! r = p                  // Parse 'p' at least once
           return! many p (r::acc)     // Try parsing 'p' multiple times
           return r::acc |> List.rev } // If fails, return the result
...