简而言之，即使您有一个令牌列表，您仍然需要解析器。
Parsec可以处理替代令牌流，但您可能需要参考手册 - 可在Daan Leijen的“遗留”主页上获得PDF文件 -
http://legacy.cs.uu.nl/daan/download/parsec/parsec.pdf。 您可以自己编写解析器而不使用组合库，但是您将重新实现Parsec的一部分。 就我所记得的，UU_parsing希望与单独的扫描程序一起使用，因此这是另一个选项。
虽然它无法处理解析，但您可能会发现Lennart Augustsson的“Lambda calculus cooked four ways”对其他事情有所帮助 -
http://www.augustsson.net/Darcs/Lambda/top.pdf
编辑 - 这里是使用Parsec进行操作的部分计划，有关详细信息，您需要查阅手册的第2.11节。
假设您拥有用于具体“内部”令牌的数据类型：
data InternalTok = Ident String
| BinOpPlus
| BinOpMinus
| UnaryOpNegate
| IntLiteral Int
deriving (Show)
然后您将获得这些类型的Parsec令牌并进行解析：
type MyToken = Token InternalTok
type MyParser a = GenParser MyToken () a
根据 Parsec 手册，定义一个辅助函数 - 这个函数处理 show 和 pos，使得单独的定义更短，参见第 19 页上的 mytoken 函数。
mytoken :: (MyToken -> Maybe a) -> MyParser a
mytoken test = token showToken posToken testToken
where
showToken tok = show tok
posToken tok = no_pos
testToken tok = test tok
目前，您的令牌类型不跟踪源位置，因此：
no_pos :: SourcePos
no_pos = newPos "" 0 0 0
对于每个终端，您都需要定义一个令牌函数：
identifier :: MyParser MyToken
identifier = mytoken (\tok -> case tok of
a@(Prefix (Ident _)) -> Just a
_ -> Nothing)
intLiteral :: MyParser MyToken
intLiteral = mytoken (\tok -> case tok of
a@(Prefix (IntLiteral _)) -> Just a
_ -> Nothing)
binPlus :: MyParser MyToken
binPlus = mytoken (\tok -> case tok of
a@(Infix BinOpPlus _ _) -> Just a
_ -> Nothing)
binMinus :: MyParser MyToken
binMinus = mytoken (\tok -> case tok of
a@(Infix BinOpMinus _ _) -> Just a
_ -> Nothing)
unaryNegate :: MyParser MyToken
unaryNegate = mytoken (\tok -> case tok of
a@(Prefix UnaryNegate _ _) -> Just a
_ -> Nothing)
编辑 - 要处理自定义中缀运算符，您需要使用这些令牌解析器：
tokInfixL :: Int -> MyParser MyToken
tokInfixL n = mytoken $ \tok -> case tok of
a@(Infix _ i InfixL) | i == n -> Just a
_ -> Nothing)
tokInfixR :: Int -> MyParser MyToken
tokInfixR n = mytoken $ \tok -> case tok of
a@(Infix _ i InfixR) | i == n -> Just a
_ -> Nothing)
tokInfixC :: Int -> MyParser MyToken
tokInfixC n = mytoken $ \tok -> case tok of
a@(Infix _ i InfixC) | i == n -> Just a
_ -> Nothing)
tokPrefix :: MyParser MyToken
tokPrefix = mytoken (\tok -> case tok of
a@(Prefix _) -> Just a
_ -> Nothing)
现在您可以定义解析器-您需要事先确定优先级的层数，因为您需要为每个层次编写解析器，顶层表达式解析仅调用最高优先级解析器。
pExpression :: Parser Expersion
pExpression = expression10
每个优先级别需要一个类似于这样的解析器，你需要自己解决非关联性。此外，你可能需要对chainl / chainr进行一些工作 - 我只是用UU_Parsing在这种风格下编写了一个解析器，使用Parsec可能会稍有不同。 注意Apply通常处于最高优先级。
expression10 :: Parser Expression
expression10 =
Apply <$> identifier <*> pExpression
<|> Prefix <$> tokPrefix <*> pExpression
<|> chainl (Infix <$> tokInfixL 10) expression9
<|> chainr (Infix <$> tokInfixR 10) expression9
expression9 :: Parser Expression
expression9 =
Prefix <$> tokPrefix <*> pExpression
<|> chainl (Infix <$> tokInfixL 9) expression8
<|> chainr (Infix <$> tokInfixR 9) expression8
...
你需要扩展语法以处理优先级为0的IntLiterals和Identifiers：
expression0 :: Parser Expression
expression0 =
IntLit <$> intLiteral
<|> Ident <$> identifier
<|> ...
编辑 - 为了无限优先级 - 如果你只有应用程序和Atom，可能类似这样的东西会起作用。请注意，您必须更改tokInfixL和tokInfixR解析器，以不再匹配assoc-level，并且您可能需要尝试使用替代方案的顺序。
expression :: Parser Expression
expression =
Apply <$> identifier <*> expression
<|> Prefix <$> tokPrefix <*> expression
<|> chainl (Infix <$> tokInfixL) expression
<|> chainr (Infix <$> tokInfixR) expression
<|> intLiteral
<|> identifier
intLiteral :: Parser Expression
intLiteral = Atom . convert <$> intLiteral
where
convert = ??
identifier :: Parser Expression
identifier = Atom . convert <$> intLiteral
where
convert = ??
a的抽象，但我想自己将它们建模为具体的数据类型。 - stephen tetleya，因为我想之后能够对树应用一些操作（比如打印）。在开始时，a是一个代数数据类型，可以是名称、数字文字或其他内容。但对于这个算法来说，这并不重要，因为不需要检查原子的任何属性。 - fuz