Propositions Parser using recursion in Elm

Question

Yesterday, I posted about an assignment I got for parsing logical propositions. After a lot of research and trying different things, I got it to work for individual propositions: going from a string to my own custom type Proposition. However, now I am at a complete roadblock - I have almost no idea how to combine these components to work for more complex propositions. I am not even sure whether they are suitable to be combined and work together. You will the code and the screenshot of my current output below, any advice / ways for approaching this would be greatly appreciated!

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) ) "
    ]

Code output so far:

enter image description here

user_7943564 · Answer

You're almost there, but you need a parser that can parse any kind of proposition, and you need to call that recursively instead of the individual parsers. There's a couple ways you can do that. The easiest is to just put all your existing parsers in a oneOf:

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

and just call that from the other parsers, e.g. from 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 ")"
    ]

This has a lot of duplication though, as the variables are parsed for each expression, which would ale make it error-prone to add more variables. So let's simplify by moving those into propositionParser:

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

which will allow us to remove the oneOf from the individual parsers, since they're only handling one case each:

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

You should now be able to see that the structure of the parser mirrors the type it parses. We now have a propositionParser with a oneOf where each case corresponds to a case from the Proposition type, and with each individual case parser using propositionParser where the type says it needs a Proposition. Knowing this, you should hopefully be able to create a parser for any custom type by creating small parsers for each individual piece, and then combine them by simply mimicking the structure of the type.

Propositions Parser using recursion in Elm

1 Answers