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