Section 2.3: A Parsing Algorithm

Terms

• $K(x)=1$ ($x$ is a term by itself, so its appearance in the string adds one complete term).
• $K(c)=1$ (same for constants).
• $K(f)=1-n$ where $f$ is an $n$ -place function symbol (a function symbol implies that there will be a complete term, $+1$ , once all $n$ terms, arguments of $f$ , are found in the string, $-n$ ).
• $K(s_{1}\ldots s_{n})=K(s_{1})+\ldots+K(s_{n})$ .

Parsing Algorithm

1. Form a tree with the only vertex being the expression $s$ .
2. If all leaves of the tree are single symbol strings, then if they all are variable or constant symbols, stop(+), otherwise, stop(-). Otherwise select the left-most leaf $s'$ having at least two symbols.
3. The first symbol of $s'$ must be an $n$ -place function symbol $f$ , otherwise stop(-).
4. We form $n$ leaves below $s'$ . Scan $s'$ after the symbol $f$ until the initial segment $t$ such that $K(t)=1$ is found. Put it the leftmost leaf. Proceed with the remainder of the string the same way for all other leaves below $s'$ . If the string ended before all terms for $n$ leaves are found, or if the last term is found before the end of the string $s'$ , stop(-). Go to step 2.

• The algorithm is finite
• The algorithm attempts to construct the tree in the only possible way, as the choice of each term $t$ in step 4 is determined by the two facts: first, $K(t)$ must equal $1$ (and for every shorter string it was not), and, second, for any proper initial substring $t_{0}$ of a term $K(t_{0})<1$ , hence, anything longer than $t$ would not be a term.
  • Hence, the tree is unique.
  • If the algorithm fails, then $s$ does not represent a term, 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 term corresponding to $s$ .

Formulas

• $K(()=-1$ .
• $K())=1$ .
• $K(\forall)=-1$ .
• $K(\neg)=0$ .
• $K(\rightarrow)=-1$ .
• $K(P)=1-n$ where $P$ is an $n$ -place predicate symbol.
• $K(=)=-1$ .

Parsing Algorithm

1. Form a tree with the only vertex being the expression $s$ .
2. If all leaves of the tree are atomic formulas (an $n$ -place predicate symbol followed by $n$ terms), stop(+). Otherwise select the left-most leaf $s'$ that is not an atomic formula.
3. The first symbol(s) of $s'$ must be either $($ or $\forall v_{i}$ , followed by other symbols, if not, stop(-). If $s'$ is $\forall v_{i}s''$ , form one leaf below it with $s''$ , and go to step 2.
4. If the second symbol of $s'$ is $\neg$ , then there should be at least four symbols in $s'$ with the last symbol being $)$ , i.e. $s'=(\neg\mbox{s''})$ (otherwise stop(-)), form one leaf below $s'$ with $s''$ , and go to step 2.
5. Scan $s'$ from left until first reaching $(s''$ where $s''$ is a non-empty string having either $K(s'')=1$ or a balance of $($ and $)$ (both methods work!), if no such $s''$ found, then stop(-). There should be a binary connective symbol ($\rightarrow$ ) 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 have $K(s'')=1$ or be balanced (and everything less than $s''$ was not), and, second, any proper initial subexpression of a wff has $K$ less than 1 or unequal number of left and right parentheses, hence, anything longer than $s''$ would not be a proper wff expression.
  • Hence, the tree is unique.
  • 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$ .