Phân tích các loại đơn giản trong FParsec

Question

Tôi đang cố gắng phân tích các loại đơn giản chuẩn (theo nghĩa lambda) bằng FParsec, nhưng tôi gặp khó khăn khi chuyển từ kiểu Lex/Yacc sang FParsec, đặc biệt với sự tôn trọng để định nghĩa đệ quy.

Ví dụ về các loại Tôi cố gắng để phân tích cú pháp là:

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

Và đây là nỗ lực của tôi:

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

Khi tôi tải ứng dụng này vào tương tác ve dòng cuối cùng gây ra một tràn ngăn xếp (trớ trêu thay khá khó để tìm kiếm những ngày này). Tôi có thể tưởng tượng lý do tại sao, cho rằng có các tham chiếu đệ quy, nhưng tôi đã nghĩ rằng một trong những lookahead mã thông báo sẽ có ngăn chặn sau sự lựa chọn đầu tiên (bracketed) trong stype. Do đó, tôi giả định rằng nó phải chọn arr, trong đó chọn stype, v.v. Nhưng làm thế nào để ngăn chặn vòng lặp này?

Tôi quan tâm đến nhận xét về việc sử dụng thành ngữ của thư viện cũng như các chỉnh sửa đối với giải pháp đã cố gắng của tôi.

Answer 1

Khi bạn làm việc với FParsec, bạn cần phải phân tích cú pháp chuỗi với sự giúp đỡ của sequence combinators thay vì đệ quy trái. Trong trường hợp của bạn, bạn có thể ví dụ như sử dụng 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" 

Answer 2

Điều này chạy, nhưng có thể bị tấn công với nhau quá nhiều. Công cụ type Parser... là từ tài liệu FParsec để tránh lỗi trình biên dịch.

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 
     }