如果你的语法相当大,你可以做的最简单的想法就是只使用 Alex/Happy 组合。它使用起来相当简单,直接接受 BNF 格式 - 不需要人工翻译 - 也许最重要的是,它可以生成速度极快的解析器/词法分析器。
如果你决心用秒差距来做这件事(或者你这样做是为了学习练习),我发现一般来说分两个阶段做起来更容易;首先词法分析,然后解析。秒差距将两者兼而有之!
首先写出合适的类型:
{-# 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
解析单个标记很简单。为简单起见,变量是 1 个或多个字母。您当然可以根据需要更改此设置。
oneToken :: Lexer Token
oneToken = (char '(' >> return LParen) <|>
(char ')' >> return RParen) <|>
(Str <$> many1 letter)
解析整个令牌流只是多次解析单个令牌,可能用空格分隔:
lexer :: Lexer [Token]
lexer = spaces >> many1 (oneToken <* spaces)
注意放置的位置spaces
:这样,字符串的开头和结尾处都会接受空格。
Since 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
and optionMaybe
当您需要“也许做某事”时,这很有用。
expr = do
e0 <- term
option e0 (parens expr >>= \e1 -> return (App e0 e1))
最后一行的意思是 - 尝试应用给定的解析器option
- 如果失败,则返回e0
.
为了测试你可以这样做:
tokAndParse = runParser (lexer <* eof) () "" >=> runParser (expr <* eof) () ""
The 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"))