Haskell Parsec：触动操作员

Question

我有一个由以下BNF定义的逻辑语言。

 formula ::= true
           | false
           | var
           | formula & formula
           | [binder] formula

 binder  ::= var 
           | $var

从本质上讲，这允许使用x & true，[x]x和[$x](x & true)等公式。语义在这里并不重要;但重要的是我在公式之前出现了这些方形括号的表达式，并且在那些方括号内的表达式中，标识符可能会或可能不会以美元符号（$）开头。现在我使用Haskell的Parsec库来帮助我构建这种语言的解析器，详见下文。

module LogicParser where

import System.IO
import Control.Monad
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr
import Text.ParserCombinators.Parsec.Language
import qualified Text.ParserCombinators.Parsec.Token as Token

-- Data Structures
data Formula = LVar String
             | TT
             | FF
             | And Formula Formula
             | Bound Binder Formula
             deriving Show

data Binder = BVar String
             | FVar String
             deriving Show

-- Language Definition
lang :: LanguageDef st
lang =
    emptyDef{ Token.identStart      = letter
            , Token.identLetter     = alphaNum
            , Token.reservedOpNames = ["&", "$", "[", "]"]
            , Token.reservedNames   = ["tt", "ff"]
            }


-- Lexer for langauge
lexer = 
    Token.makeTokenParser lang


-- Trivial Parsers
identifier     = Token.identifier lexer
keyword        = Token.reserved lexer
op             = Token.reservedOp lexer
roundBrackets  = Token.parens lexer
whiteSpace     = Token.whiteSpace lexer

-- Main Parser, takes care of trailing whitespaces
formulaParser :: Parser Formula
formulaParser = whiteSpace >> formula

-- Parsing Formulas
formula :: Parser Formula
formula = andFormula
        <|> formulaTerm

-- Term in a Formula
formulaTerm :: Parser Formula
formulaTerm = roundBrackets formula
            <|> ttFormula
            <|> ffFormula
            <|> lvarFormula
            <|> boundFormula

-- Conjunction
andFormula :: Parser Formula
andFormula = 
    buildExpressionParser [[Infix (op "&" >> return And) AssocLeft]] formulaTerm

-- Bound Formula
boundFormula :: Parser Formula
boundFormula = 
    do  op "["
        v <- var
        op "]"
        f <- formulaTerm
        return $ Bound v f

-- Truth
ttFormula :: Parser Formula
ttFormula = keyword "tt" >> return TT

-- Falsehood
ffFormula :: Parser Formula
ffFormula = keyword "ff" >> return FF

-- Logical Variable
lvarFormula :: Parser Formula
lvarFormula =
    do  v <- identifier
        return $ LVar v

-- Variable
var :: Parser Binder
var = try bvar <|> fvar

-- Bound Variable
bvar :: Parser Binder
bvar =
    do  op "$"
        v <- identifier
        return $ BVar v

-- Free Variable
fvar :: Parser Binder
fvar =
    do  v <- identifier
        return $ FVar v


-- For testing
main :: IO ()
main = interact (unlines . (map stringParser) . lines)

stringParser :: String -> String
stringParser s = 
    case ret of
        Left e ->  "Error: " ++ (show e)
        Right n -> "Interpreted as: " ++ (show n)
    where 
        ret = parse formulaParser "" s

我的问题如下。当美元符号运算符（$）触及方括号时，我得到一个错误，而如果我添加一个空格，解析器工作正常：

