Propositions Parser using recursion

Hey everyone! 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) ) "
    ] 

2 Likes

I wrote a parser for Elm types a while ago, so maybe it would help to read through that code:

I do not know the specifics of your assignment, but maybe there will be some techniques in there that are relevant!

Aside: If you have parentheses around each And, Or, Implies, and Equal, that makes things much easier! You can decide which proposition you are looking at when you see the infix operator. (If there are not always parentheses, but instead there is “operator associativity and precedence” that implicitly clarify the parens, I have found it works well to parse them into a flat list and then figure out the implicit parentheses in a second pass, independent from the parser code.) Not sure what is right for your case, but hopefully this gives some ideas!

1 Like

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.