Haskell/ParseExps
本章讨论如何将诸如“3*sin x + y”之类的文本字符串转换为抽象的语法表示，例如 Plus (Times (Number 3) (Apply "sin" (Variable "x"))) (Variable "y")。
我们将在整个过程中使用 Text.ParserCombinators.ReadP，因此您需要打开参考以进行参考。
import Text.ParserCombinators.ReadP
为了热身，为了开始解决问题，我们首先尝试一个更简单的问题。一种语言，其中符号只是字母“o”，一个运算符“&”和括号。首先定义这些树的数据类型
data Tree = Branch Tree Tree | Leaf deriving Show
现在，使用 ReadP 库定义叶子解析器
leaf = do char 'o'
return Leaf
现在要定义由“&”运算符组成的分支解析器，我们需要选择一个结合性。也就是说，o&o&o 是否与 (o&o)&o 或 o&(o&o) 相同 - 让我们选择后者。
作为第一个近似值，我们可以忘记括号，在第一个“里程碑”之后添加它们
branch = do a <- leaf
char '&'
b <- tree
return (Branch a b)
tree = leaf +++ branch
现在可以测试它，看看它是否在一些输入上正常工作
*Main> readP_to_S tree "o" [(Leaf,"")] *Main> readP_to_S tree "o&o" [(Leaf,"&o"),(Branch Leaf Leaf,"")] *Main> readP_to_S tree "o&o&o" [(Leaf,"&o&o"),(Branch Leaf Leaf,"&o"),(Branch Leaf (Branch Leaf Leaf),"")]
由于它运行良好，我们可以继续添加对括号的支持。括号通常定义，以便我们以后可以重用它
brackets p = do char '('
r <- p
char ')'
return r
我们现在可以更新分支和树解析器以支持括号
branch = do a <- leaf +++ brackets tree
char '&'
b <- tree
return (Branch a b)
tree = leaf +++ branch +++ brackets tree
一些测试表明它似乎有效
*Main> readP_to_S tree "((o&((o&o)))&o&((o&o)&o)&o)" [(Branch (Branch Leaf (Branch Leaf Leaf)) (Branch Leaf (Branch (Branch (Branch Leaf Leaf) Leaf) Leaf)),"")]
这为改编提供了一个良好的起点。朝着最终目标的第一项修改，这很容易做到，是将叶子从仅仅“o”更改为任何字符串。为此，我们必须在数据类型中更改为 `Leaf String` 并更新叶子函数
data Tree = Branch Tree Tree | Leaf String deriving Show
leaf = do s <- many1 (choice (map char ['a'..'z']))
return (Leaf s)
对于下一个改编，我们尝试添加一个新的运算符“|”，它比“&”更弱。即“foo&bar|baz”应解析为“(foo&bar)|baz”。首先，我们需要更新表示语法的类型
data Operator = And | Or deriving Show data Tree = Branch Operator Tree Tree | Leaf String deriving Show
显而易见的事情是复制 `branch` 函数并将其命名为 `andBranch` 和 `orBranch`，并使用左选择运算符 `<++` 为或运算符赋予优先级
andBranch = do a <- leaf +++ brackets tree
char '&'
b <- tree
return (Branch And a b)
orBranch = do a <- leaf +++ brackets tree
char '|'
b <- tree
return (Branch Or a b)
tree = leaf +++ (orBranch <++ andBranch) +++ brackets tree
但是，此修改不起作用，正如我们在示例中看到的那样
>>> last $ readP_to_S tree "a&b|s" (Branch And (Leaf "a") (Branch Or (Leaf "b") (Leaf "s")),"")
如果我们将诸如“a&b&c&d|e&f&g&h|i&j&k|l&m&n&o|p&q&r|s”之类的表达式视为一棵树“X|Y|Z|W|P|Q”（我们已经知道如何解析它！），除了叶子是一个更复杂的形式（但同样，我们已经知道如何解析它），那么我们可以组合一个有效的解析器
andBranch = do a <- leaf +++ brackets tree
char '&'
b <- andTree
return (Branch And a b)
andTree = leaf +++ brackets tree +++ andBranch
orBranch = do a <- andTree +++ brackets tree
char '|'
b <- orTree
return (Branch Or a b)
orTree = andTree +++ brackets tree +++ orBranch
tree = orTree
虽然这种方法确实有效，例如
*Main> readP_to_S tree "(foo&bar|baz)" [(Leaf "","(foo&bar|baz)"),(Branch Or (Branch And (Leaf "foo") (Leaf "bar")) (Leaf "baz"),""),(Branch Or (Branch And (Leaf "foo") (Leaf "bar")) (Leaf "baz"),"")] *Main> readP_to_S tree "(foo|bar&baz)" [(Leaf "","(foo|bar&baz)"),(Branch Or (Leaf "foo") (Branch And (Leaf "bar") (Leaf "baz")),""),(Branch Or (Leaf "foo") (Branch And (Leaf "bar") (Leaf "baz")),"")]
它以模棱两可的方式进行解析，这对于效率而言是不希望的，并且暗示我们可能做了一些不自然的事情。`andTree` 和 `orTree` 函数都包含 `brackets tree`，因为 `orTree` 包含 `andTree`，这就是歧义潜入的地方。为了解决它，我们只需从 `orTree` 中删除即可。
orTree = andTree +++ orBranch
所有先前的修补和玩弄实际上已经使我们最终程序的很大一部分结构变得清晰。回顾所写的内容，我们可以很容易地扩展它以添加另一个运算符，然后添加另一个运算符（留给读者的练习：如果不清楚这到底是如何完成的，请弄清楚并完成它）。片刻的思考表明，我们可以完成这种模式并将其抽象出来，给出一个任意长的运算符列表
operators = [(Or,'|'),(And,'&')]
或者可能
data Operator = Add | Mul | Exp deriving Show operators = [(Add,'+'),(Mul,'*'),(Exp,'^')]
解析器应该从它计算出来，将其嵌套（正如我们过去手动完成的那样），以便解析正确地发生，没有歧义。
经验丰富 的 Haskell 程序员已经在脑海中看到了以下内容
tree = foldr (\(op,name) p ->
let this = p +++ do a <- p +++ brackets tree
char name
b <- this
return (Branch op a b)
in this)
(leaf +++ brackets tree)
operators
然后对其进行测试。
*Main> readP_to_S tree "(x^e*y+w^e*z^e)" [(Leaf "","(x^e*y+w^e*z^e)"),(Branch Add (Branch Mul (Branch Exp (Leaf "x") (Leaf "e")) (Leaf "y")) (Branch Mul (Branch Exp (Leaf "w") (Leaf "e")) (Branch Exp (Leaf "z") (Leaf "e"))),"")]
这是一个暂停的好检查点，总而言之，我们将胚胎解析器提炼成了以下脚本
import Text.ParserCombinators.ReadP
brackets p = do char '('
r <- p
char ')'
return r
data Operator = Add | Mul | Exp deriving Show
operators = [(Add,'+'),(Mul,'*'),(Exp,'^')]
data Tree = Branch Operator Tree Tree | Leaf String deriving Show
leaf = do s <- many1 (choice (map char ['a'..'z']))
return (Leaf s)
tree = foldr (\(op,name) p ->
let this = p +++ do a <- p +++ brackets tree
char name
b <- this
return (Branch op a b)
in this)
(leaf +++ brackets tree)
operators
由于函数式/应用式符号和忽略空格都依赖于一些相同的字符（空格字符），因此询问哪一个应该首先实现，或者是否不重要哪一个应该首先编程，是一个有用的问题。
考虑到表达式“f x”，表明我们应该在处理应用式符号之前找到如何解析空格，因为一旦处理完毕，函数应用应该仅仅对应于简单的并置（如预期的那样）。
在使我们当前的解析器忽略空格方面存在一个技术难题：如果我们要创建一个 `skipWhitespace` 解析器，并在空格可能出现的任何地方放置它，我们将遇到模棱两可的解析。因此，有必要仅在某些关键位置跳过空格，例如，我们可以选择这样的约定，即始终在读取令牌 *之前* 跳过空格。然后“ a + b * c ” 将被解析器以以下方式分块：“[ a][ +][ b][ *][ c][ ]”。我们选择哪种约定是任意的，但在读取之前忽略空格似乎更简洁，因为它可以处理“ a”而没有任何抱怨。
我们定义如下
skipWhitespace = do many (choice (map char [' ','\n']))
return ()
并更新之前编写的所有解析，以便它们遵循新的约定
brackets p = do skipWhitespace
char '('
r <- p
skipWhitespace
char ')'
return r
leaf = do skipWhitespace
s <- many1 (choice (map char ['a'..'z']))
return (Leaf s)
tree = foldr (\(op,name) p ->
let this = p +++ do a <- p +++ brackets tree
skipWhitespace
char name
b <- this
return (Branch op a b)
in this)
(leaf +++ brackets tree)
operators
为了添加应用式支持，语法显然需要允许它
data Tree = Apply Tree Tree | Branch Operator Tree Tree | Leaf String deriving Show
此语法树将允许诸如“(x + y) foo”之类的句子，虽然这不是正确的，但诸如“(f . g) x”之类的其他句子在 Haskell 中很常见 - 应该由类型检查器来决定哪个有意义，哪个没有意义：这种关注点分离使我们的问题（解析）保持简单和同质。
我们的解析器本质上只是两个函数 `leaf` 和 `tree`（`skipWhitespace` 和 `brackets` 被视为“库”或辅助函数）。`tree` 函数吞噬了所有可以吞噬的运算符，并将叶子附加到它可以附加的地方。而 `leaf` 函数可以被认为是读取所有不包含运算符的内容。鉴于对程序的这种看法，很明显，为了支持应用式符号，需要用解析函数应用链的东西替换叶子。
显而易见的事情是尝试一下，
leaf = chainl1 (do skipWhitespace
s <- many1 (choice (map char ['a'..'z']))
return (Leaf s))
(return Apply)
并且很容易扩展以支持前面讨论的“常见”复合句
leaf = chainl1 (brackets tree
+++ do skipWhitespace
s <- many1 (choice (map char ['a'..'z']))
return (Leaf s))
(return Apply)
这就是问题完全解决！我们最初的目标已经完成，只需要指定他们想要使用的运算符（按顺序）并编写一个遍历函数将 `Tree` 转换为例如数学表达式 - 如果使用未知函数等则会给出错误。
编写的算法足够通用，可以在不同的情况下使用，即使它们只有一个用途 - 如果我们打算在更大的程序中使用它们，将内部与外部（其接口）隔离至关重要。
module Parser
( Tree(..), parseExpression
) where
import Data.Maybe
import Text.ParserCombinators.ReadP
skipWhitespace = do many (choice (map char [' ','\n']))
return ()
brackets p = do skipWhitespace
char '('
r <- p
skipWhitespace
char ')'
return r
data Tree op = Apply (Tree op) (Tree op) | Branch op (Tree op) (Tree op) | Leaf String deriving Show
parseExpression operators = listToMaybe . map fst . filter (null .snd) . readP_to_S tree where
leaf = chainl1 (brackets tree
+++ do skipWhitespace
s <- many1 (choice (map char ['a'..'z']))
return (Leaf s))
(return Apply)
tree = foldr (\(op,name) p ->
let this = p +++ do a <- p +++ brackets tree
skipWhitespace
char name
b <- this
return (Branch op a b)
in this)
(leaf +++ brackets tree)
operators