BACKEND: Parser Optimizations for Nested Cases in Parenthesis

[JMAR059]

Currently both relationParsing.py and booleanParsing.py when encountering parenthesis on the current position, will go forward to find the segment of encapsulated by the parenthesis and call the parsing function recursively on that segment:

R - (S ∧ (A ∧ B)) ⨯ T
    ^           ^
    |           |
start position  |
                L  matching parenthesis, calls relationalParsing( "S ∧ (A ∧ B)", relations, debug)

This would make the parser run in worse case O(n^2), on top of having recursion overhead.

The best implementation would be using a stack algorithm to use parenthesis to save part of nodes, then complete the built based on what is on top of the queue when finding a right hand ')'. A high level overview using the example would be:

1: R - (S ∧ (A ∧ B) ) ⨯ T
     ^
     Stack: _
     Current Node: (R - _)

2: R - (S ∧ (A ∧ B) ) ⨯ T
       ^
     Stack: (R - _)      # Added to stack
     Current Node: _

3: R - (S ∧ (A ∧ B) ) ⨯ T
          ^
     Stack: (R - _)
     Current Node: (S ∧ _)

4: R - (S ∧ (A ∧ B) ) ⨯ T
            ^
     Stack: (S ∧ _) --> (R - _)    # Added to stack
     Current Node: _

5: R - (S ∧ (A ∧ B) ) ⨯ T
                 ^
     Stack: (S ∧ _) --> (R - _)
     Current Node: (A ∧ B)

6: R - (S ∧ (A ∧ B) ) ⨯ T
                  ^
     Stack: (R - _)     # Stack popped
     Current Node: (S ∧ (A ∧ B))

7: R - (S ∧ (A ∧ B) ) ⨯ T
                    ^
     Stack: _             # Stack popped
     Current Node: (R - (S ∧ (A ∧ B) ) )

8: R - (S ∧ (A ∧ B) ) ⨯ T
                         ^
     Stack: _ 
     Current Node: (R - (S ∧ (A ∧ B) ) ) ⨯ T

   # Final Statement: (R - (S ∧ (A ∧ B) ) ) ⨯ T

This implementation would be O(n) and not use recursion.

Each element in the stack may be different, there could always be singleton operations that do not explicitly use the right hand side to build next, such as σ_{id} (R x S). Where the select operation will wait for a 'Left Hand Side' node. Just a small edge case to consider.

To verify this implementation works, have unit cases and that all test pass before and after.