Ví dụ về trình phân tích cú pháp đầy đủ với parsec?

Question

Tôi đang cố gắng làm cho một trình phân tích cú pháp cho một ngôn ngữ chức năng đơn giản, giống như Caml, nhưng tôi dường như bị mắc kẹt với những thứ đơn giản nhất.

Vì vậy, tôi muốn biết nếu có một số ví dụ hoàn chỉnh hơn về các trình phân tích cú pháp parsec, thứ gì đó vượt ra ngoài "đây là cách bạn phân tích cú pháp 2 + 3". Đặc biệt là các cuộc gọi chức năng theo thuật ngữ và tương tự.

Và tôi đã đọc "Viết cho bạn một sơ đồ", nhưng cú pháp của lược đồ khá đơn giản và không thực sự giúp ích cho việc học.

Các vấn đề nhất tôi có là làm thế nào để sử dụng try, <|> và choice đúng, bởi vì tôi thực sự không hiểu tại sao parsec bao giờ có vẻ phân tích a(6) như một cuộc gọi chức năng sử dụng phân tích cú pháp này:

expr = choice [number, call, ident] 

number = liftM Number float <?> "Number" 

ident = liftM Identifier identifier <?> "Identifier" 

call = do 
    name <- identifier 
    args <- parens $ commaSep expr 
    return $ FuncCall name args 
    <?> "Function call" 

EDIT thêm một số mã để hoàn thành, mặc dù điều này là thực sự không phải là điều tôi hỏi:

AST.hs

module AST where 

data AST 
    = Number Double 
    | Identifier String 
    | Operation BinOp AST AST 
    | FuncCall String [AST] 
    deriving (Show, Eq) 

data BinOp = Plus | Minus | Mul | Div 
    deriving (Show, Eq, Enum) 

Lexer.hs

module Lexer (
      identifier, reserved, operator, reservedOp, charLiteral, stringLiteral, 
      natural, integer, float, naturalOrFloat, decimal, hexadecimal, octal, 
      symbol, lexeme, whiteSpace, parens, braces, angles, brackets, semi, 
      comma, colon, dot, semiSep, semiSep1, commaSep, commaSep1 
    ) where 

import Text.Parsec 
import qualified Text.Parsec.Token as P 
import Text.Parsec.Language (haskellStyle) 

lexer = P.makeTokenParser haskellStyle 

identifier = P.identifier lexer 
reserved = P.reserved lexer 
operator = P.operator lexer 
reservedOp = P.reservedOp lexer 
charLiteral = P.charLiteral lexer 
stringLiteral = P.stringLiteral lexer 
natural = P.natural lexer 
integer = P.integer lexer 
float = P.float lexer 
naturalOrFloat = P.naturalOrFloat lexer 
decimal = P.decimal lexer 
hexadecimal = P.hexadecimal lexer 
octal = P.octal lexer 
symbol = P.symbol lexer 
lexeme = P.lexeme lexer 
whiteSpace = P.whiteSpace lexer 
parens = P.parens lexer 
braces = P.braces lexer 
angles = P.angles lexer 
brackets = P.brackets lexer 
semi = P.semi lexer 
comma = P.comma lexer 
colon = P.colon lexer 
dot = P.dot lexer 
semiSep = P.semiSep lexer 
semiSep1 = P.semiSep1 lexer 
commaSep = P.commaSep lexer 
commaSep1 = P.commaSep1 lexer 

Parser.hs

module Parser where 

import Control.Monad (liftM) 
import Text.Parsec 
import Text.Parsec.String (Parser) 
import Lexer 
import AST 

expr = number <|> callOrIdent 

number = liftM Number float <?> "Number" 

callOrIdent = do 
    name <- identifier 
    liftM (FuncCall name) (parens $ commaSep expr) <|> return (Identifier name) 

Answer 1

Hmm,

*Expr> parse expr "" "a(6)" 
Right (FuncCall "a" [Number 6.0]) 

rằng phần làm việc cho tôi sau khi điền các mảnh còn thiếu.

Chỉnh sửa: Tôi điền vào các phần còn thiếu bằng cách viết trình phân tích cú pháp số float của riêng tôi, có thể phân tích cú pháp số nguyên. Mặt khác, trình phân tích cú pháp float phân tích cú pháp từ Text.Parsec.Token chỉ phân tích cú pháp các phần tử bằng phần phân số hoặc số mũ, do đó không phân tích được cú pháp "6".

Tuy nhiên,

*Expr> parse expr "" "variable" 
Left (line 1, column 9): 
unexpected end of input 
expecting "(" 

khi cuộc gọi không thành sau khi đã phân tích một định danh, một phần của đầu vào được tiêu thụ, do đó ident không cố gắng, và phân tích tổng thể thất bại. Bạn có thể a) làm cho nó try call trong danh sách lựa chọn expr, do đó cuộc gọi không thành công mà không tiêu thụ đầu vào hoặc b) viết một cuộc gọi phân tích cú phápOrIdent để sử dụng trong expr, ví dụ:

callOrIdent = do 
    name <- identifier 
    liftM (FuncCall name) (parens $ commaSep expr) <|> return (Identifier name) 

giúp tránh try và do đó có thể hoạt động tốt hơn.

Answer 2

Tôi đã viết một loạt ví dụ về cách phân tích Chữ số La Mã bằng parsec. Nó khá cơ bản nhưng bạn hoặc những người mới khác có thể tìm thấy nó hữu ích:

https://github.com/russell91/roman

Answer 3

Cuốn sách Write Yourself a Scheme in 48 Hours là một tuyệt vời, trong cái nhìn tổng quan chiều sâu và hướng dẫn các chức năng Parsec của. Nó hướng dẫn bạn qua tất cả mọi thứ với các ví dụ sâu, và cuối cùng bạn đã thực hiện một phần khá quan trọng của lược đồ trong một trình thông dịch parsec.