Part 6: Other approaches (Bonus)
Order of precedence
Incorporating precedence rules into the existing grammar is a challenging task. This complexity arises from the need to avoid left recursion, which is not supported by many parser generators. Additionally, determining the correct order of operations and resolving ambiguities during parsing requires careful consideration. The order of operations is as follows:
- Parenthesis
- Negation
- Conjunction
- Disjunction
- Implication
- Equivalence
Three important factors to consider when defining the grammar are the order of operations, the recursive use of parentheses and the grouping for associative operations.
Order of operations
The wff should be parsed recursively in the opposite order of operations to group in the correct order, with each rule recursively leading to the next rule. For instance, in the expression: $A ∨ B → C \wedge ¬D ↔ E \wedge (F ↔ G)$, the grouping is actually: $ (((A ∨ B) → (C \wedge ¬D)) ↔ (E \wedge (F ↔ G))) $.
Recursive use of parentheses
To enable the use of parentheses recursively, the rule must be connected back to the first operation, the equivalence rule. And at some point A choice has to be made between the atom rule or the parenthesis rule, which is achieved with the ordered choice expression ‘|’. This allows the following wff to be recognized: $ ((A ∨ B) ∧ (C ∨ D)) $.
Grouping for associative operations
Using the repetition operator * allows for the grouping of associative operations by allowing zero or more repetitions. For example: $ A ∨ B ∨ C => D $, can be grouped as $ ((A ∨ B ∨ C) => D) $ rather than $ (((A ∨ B) ∨ C) => D) $. Additionally, the optional operator ? can be used to restrict the implication rule and prevent ambiguity when used consecutively. An ambiguous expression that is not accepted by the language is: $ A => B => C $, because $ (A => B) => C $ is not evaluated the same as $ A => (B => C) $, i.e., the implication operator is not associative.
Model: Equivalence;
Equivalence: (Implication '<=>' )* Implication;
Implication: (Disjunction '=>' )? Disjunction;
Disjunction: (Conjunction '|' )* Conjunction;
Conjunction: (Negation '&' )* Negation;
Negation: ('~')* Atom;
Atom: ID | Parenthesis;
Parenthesis: '(' Equivalence ')';
Iterative design
Rather than using recursion to create the string, we can use iteration. Iteration is less likely to have a stack overflow, more space-efficient and often faster due to avoiding function call overhead. The downside is that the algorithm may be slightly more difficult to read and write.
An appropriate way to iterate over the AST while maintaining correct parenthesis enclosing is to use the depth-first post-order traversal. In that way, we can build the string bottom-up and add parenthesis when a binary connective is visited. Because the AST is not a binary tree, we must specify how to traverse an atom, a negation and binary connectives.
How to traverse the next node will depend on the current node (wff) in the AST. An Atom object is a leaf node, so it has no next node to return. A Negation object only has one child, and binary connectives have exactly two children. Translating to code gives us:
def match_case_next(wff: WFF, left_direction: bool=True) -> Union[WFF, None]:
match wff.__class__.__name__:
case Atom.__name__:
return None
case Negation.__name__:
return wff.wff
case _:
if left_direction:
return wff.lhs
else:
return wff.rhs
To avoid looping infinitely, the algorithm also needs to know if a child has already been visited.
def match_case_not_visited(wff: WFF, lastVisited: WFF) -> bool:
match wff.__class__.__name__:
case Atom.__name__:
return False
case Negation.__name__:
return not (wff.wff is lastVisited)
case _:
return not (wff.rhs is lastVisited)
In post-order traversal, we first traverse the left subtree of a node, then traverse the right subtree, and finally visit the node itself. This means that we visit a node only after visiting all of its children. As we traverse the tree, we move from left to right, visiting each node bottom-up. This approach ensures that we visit the children of a node before visiting the node itself. The traversal algorithm is as follows:
def build_traversal_post_order(wff: WFF) -> List[WFF]:
traversal = []
stack = []
lastVisited = None
while len(stack) > 0 or wff != None:
if wff != None:
stack.append(wff)
wff = match_case_next(wff)
else:
peeked = stack[-1]
if match_case_not_visited(peeked, lastVisited):
wff = match_case_next(peeked, left_direction=False)
else:
traversal.append(peeked)
lastVisited = stack.pop()
return traversal
After creating a traversal list, we can just iterate over it and conditionally build the string. The approach here is to build the subformulas first and then combine them bottom-up.
def build_string(traversal_list: List[WFF]) -> str:
stack = []
for wff in traversal_list:
match wff.__class__.__name__:
case Atom.__name__:
stack.append(wff.id)
case Negation.__name__:
if len(stack) > 0:
stack.append("¬" + stack.pop())
else:
stack.append("¬")
case Conjunction.__name__:
rhs = stack.pop()
lhs = stack.pop()
stack.append(f"({lhs} ∧ {rhs})")
case Disjunction.__name__:
rhs = stack.pop()
lhs = stack.pop()
stack.append(f"({lhs} ∨ {rhs})")
case Implication.__name__:
rhs = stack.pop()
lhs = stack.pop()
stack.append(f"({lhs} → {rhs})")
case Equivalence.__name__:
rhs = stack.pop()
lhs = stack.pop()
stack.append(f"({lhs} ↔ {rhs})")
return "".join(stack)
We can then convert our wff to a string:
def wff_to_string(wff: WFF) -> str:
traversal = build_traversal_post_order(wff)
return build_string(traversal)
You’ve made it this far, well done! Up next is the conclusion.