如何在 Haskell 中编写上下文无关语法？另外，我制作这个编译器的方向正确吗？

Question

作为参考，我正在学习《编译器原理：技术与工具》（又名“龙书”）这本书。

我正在创建一种可以将两个自然数相加的语言。我已经完成了词法分析器的编写。词法分析器的标记由以下部分组成。

data Token = Digit String | Plus | Minus | Multiply | Divide
    deriving (Show, Eq)

令牌确实包含其他操作，但我只关心两个自然数相加。我构建词法分析器的方式如下。

1. 我首先读取所有输入字符串并从该字符串中获取所有单词。单词是任何连续的字符串，后跟一个空格。下面的函数可以做到这一点。

getAllWords :: String -> String -> [String]
getAllWords string word = case string of
    []     -> [word]
    ' ':xs -> word : (getAllWords xs "")
    x:xs   -> getAllWords xs (word ++ [x])

2. 然后我从这个字符串列表中删除所有空格。

removeWhiteSpace :: [String] -> [String]
removeWhiteSpace list = case list of
    []    -> []
    "":xs -> removeWhiteSpace xs
    x:xs  -> x : (removeWhiteSpace xs)

3. 我对该语言中的每个标记都有一个 DFA。我运行一个函数分词器，将我从 (removeWhiteSpace (getAllWords list "")) 获得的列表中的每个单词传递到每个 DFA。如果 DFA 识别出该单词，则会输出相关标记。该函数通过从左到右读取原始字符串来返回所有标记的列表。

tokeniserHelper :: [String] -> [Token]
tokeniserHelper list = case list of
    [] -> []
    x:xs
        | (digitDFA x S0 == True)    -> (Digit x) : (tokeniserHelper xs)
        | (plusDFA x S0 == True)     -> (Plus)    : (tokeniserHelper xs)
        | (minusDFA x S0 == True)    -> (Minus)   : (tokeniserHelper xs)
        | (multiplyDFA x S0 == True) -> (Multiply) : (tokeniserHelper xs)
        | (divideDFA x S0 == True)   -> (Divide) : (tokeniserHelper xs)
 
tokeniser :: String -> [Token]
tokeniser string = tokeniserHelper (removeWhiteSpace (getAllWords string ""))

我意识到这与将所有 DFA 合并为一个大 DFA 的一般想法有点不同。但我第一次发现这种方法更简单。书中也有建议，所以我决定采用它。

---

现在我已经转向解析器部分，我正在尝试实现一个递归下降解析器来构造解析树。对于解析树，我使用玫瑰树作为我的基础数据结构。

data ParseTree a = Node a [ParseTree a]
    deriving (Show, Eq)

我想使用的语法如下。

E -> E + E | 0E | . . . | 9E | \epsilon

但我不确定如何实现这个语法以用于递归下降解析器。有人可以指导我如何做吗。

另外，我构建编译器的方向正确吗？我做的事情有什么根本错误吗？

Answer 1

Haskell 中通常的方法是使用解析器 monad。这不是龙书里的内容。我假设您总体上了解 monad。如果你不这样做，那么我建议你先去看看 State、Reader 和 Random monad 等东西是如何工作的。

用于您的标记的简单解析器 monad 将如下所示：

newtype Parser a = Parser { runParser :: [Token] -> [(a, [Token])] }

这意味着

Parser

接受一个标记列表并输出一个可能解析的列表，以及每个解析项后面的剩余标记列表。

在本例中，我将返回类型设置为列表。这是最通用的解决方案：这意味着返回每个可能的解析，从而允许您有一个不明确的语法。然而，它只能通过返回一个空列表来发出错误信号，而不知道出了什么问题。

所以现在你可以编写一个解析器规则，例如：

digit :: Parser (ParseTree Token)
digit = Parser $ \tokens -> case tokens of
  (Digit str : rest) -> [(ParseTree (Digit str) [], rest)]
  _ -> []

这表示如果第一个标记是

digit

，则

Digit

解析器将会成功。在这种情况下，它将数字作为解析树中的单个叶子与列表的其余部分一起返回。如果有其他情况，则解析器将失败，返回空结果列表。

Parser $ \tokens ->

位只是将匿名函数包装在

Parser

类型中。

这本身并没有多大用处，但是您可以将这些原始解析器组合成更复杂的解析器。您使用的两个主要组合器是串联（即解析这个，然后解析那个）和交替（即解析这个或那个）。这就是 monad 实例发挥作用的地方。

首先，这是解析器的 monad 实例。

instance Monad Parser where
  return a = Parser $ \tokens -> [a, tokens]
  v >>= f =  Parser $ \tokens -> concatMap f2 $ runParser v tokens
    where f2 (v, rest) = runParser f2 v rest

return

函数是一个空解析器：它返回一个值而不消耗任何东西。

>>=

（又名“绑定”）运算符采用类型为

v

的现有解析器

Parser a

和类型为

f

的第二个函数

a -> Parser b

。它将其转换为单个解析器，该解析器执行

v

解析器并将结果传递给

f

，从而给出第二个解析器。然后，该解析器在标记的

rest

上运行（即第一个解析器留下的内容）并返回结果。

我假设您知道如何将

do

符号脱糖为

>>=

调用。

所以你可以写这样的东西：

expression :: Parser (ParseTree Token)
expression = do
   arg1 <- digit
   op <- operator  -- Exercise: define operator :: Parser (ParseTree Token)
   arg2 <- digit
   return $ ParseTree op [arg1, arg2]

这将解析一个简单的

digit + digit

表达式。

您还需要一个替代运算符，然后您可以构建通用的递归下降解析器。另请参阅

Alternative

类型类，它为您提供了此概念的通用类型类。