Разбор простых типов в FParsec - PullRequest
Новая
       13

Разбор простых типов в FParsec

5 голосов
/ 20 июля 2011

Я пытаюсь проанализировать стандартные простые типы (в смысле лямбда-исчисления), используя FParsec, но у меня возникают трудности при переходе от стиля Lex / Yacc к стилю, используемому в FParsec, особенно в отношении рекурсивных определений.

Примеры типов, которые я пытаюсь проанализировать:

  • о
  • o -> o
  • (o -> o -> o) -> o

А вот моя попытка: 


    type SType =
      | Atom
      | Arrow of SType * SType

    let ws = spaces
    let stype, styperef = createParserForwardedToRef()

    let atom = pchar 'o' .>> ws |>> (fun _ -> Atom)

    let arrow = pipe2 (stype .>> (pstring "->" .>> ws)) 
                      stype
                      (fun t1 t2 -> Arrow (t1,t2))

    let arr = parse {
                let! t1 = stype
                do!  ws
                let! _  = pstring "->"
                let! t2 = stype
                do!  ws
                return Arrow (t1,t2)
              }

    styperef := choice [ pchar '(' >>. stype .>> pchar ')';
                         arr;
                         atom ]

    let _ = run stype "o -> o"`

Когда я загружаю это в интерактив, последняя строка вызывает переполнение стека (по иронии судьбы довольно трудно искать в эти дни). Я могу себе представить, почему, учитывая, что есть рекурсивные ссылки, но я бы подумал, что однозначный прогноз не позволил бы после первого (заключенного в скобки) выбора в stype. Поэтому я предполагаю, что он должен выбирать arr, который выбирает stype и так далее. Но как предотвратить этот цикл?

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

Ответы [ 2 ]

4 голосов
/ 21 июля 2011

Когда вы работаете с FParsec, вам нужно анализировать последовательности с помощью комбинаторов последовательностей вместо левой рекурсии. В вашем случае вы можете, например, использовать комбинатор sepBy1: 

open FParsec

type SType =
     | Atom
     | Arrow of SType * SType

let ws = spaces : Parser<unit, unit>
let str_ws s = pstring s >>. ws

let stype, stypeRef = createParserForwardedToRef()

let atom = str_ws "o" >>% Atom

let elem = atom <|> between (str_ws "(") (str_ws ")") stype

do stypeRef:= sepBy1 elem (str_ws "->") 
              |>> List.reduceBack (fun t1 t2 -> Arrow(t1, t2))

let _ = run stype "o -> o"
0 голосов
/ 20 июля 2011

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

type SType = 
    | Atom 
    | Arrow of SType * SType

type UserState = unit
type Parser<'t> = Parser<'t, UserState>


let ws = spaces

let atom : Parser<_> = pchar 'o' .>> ws |>> (fun _ -> Atom)

let rec term =
    parse {
        // Force something to come before another term.  Either
        // an atom, or a term in parens.
        let! first = choice [atom;
                             (pstring "(" .>> ws) >>. term .>> 
                              (pstring ")" .>> ws)]

        // Check if this is an arrow.  If not, just return first.
        let! res = choice [((pstring "->") .>> ws) >>. term |>> (fun x ->
                               Arrow (first, x));
                           preturn first]
        return res
        }
...