Блог

У меня есть логический язык, определенный следующим BNF.

  formula ::= true
           | false
           | var
           | formula amp; formula
           | [binder] formula

 binder  ::= var 
           | $var
  

По сути, это позволяет использовать такие формулы, как x amp; true , [x]x и [$x](x amp; true) . Семантика здесь не важна; но важно то, что у меня есть эти выражения в квадратных скобках, появляющиеся перед формулами, и внутри этих выражений в квадратных скобках идентификаторам может предшествовать знак доллара ( $ ), а может и не предшествовать. Теперь я использовал библиотеку Parsec от Haskell, чтобы помочь мне создать анализатор для этого языка, подробно описанный ниже.

 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 = ["amp;", "$", "[", "]"]
            , 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 "amp;" >> 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 amp; true) ? Обратите внимание, что у него нет проблем с amp; касанием его операндов, только когда соприкасаются два оператора [ и $ .

Я не очень знаком со стороной Parsec с токенами, но из его документации я думаю, что вам нужно предоставить opLetter и, возможно opStart , поскольку вы предоставляете reservedOp :

 opLetter :: ParsecT s u m Char    
  

Этот анализатор должен принимать любые допустимые конечные символы операторов. Обратите внимание, что этот анализатор должен быть определен даже в том случае, если язык не поддерживает определяемые пользователем операторы, иначе анализатор reservedOp не будет работать корректно.

В частности, по умолчанию opLetter не включает [ or ] , поэтому он ведет себя неустойчиво, когда вы думаете, что одним из них должен быть op.

Я думаю, ему не нравится, что у вас есть квадратные скобки в качестве операторов. Я бы попробовал это:

1. удалить "[" и "]" из Token.reservedOpNames
2. добавьте другой анализатор к вашим обычным анализаторам: squareBrackets = Token.brackets lexer

3. измените свою boundFormula функцию на:

    boundFormula =
       do v <- squareBrackets var
          f <- formulaTerm
          return $ Bound v f
     

Вот как я бы написал ваш синтаксический анализатор с помощью Megaparsec (документы, учебник):

 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 "amp;") ]
      ]
  

Некоторые моменты:

• По возможности используйте аппликативный стиль ( <$> , <$ , $> ).
• Megaparsec переименовал некоторые комбинаторы, подобные many1 to some . Есть руководство по переключению с Parsec на Megaparsec, которое облегчает переход. (Возможно, это немного устарело; я отправил PR в процессе ответа на этот вопрос.)
• Вам не нужно, try когда BVar s и FVar s являются взаимоисключающими для первого символа, $ . Достаточно сначала просто перечислить BVar анализатор. Поскольку вы не найдете никакого другого допустимого выражения, начинающегося с $ , сбой синтаксического анализатора, который потребил $ , не является проблемой.

• В вашей грамматике ничего не говорится о литеральных скобках или литеральных скобках после скобок. Итак, для синтаксического анализа "[$x](x amp; 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 немного сложны, потому что они требуют, чтобы вы указали, что такое токен, что такое пробел и так далее. Синтаксические анализаторы лексем в мегапарсекундах обладают некоторой сложностью, но вы можете исключить части, которые не имеют отношения к делу (например, комментарии к строке и комментарии к блокам), используя empty :: Alternative f => f a .

• Пробелы в комбинаторах синтаксического анализа — сложная задача. Убедитесь, что все анализаторы являются либо анализаторами лексем (например, symbol "foo" , lexeme $ some C.letterChar ), либо комбинациями анализаторов лексем. Если вы используете lexeme что-то, что уже является анализатором лексем, вы делаете что-то неправильно, и если вы забудете использовать lexeme что-то, вы рискуете запретить пробелы в тех местах, где вы хотите это разрешить.

  Я не использовал lexeme around C.char '$' .

• Всегда есть угловые регистры, например, пробелы в начале:

   > parseTest formula " [$x](x amp; true) "
  1:1:
    |
  1 |  [$x](x amp; true) 
    | ^^^^^
  unexpected " [$x]"
  expecting "false", "true", '[', '¬', or letter
    

  Если вы хотите точно утверждать, что ваш анализатор допускает пробелы во всех нужных местах, вы можете создать «ugly-printer», который для произвольных синтаксических деревьев вставляет произвольные пробелы там, где это разрешено. Тогда ваше свойство заключается в том, что синтаксический анализ синтаксического дерева с уродливым шрифтом должен давать такое же синтаксическое дерево.

• Ошибки синтаксического анализа в мегапарсекундах выглядят очень красиво.

  Они могут выглядеть приятнее, если вы используете <?> оператор (также доступный в Parsec).