如何让解析器识别[$x](x & true)？请注意，仅当两个运算符&和[触摸时，$触及其操作数没有问题。

Answer 1

我不太熟悉Parsec的标记方面，但是从its documentation我认为你需要提供opLetter和可能opStart，因为你提供reservedOp：

opLetter :: ParsecT s u m Char    
此解析器应接受运算符的任何合法尾部字符。请注意，如果语言不支持用户定义的运算符，甚至应该定义此解析器，否则reservedOp解析器将无法正常工作。

特别是默认的opLetter不包括[或]，所以当你认为其中一个应该是op时它表现不正常。

Answer 2

我认为它不喜欢你用方括号作为运算符。我会试试这个：

从"["删除"]"和Token.reservedOpNames
将另一个解析器添加到您的Trivial Parsers：squareBrackets = Token.brackets lexer
将您的boundFormula函数更改为： boundFormula = do v <- squareBrackets var f <- formulaTerm return $ Bound v f

Answer 3

以下是我用Megaparsec（docs，tutorial）编写解析器的方法：

import Text.Megaparsec
import qualified Text.Megaparsec.Char as C
import qualified Text.Megaparsec.Char.Lexer as L
import Control.Monad.Combinators.Expr
import Data.Void

type Parser = Parsec Void String

data Formula = LVar String
             | TT
             | FF
             | Not Formula -- Added to demonstrate `Prefix` of `makeExprParser`
             | And Formula Formula
             | Bound Binder Formula
             deriving Show

data Binder = BVar String
            | FVar String
            deriving Show

Megaparsec也有makeExprParser，但它被转移到一个单独的parser-combinators包：

formula :: Parser Formula
formula = makeExprParser term operators
  where
    term = choice
      [ TT <$ symbol "true"
      , FF <$ symbol "false"
      , LVar <$> var
      , Bound <$> brackets binder <*> parens formula
      ]

    binder = choice
      [ BVar <$> (C.char '$' >> var)
      , FVar <$> var
      ]

    var = lexeme $ some C.letterChar

    operators :: [[Operator Parser Formula]]
    operators =
      [ [ Prefix (Not <$ symbol "¬") ]
      , [ InfixL (And <$ symbol "&") ]
      ]

一些要点：

尽可能使用适用的风格（<$>，<$，$>）。
Megaparsec将一些像many1这样的组合器改名为some。有一个教程，Switch from Parsec to Megaparsec，有助于过渡。（这可能有点过时;我在回答这个问题的过程中发了一封公关。）
当trys和BVars在第一个角色FVar上互斥时，你不需要$。简单地列出BVar解析器就足够了。由于您将找不到以$开头的任何其他有效表达式，因此使用$的失败解析器不是问题。
你的语法没有说明括号后的字面括号或字面括号。因此，为了解析"[$x](x & true)"，您需要在语法中添加明确的括号，或者为 formula ::= ... | '(' formula ')' 或者作为 formula ::= ... | '[' binder ']' '(' formula ')' 如果他们只被允许在那里。我和后者一起去了，但这可能是错的。

继续，

lexeme :: Parser a -> Parser a
lexeme = L.lexeme spaceConsumer

symbol :: String -> Parser String
symbol = L.symbol spaceConsumer

spaceConsumer :: Parser ()
spaceConsumer = L.space C.space1 empty empty

brackets, parens :: Parser a -> Parser a
brackets = between (symbol "[") (symbol "]")
parens = between (symbol "(") (symbol ")")

最后几点，

使用between将解析器包装在brackets或braces中。
Parsec令牌解析器有点复杂，因为它们要求您指定令牌是什么以及空白是什么等等。 Megaparsec lexeme解析器具有一些复杂性，但您可以使用empty :: Alternative f => f a省略不相关的部分（例如行注释和块注释）。
解析器组合器中的空格很棘手。确保所有解析器都是lexeme解析器（例如symbol "foo"，lexeme $ some C.letterChar）或lexeme解析器的组合。如果你在已经是lexeme解析器的东西上使用lexeme，你做错了什么，如果你忘记在某些东西上使用lexeme，你就有可能在你想要允许的地方禁止使用空格。我没有在lexeme附近使用C.char '$'。
总是存在极端情况，例如：开头的空白： > parseTest formula " [$x](x & true) " 1:1: | 1 | [$x](x & true) | ^^^^^ unexpected " [$x]" expecting "false", "true", '[', '¬', or letter 如果你想彻底断言你的解析器在所有正确的位置允许空格，你可以构建一个“丑陋的打印机”，对于任意语法树，在允许的地方插入任意空格。那么你的属性是解析一个丑陋的语法树应该产生相同的语法树。
Megaparsec解析错误看起来非常好。如果你使用<?>算子（也可以在Parsec中使用），它们看起来更好。

Haskell Parsec：触动操作员

问题描述投票：1回答：3

3个回答

最新问题

Haskell Parsec：触动操作员

问题描述 投票：1回答：3

3个回答

最新问题

问题描述投票：1回答：3