Section 1.3: A Parsing Algorithm

Parsing Algorithm

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.

• 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

Conventions

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