有沒有把BNF翻譯成Parsec程序的技巧？

的BNF那場比賽的函數調用鏈（如x(y)(z)...）：有沒有把BNF翻譯成Parsec程序的技巧？

expr = term T 
T = (expr) T 
     | EMPTY 
term = (expr) 
     | VAR

它翻譯成秒差距的程序，看起來很棘手。

term :: Parser Term 
term = parens expr <|> var 

expr :: Parser Term 
expr = do whiteSpace 
      e <- term 
      maybeAddSuffix e 
    where addSuffix e0 = do e1 <- parens expr 
          maybeAddSuffix $ TermApp e0 e1 
     maybeAddSuffix e = addSuffix e 
          <|> return e

您能否列出關於將BNF轉換爲Parsec程序的所有設計模式？

來源

2015-03-03 Ghjhdf

這不回答你的問題，但你*的威力*感興趣的快樂：https://www.haskell.org/happy/這是一個程序它讀取一個BNF規範並生成一個Haskell解析器。 – MathematicalOrchid 2015-03-03 15:03:33

你的問題之一是BNF語法通常用於描述語言標記，但是你有一個基於Char的解析器，這意味着你必須在一個步驟中進行標記（解析標記）和解析你感興趣的實際語言。 – Cubic 2015-03-03 15:34:36

最簡單的認爲你可以做的，如果你的語法是相當大的只是使用Alex/Happy組合。它的使用相當簡單，直接接受BNF格式 - 不需要人工翻譯 - 也許最重要的是，生成快速的解析器/詞法分析器。

如果你已經習慣使用parsec（或者你在做這個學習練習），我覺得在兩個階段做起來更容易一些;先解析，然後解析。 Parsec將同時做到這一點！

首先寫入適當類型：

{-# LANGUAGE LambdaCase #-} 

import Text.Parsec 
import Text.Parsec.Combinator 
import Text.Parsec.Prim 
import Text.Parsec.Pos 
import Text.ParserCombinators.Parsec.Char 
import Control.Applicative hiding ((<|>)) 
import Control.Monad 

data Term = App Term Term | Var String deriving (Show, Eq) 

data Token = LParen | RParen | Str String deriving (Show, Eq) 

type Lexer = Parsec [Char]() -- A lexer accepts a stream of Char 
type Parser = Parsec [Token]() -- A parser accepts a stream of Token

解析單令牌是簡單的。爲了簡單起見，變量是一個或多個字母。無論你喜歡，你當然可以改變它。

oneToken :: Lexer Token 
oneToken = (char '(' >> return LParen) <|> 
      (char ')' >> return RParen) <|> 
      (Str <$> many1 letter)

解析整個令牌流只是解析單個標記多次，可以用空格分隔：

lexer :: Lexer [Token] 
lexer = spaces >> many1 (oneToken <* spaces)

注spaces的位置：這樣一來，白色的空間，在開始接受字符串的結尾。

由於Parser使用自定義令牌類型，所以必須使用自定義satisfy函數。幸運的是，這與現有的滿足幾乎相同。

satisfy' :: (Token -> Bool) -> Parser Token 
satisfy' f = tokenPrim show 
         (\src _ _ -> incSourceColumn src 1) 
         (\x -> if f x then Just x else Nothing)

然後，我們可以爲每個原始令牌編寫解析器。

lparen = satisfy' $ \case { LParen -> True ; _ -> False } 
rparen = satisfy' $ \case { RParen -> True ; _ -> False } 
strTok = (\(Str s) -> s) <$> (satisfy' $ \case { Str {} -> True ; _ -> False })

正如你可能想象的那樣，parens對我們的目的會很有用。寫起來非常簡單。

parens :: Parser a -> Parser a 
parens = between lparen rparen

現在有趣的部分。

term, expr, var :: Parser Term 

term = parens expr <|> var 

var = Var <$> strTok

這兩個應該是相當明顯的給你。

Parec包含組合子option和optionMaybe，當您需要「可能做某事」時它們非常有用。

expr = do 
    e0 <- term 
    option e0 (parens expr >>= \e1 -> return (App e0 e1))

最後一行意味着 - 嘗試應用給option解析器 - 如果失敗，而不是返回e0。

測試你可以這樣做：

tokAndParse = runParser (lexer <* eof)() "" >=> runParser (expr <* eof)() ""

的eof連接到每個解析器是確保整個輸入被消耗;如果有額外的尾隨字符，字符串不能成爲語法的成員。請注意 - 您的示例x(y)(z)實際上並不在您的語法中！

>tokAndParse "x(y)(z)" 
Left (line 1, column 5): 
unexpected LParen 
expecting end of input

但是以下

>tokAndParse "(x(y))(z)" 
Right (App (App (Var "x") (Var "y")) (Var "z"))

來源

2015-03-03 17:18:40 user2407038

有沒有把BNF翻譯成Parsec程序的技巧？

回答

相關問題