У меня есть логический язык, определенный следующим BNF.
formula ::= true
| false
| var
| formula & formula
| [binder] formula
binder ::= var
| $var
По сути, это позволяет использовать такие формулы, как x & true, [x]x и [$x](x & 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 = ["&", "$", "[", "]"]
, 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)? Обратите внимание, что у него нет проблем с тем, что & касается его операндов, только когда два оператора [ и $ касаются.