命题解析器使用榆树中的递归

Question

昨天，我发布了一份解析逻辑命题的作业。经过大量研究并尝试不同的事情后，我让它适用于单个命题：从字符串到我自己的自定义类型命题。然而，现在我完全遇到了障碍——我几乎不知道如何组合这些组件来实现更复杂的命题。我什至不确定他们是否适合结合在一起工作。您将在下面看到我当前输出的代码和屏幕截图，任何解决此问题的建议/方法将不胜感激！

type Proposition
  = A 
  | B 
  | C
  | And Proposition Proposition
  | Or Proposition Proposition
  | Implies Proposition Proposition
  | Not Proposition
  | Equal Proposition Proposition

andParser : Parser Proposition
andParser =
  oneOf
    [ succeed A
        |. keyword "A"
    , succeed B
        |. keyword "B"
    , succeed C
        |. keyword "C"
    , succeed And
        |. symbol "&"
        |. spaces
        |. symbol "("
        |. spaces
        |= lazy (\_ -> andParser)
        |. spaces
        |. symbol ","
        |. spaces
        |= lazy (\_ -> andParser)
        |. spaces
        |. symbol ")"
    ]

orParser : Parser Proposition
orParser =
  oneOf
    [ succeed A
        |. keyword "A"
    , succeed B
        |. keyword "B"
    , succeed C
        |. keyword "C"
    , succeed Or
        |. symbol "|"
        |. spaces
        |. symbol "("
        |. spaces
        |= lazy (\_ -> orParser)
        |. spaces
        |. symbol ","
        |. spaces
        |= lazy (\_ -> orParser)
        |. spaces
        |. symbol ")"
    ]

implParser : Parser Proposition
implParser =
  oneOf
    [ succeed A
        |. keyword "A"
    , succeed B
        |. keyword "B"
    , succeed C
        |. keyword "C"
    , succeed Implies
        |. symbol ">"
        |. spaces
        |. symbol "("
        |. spaces
        |= lazy (\_ -> implParser)
        |. spaces
        |. symbol ","
        |. spaces
        |= lazy (\_ -> implParser)
        |. spaces
        |. symbol ")"
    ]

equalParser : Parser Proposition
equalParser =
  oneOf
    [ succeed A
        |. keyword "A"
    , succeed B
        |. keyword "B"
    , succeed C
        |. keyword "C"
    , succeed Equal
        |. symbol "="
        |. spaces
        |. symbol "("
        |. spaces
        |= lazy (\_ -> equalParser)
        |. spaces
        |. symbol ","
        |. spaces
        |= lazy (\_ -> equalParser)
        |. spaces
        |. symbol ")"
    ]

notParser : Parser Proposition
notParser =
  oneOf
    [ succeed A
        |. keyword "A"
    , succeed B
        |. keyword "B"
    , succeed C
        |. keyword "C"
    , succeed Not
        |. symbol "N"
        |. symbol "("
        |. spaces
        |= lazy (\_ -> notParser)
        |. spaces
        |. symbol ")"
    ]

my_results: List String
my_results =
    [     "and parser test ____& (A , B)______",
          pr <| Parser.run andParser "& (A , C)",
          "or parser test ____ | (A , B) ______",
          pr <| Parser.run orParser "| (A , B)",
          "implies parser test ____ > (A , B) ______",
          pr <| Parser.run implParser "> (A , B)",
          "equal parser test ____ = (A , B) ______",
          pr <| Parser.run equalParser "= (A , B)",
          "equal parser test ____ N ( A ) ______",
          pr <| Parser.run notParser "N(B)",
          "parsing & ( N (B) ) C",
          pr <| Parser.run andParser "& ( A, N(B) ) "
    ] 

到目前为止的代码输出：

Answer 1

你已经快完成了，但是你需要一个可以解析任何类型命题的解析器，并且你需要递归地调用它而不是单独的解析器。有几种方法可以做到这一点。最简单的方法是将所有现有的解析器放在 oneOf 中：

propositionParser : Parser Proposition
propositionParser =
    oneOf
        [ andParser
        , orParser
        , implParser
        , equalParser
        , notParser
        ]

然后从其他解析器调用它，例如从 notParser ：

notParser : Parser Proposition
notParser =
  oneOf
    [ succeed A
        |. keyword "A"
    , succeed B
        |. keyword "B"
    , succeed C
        |. keyword "C"
    , succeed Not
        |. symbol "N"
        |. symbol "("
        |. spaces
        |= lazy (\_ -> propositionParser)
        |. spaces
        |. symbol ")"
    ]

但这有很多重复，因为为每个表达式解析变量，这会使添加更多变量容易出错。因此，让我们通过将它们移入 propositionParser 来简化：

propositionParser : Parser Proposition
propositionParser =
    oneOf
        [ succeed A
            |. keyword "A"
        , succeed B
            |. keyword "B"
        , succeed C
            |. keyword "C"
        , andParser
        , orParser
        , implParser
        , equalParser
        , notParser
        ]

这将允许我们从各个解析器中删除 oneOf，因为它们每个只处理一种情况：

notParser : Parser Proposition
notParser =
    succeed Not
        |. symbol "N"
        |. symbol "("
        |. spaces
        |= lazy (\_ -> propositionParser)
        |. spaces
        |. symbol ")"

您现在应该是可以看到解析器的结构反映了它解析的类型。我们现在有一个带有 oneOf 的 propositionParser，其中每个案例对应于 Proposition 类型中的一个案例，并且每个案例解析器都使用 >propositionParser 其中类型表明它需要一个Proposition。知道了这一点，您应该希望能够通过为每个单独的部分创建小型解析器来为任何自定义类型创建解析器，然后通过简单地模仿类型的结构来组合它们。