在FParsec中解析简单类型 [英] Parsing simple types in FParsec

问题描述

我正在尝试使用FParsec解析标准的简单类型(就Lambda演算而言)，但是我很难从Lex/Yacc样式转换为FParsec中使用的样式，特别是在递归定义方面./p>

我尝试解析的类型的示例是:

• o
• 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，依此类推.但是如何防止这种循环呢?

我对库的惯用用法以及对我尝试的解决方案的更正感兴趣.

解决方案

使用FParsec时，您需要在

I'm trying to parse standard simple types (in the sense of lambda calculus) using FParsec, but I've having difficulty going from a Lex/Yacc style to that used in FParsec, specifically with respect to recursive definitions.

Examples of the types I am trying to parse are:

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

And here is my attempt:

    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"`

When I load this into the interactive the last line causes a stack overflow (ironically quite hard to search for these days). I can imagine why, given that there are recursive references, but I would have thought the one token lookahead would have prevented following the first (bracketed) choice in stype. I assume therefore that it must be choosing arr, which chooses stype, and so on. But how to prevent this loop?

I'm interested in comments on idiomatic use of the library as well as corrections to my attempted solution.

解决方案

When you work with FParsec you need to parse sequences with the help of the sequence combinators instead of left-recursion. In your case you could for example use the sepBy1 combinator:

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"

这篇关于在FParsec中解析简单类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！