解析FParsec中的简单类型

Question

我正在尝试使用FParsec解析标准的简单类型(在lambda演算的意义上),但是我很难从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,等等.但是如何防止这种循环呢？

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

Answer 1

当您使用 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"