Section 1.3: Problem 1 Solution »

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.

Parsing Algorithm

The following parsing algorithm ensures that a string $s$ of sentence symbols and characters $($ , $)$ , $\neg$ , $\wedge$ , $\vee$ , $\rightarrow$ , and $\leftrightarrow$ is parsed to a tree iff $s$ corresponds to a wffs, and in this case the tree is uniquely determined and represents the wff.
1. Form a tree with the only vertex being the expression $s$ .
2. If all leaves of the tree are sentence symbols, stop(+). Otherwise select the left-most leaf having an expression $s'$ .
3. The first symbol of $s'$ must be $($ , and there should be the second symbol, otherwise stop(-).
4. If the second symbol is $\neg$ , then there should be at least four symbols in $s'$ with the last symbol being $)$ , i.e. $s'=(\neg s'')$ (otherwise stop(-)), form a new leaf below $s'$ having $s''$ , and go to step 2.
5. Scan $s'$ from left until first reaching $(s''$ where $s''$ is a non-empty string having a balance of $($ and $)$ , if no such $s''$ found, then stop(-). There should be one of the four binary connective symbols after $s''$ , followed by a non-empty $s'''$ and $)$ , otherwise stop(-). We form two leaves, the left one $s''$ and the right one $s'''$ , below $s'$ . 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 $s''$ in step 5 is determined by the two facts: first, $s''$ must be balanced (and everything less than $s''$ was not), and, second, any proper initial subexpression of a wff has inbalance of parentheses, hence, anything longer than $s''$ 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 $s$ 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 $s$ .

Polish notation

Instead of $(\alpha\square\beta)$ use $\square\alpha\beta$ . This allows to avoid both parentheses and ambiguity. The uniqueness of readability of this notation is studied in Section 2.3.

Conventions

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: $\alpha\square\beta\square\gamma$ is understood as $(\alpha\square(\beta\square\gamma))$ .

Other facts

• 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.