Section 1.3: A Parsing Algorithm
The purpose of this section is to ensure that there is no ambiguity in wffs formed by the rules of the previous section, in particular, that there are enough parentheses to distinguish any two formulas by their final representation.
The following parsing algorithm ensures that a string of sentence symbols and characters , , , , , , and is parsed to a tree iff corresponds to a wffs, and in this case the tree is uniquely determined and represents the wff.
- Form a tree with the only vertex being the expression .
- If all leaves of the tree are sentence symbols, stop(+). Otherwise select the left-most leaf having an expression .
- The first symbol of must be , and there should be the second symbol, otherwise stop(-).
- If the second symbol is , then there should be at least four symbols in with the last symbol being , i.e. (otherwise stop(-)), form a new leaf below having , and go to step 2.
- Scan from left until first reaching where is a non-empty string having a balance of and , if no such found, then stop(-). There should be one of the four binary connective symbols after , followed by a non-empty and , otherwise stop(-). We form two leaves, the left one and the right one , below . Go to step 2.
stop(+) the tree represents the wff corresponding to the initial expression
stop(-) the initial expression does not correspond to any wff
- The algorithm is finite
The algorithm attempts to construct the tree in the only possible way, as the choice of
in step 5 is determined by the two facts: first,
must be balanced (and everything less than
was not), and, second, any proper initial subexpression of a wff has inbalance of parentheses, hence, anything longer than
would not be a proper wff expression.
- The tree is unique. In particular, this gives as a method to define the extension of a truth assignment.
- If the algorithm fails, then does not represent a wff, as the only possible way to try to understand (parse) it fails.
- If the algorithm stops in step 2, then the resulting tree represents the only possible wff corresponding to .
Instead of use . This allows to avoid both parentheses and ambiguity. The uniqueness of readability of this notation is studied in Section 2.3.
Conventions to omit parentheses whenever possible using standard notation:
- Omit outermost parentheses.
- The negation, conjunction and disjunction symbols apply to as little as possible.
- Right precedence: is understood as .
- We could have omitted right parentheses in our building rules, yet have unambiguous wffs.
- The algorithm could have also been built to parse from the bottom up, by considering the innermost pairs of parentheses.
- We could have also made left and right parentheses indistinguishable, and still have unambiguous wffs.