3

在这里，我想到一个可能的配置是一棵规范树，每个规范都有一个对应的关键字（字符串）和类型。像这样的东西：

data Select = And | Or
data ConfigTree = Node Select [ConfigTree] | Leaf (String, *)

鉴于没有“类型类型”，我不确定如何正确编写它，但暂时不要介意。

现在，给定这样一棵树，我想构建一个可以读取可能的有效配置的解析器；我假设我已经有了可以解析关键字/类型对的子解析器。

例如，一个可能的配置树是：

Node And [ Leaf ("width", Double)
         , Node Or [ Leaf ("height", Double) , Leaf ("aspectratio", Double)
         ]

它可以指定矩形的大小。一个可能的配置文件是：

aspectratio = 2
width = 10

（假设配置文件只是换行符分隔对的列表，keyword = blah，其中 blah 是该关键字的相应解析器可以处理的内容；但它们可以按任何顺序排列，只需匹配一个树的可能“有效子集”，其中有效子集是包含顶部节点的任何子集，它包含它包含的“和”节点的所有子节点，并且准确地说是它包含的“或”节点的一个子节点。）

我什至不知道如何开始构建这样的解析器。任何人都可以提供一些关于如何进行的提示，或者一种将上述 ConfigTree 数据类型完全重构为更易于解析的方法吗？

4

1 回答 1

2

为此构建解析器的问题在于您的输入格式与您的数据类型完全不匹配。输入格式是一个简单、易于解析的键值对列表，而您的数据类型是树。例如，要确定And节点中的所有子树是否有效，您必须知道完整的输入。

因此，与其直接在解析器中验证键值对列表，不如事后进行。

我整理了一个小例子来说明我的意思：

data Type = TDouble | TString 
data Select = And | Or 
data ConfigTree = Node Select [ConfigTree] | Leaf (String, Type)

-- matches a list of key-value pairs against a tree
match :: [(String, String)] -> ConfigTree -> Bool
match sts (Leaf (s, t)) = case filter ((== s) . fst) sts of
                            -- we don't want multiple occurences of a key
                            [(_, v)] -> if valid v t then True else False 
                            _        -> False
match sts (Node And cfgs) = and . map (match sts) $ cfgs
-- not completely what you described, because it will match 1 or more
match sts (Node Or cfgs)  = or  . map (match sts) $ cfgs

-- validates a string against a type
valid :: String -> Type -> Bool
valid s TDouble = case reads s :: [(Double, String)] of
                    [(_, "")] -> True
                    _         -> False
valid _ TString = True

-- this is what you actually parsed
config = [ ("aspectratio", "2")
         , ("width", "123")
         , ("name", "Sam")
         ]

-- the example tree
cfgTree = Node And [ Leaf ("width", TDouble)
                   , Node Or [ Leaf ("height", TDouble), Leaf ("aspectratio", TDouble)]
                   ]

我不认为这是一个特别有用的示例，因为它所做的只是检查您的配置数据是否有效，它不会提取它们，但我希望它能够说明我的意思。

于 2012-02-04T23:42:58.910 回答