0

I have some pseudocode that is in the form:

patch a:
  if b == "foo1"
  then
    a = "No"
    if c == "foo2"
    then
      if d == "foo3" || d == "foo4" || d == "foo5" || d == "foo6"
      then
        a = "Yes"
      else
        a = "No"
    else
      if c == "foo7"
      then
        if d == "foo8" || d == "foo9"
        then
          a = "Yes"
        else
          a = "No"
      else
        if c == "foo10"
        then
          if d == "foo11" || d == "foo12"
          then
            a = "Yes"
          else
            a = "No"
        else
          if c == "foo13"
          then
            if d != "foo11" && d != "foo12" && d != "foo8" && d != "foo9"
            then
              a = "Yes"
            else
              a = "No"
          else
            a = "Yes"

I have an ANTLR file that I am using to parse this pseudocode. I would like to be able to derive a single condition that satisfies each variable assignment I encounter as I parse the pseudocode. For the example above a single condition for a = "yes" would look like:

  (b == "foo1" AND c == "foo7" AND (d == "foo8" OR d == "foo9")) OR
  (b == "foo1" AND c == "foo10" AND (d == "foo11" OR d == "foo12")) OR
  (b == "foo1" AND c == "foo13" AND d != "foo11" AND d != "foo12" AND d != "foo8" AND d != "foo9")

and the single condition for a = "no" would look like:

(b == "foo1" AND c == "foo2" AND d != "foo3" AND d != "foo4" AND d != "foo5" AND d != "foo6") OR
  (b == "foo1" AND c == "foo7" AND d != "foo8" AND d != "foo9") OR
  (b == "foo1" AND c == "foo10" AND d != "foo11" AND d != "foo12") OR
  (b == "foo1" AND c == "foo13" AND (d == "foo11" OR d == "foo12" OR d == "foo8" OR d == "foo9"))

I am using a stack to maintain my conditions. Everytime, I enter an if block I push my condition to the stack and pop it when I leave the if block. When I enter a then block I push an AND to the stack and when I enter an else block I push an OR to stack. This works fine for simple patches but I am struggling to figure how to accommodate for line 4 in the example patch.

With the my current solution I am getting something like a = "No" when b == "foo1" OR ... this causing problems since it possible for a == "Yes" if a couple of more conditions are met. How do I account for this situation?

Update 1 Instead of trying to do this entirely in pass I decided to build an AST out of ANTLR's parse tree. It has a couple of node types which just store some data, like conditionNode storing if statements, assignmentNode storing assignments and the main ASTNode which captures scope and has things reference to parent, thenBranch, elseBranch and a root node which can be an assignmentNode or conditionNode. Using this structure it was easy to build out the conditions for leaf node assignments. Still would like help trying to figure out nonleaf node assignments.

5
  • Are you aware that string comparison in Java is done with the equals method, not the == operator? I'm not sure from the wording of your question whether this is the difficulty you're facing or not. Commented Nov 29, 2023 at 7:12
  • So, given an "end result", like a == "Yes", you want all the paths that lead to this result? In the case of a equals to "Yes", for example [b=="foo1", c=="foo2", d=="foo3"], [b=="foo1", c=="foo13", d!=("foo11","foo12","foo8","foo9")] , [b=="foo1", c!="foo13"], etc. Commented Nov 29, 2023 at 10:52
  • This is an algebraic rewrite problem. You want to rewrite "if e1 then e2 else e3" as the Boolean expression "(e1 and e2) or (not e1 and not e3)". You're stack should be an expression (which you never say), but you don't need one. You are rewriting if-then-else into an expression of ands, ors, and nots. Proceed recursively, bottom up, returning an expression. You can ignore a = "No" if you assume the value is set in the following statement, which it is. For "if e1 then a=yes then a=no", simply return "e1". The output expression can probably be simplified, but that is another step. Commented Nov 29, 2023 at 10:53
  • @DawoodibnKareem the pseudocode I provided is not Java, I will be converting the pseudocode to Java. Sorry that was not clear Commented Nov 29, 2023 at 14:01
  • @BartKiers yes that sounds about right Commented Nov 29, 2023 at 14:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.