有没有把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程序的技巧？

回答

相关问题