---
title: Unique Readability and a Parsing Algorithm
module: Sentential Logic
moduleNumber: 2
lessonNumber: 3
order: 203
summary: >
  Parentheses keep a formula from being read two ways. The parenthesis lemmas and
  a top-down parsing algorithm recover a formula's structure and yield unique
  readability: every wff has exactly one formation tree, which is what makes the
  truth recursion well defined.
topics: [Sentential Logic]
sources:
  - book: Enderton
    ref: "Ch. 1 — Sentential Logic; §1.3 A Parsing Algorithm"
draft: false
---

The truth recursion assigns $\bar v(\varphi)$ by climbing the formation tree of
$\varphi$, which makes sense only if $\varphi$ has _one_ formation tree. It does:
the parentheses in the definition of a wff leave no formula ambiguous.

Without parentheses, ambiguity is immediate. The string $A_1 \vee A_2 \wedge A_3$
can be assembled two ways, as $((A_1 \vee A_2) \wedge A_3)$ or as
$(A_1 \vee (A_2 \wedge A_3))$. Under $v(A_1) = T$, $v(A_3) = F$ the two readings
disagree — the first is $F$ (its conjunction has a false right conjunct), the
second $T$ (its disjunction has a true left disjunct) — so $\bar v$ would have no
well-defined value. The parentheses in every $\mathcal{E}_\square(\alpha, \beta)$
exist to forbid exactly this.[^enderton-parse]

## The parenthesis lemmas

Two facts about how parentheses distribute in a wff are used throughout. The first
was proved in the [formation
lesson](/logic/sentential-logic/formal-languages-and-well-formed-formulas).

> **Lemma (Balanced parentheses in wffs).** Every wff has equally many left and right parentheses.

> **Lemma (Proper initial segments of wffs).** Any proper initial segment of a wff has more left parentheses
> than right. Consequently no proper initial segment of a wff is itself a wff.

The consequence follows from the lemma with the parenthesis-balance lemma: a wff is balanced, but a proper
initial segment is left-heavy, so a proper initial segment cannot be a wff.

> **Proof of the initial-segment lemma.** Apply the induction principle to the set $S$ of wffs all of
> whose proper initial segments are left-heavy. A sentence symbol has no proper
> initial segments, so it lies in $S$ vacuously. For closure under
> $\mathcal{E}_\wedge$, take $\alpha, \beta \in S$ and list the proper initial
> segments of $(\alpha \wedge \beta)$:
>
> - $($ — one excess left parenthesis;
> - $(\alpha_0$ where $\alpha_0$ is a proper initial segment of $\alpha$ — the
>   leading $($ plus the excess $\alpha_0$ carries by the inductive hypothesis;
> - $(\alpha$ — the leading $($ over the balanced $\alpha$;
> - $(\alpha\wedge$ — same, with a connective added;
> - $(\alpha \wedge \beta_0$ with $\beta_0$ a proper initial segment of $\beta$ —
>   leading $($, balanced $\alpha$, excess in $\beta_0$;
> - $(\alpha \wedge \beta$ — leading $($ over two balanced pieces.
>
> Every case is left-heavy. The other operations are handled the same way, so $S$
> is closed and, by induction, contains all wffs. $\blacksquare$

The running count of unmatched left parentheses makes the lemma visual. Scan a
wff left to right, adding $1$ at each $($ and subtracting $1$ at each $)$. The
parenthesis-balance lemma says the count returns to $0$ at the end; the
initial-segment lemma says it stays strictly
positive at every proper initial segment along the way.

$$
% caption: Unmatched left parentheses while scanning a wff left to right. The
% count ends at zero (balanced) but is strictly positive at every proper initial
% segment, so no prefix closes off into a wff of its own.
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (0,0) -- (9.2,0) node[right, font=\footnotesize] {position};
  \draw[->, black] (0,0) -- (0,3.0) node[above, font=\footnotesize] {unmatched left parentheses};
  \foreach \y in {1,2} \draw[black] (0,\y) -- (9,\y);
  \foreach \y in {1,2} \node[anchor=east, font=\scriptsize] at (-0.1,\y) {\y};
  % step plot for ( ( A and B ) implies C )
  \draw[acc, very thick]
    (0,0) -- (0.9,0) -- (0.9,1) -- (1.8,1) -- (1.8,2) -- (4.5,2)
    -- (4.5,1) -- (7.2,1) -- (8.1,1) -- (8.1,0) -- (9.0,0);
  \fill[acc] (9.0,0) circle (2pt);
  \node[acc, anchor=south west, font=\scriptsize] at (7.3,1.05) {stays above zero};
  \node[anchor=north, font=\scriptsize] at (9.0,-0.05) {closes};
\end{tikzpicture}
$$

> **Worked example.** Run the unmatched-parenthesis count along
> $((A \wedge B) \to C)$.
>
> Reading left to right, add $1$ at each $($ and subtract $1$ at each $)$:
>
> $$
> \underbrace{(}_{1} \; \underbrace{(}_{2} \; \underbrace{A}_{2} \; \underbrace{\wedge}_{2} \; \underbrace{B}_{2} \; \underbrace{)}_{1} \; \underbrace{\to}_{1} \; \underbrace{C}_{1} \; \underbrace{)}_{0}
> $$
>
> The count reaches $2$ after the two opening parentheses, drops to $1$ at the
> inner $)$, and returns to $0$ only at the final symbol. It stays strictly
> positive at every proper initial segment, as the initial-segment lemma
> requires, so no prefix such as $((A \wedge B)$ closes off into a wff of its own.

## The parsing algorithm

The initial-segment lemma forces every choice a parser could make. The algorithm reads an
expression and either rejects it or builds its formation tree from the top down,
splitting each compound at its principal connective.

```algorithm
caption: $\textsc{Parse}(\varepsilon)$ — build the formation tree of an expression, or reject
place $\varepsilon$ at the root; mark it the only vertex
repeat
  if every minimal vertex holds a sentence symbol then
    return the tree // $\varepsilon$ is a wff
  select a minimal vertex whose expression $\mu$ is not a sentence symbol
  if the first symbol of $\mu$ is not "(" then reject
  if the second symbol of $\mu$ is "$\neg$" then
    $\mu$ must be $(\neg\, \beta)$ with $\beta$ an expression
    attach one child holding $\beta$
  else
    scan from the left to the shortest $(\alpha$ with $\alpha$ balanced and nonempty
    the next symbol must be a binary connective // the principal connective
    the remainder must be $\beta)$ with $\beta$ an expression
    attach children holding $\alpha$ and $\beta$
until the tree is complete
```

Four observations establish correctness.[^enderton-parse]

- **Termination.** Each child holds a strictly shorter expression than its
  parent, so the tree depth is bounded by the length of $\varepsilon$.
- **Forced choices.** In the binary case the first constituent must be exactly
  $\alpha$: any shorter prefix is unbalanced (violating the parenthesis-balance
  lemma applied to a
  would-be constituent), and any longer one contains the balanced $\alpha$ as a
  proper initial segment (violating the initial-segment lemma). The principal connective and the
  second constituent are then determined.
- **Rejection is sound.** If the algorithm rejects, the only possible attempt to
  build a tree has failed, so $\varepsilon$ was no wff.
- **Acceptance is sound.** If it succeeds, working up the finished tree shows
  every vertex holds a wff, the root included.

$$
% caption: The parsing decision flow for one non-atomic vertex; every branch is
% forced, so the tree it produces is the only tree the expression admits.
\begin{tikzpicture}[font=\footnotesize, node distance=6mm,
  box/.style={draw, minimum width=34mm, minimum height=9mm, align=center, font=\scriptsize},
  dec/.style={draw, diamond, aspect=2, inner sep=1pt, align=center, font=\scriptsize},
  term/.style={draw=acc, minimum width=24mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[box] (pick) at (0,4.2) {pick a non-atomic\\minimal vertex};
  \node[dec] (p1) at (0,2.7) {leading symbol\\a left paren?};
  \node[term] (rej) at (5.2,2.7) {reject};
  \node[dec] (p2) at (0,1.0) {second symbol\\a negation?};
  \node[box] (un) at (-3.2,-0.7) {one child:\\the body};
  \node[box] (bin) at (2.8,-0.7) {split at balanced\\initial segment; two children};
  \node[term] (loop) at (0,-2.4) {return to vertex list};
  \draw[->, black] (pick) -- (p1);
  \draw[->, black] (p1) -- node[above, font=\scriptsize] {no} (rej);
  \draw[->, black] (p1) -- node[right, font=\scriptsize] {yes} (p2);
  \draw[->, black] (p2) -- node[above left, font=\scriptsize] {yes} (un);
  \draw[->, black] (p2) -- node[above right, font=\scriptsize] {no} (bin);
  \draw[->, black] (un) |- (loop);
  \draw[->, black] (bin) |- (loop);
\end{tikzpicture}
$$

> **Worked example.** Parse $((A \vee B) \wedge C)$.
>
> The first symbol is $($ and the second is $A$, not $\neg$, so the principal
> connective is binary. Scan from just past the opening $($ for the shortest
> balanced nonempty initial segment: $(A$ is left-heavy, $(A \vee$ is left-heavy,
> and $(A \vee B)$ is the first balanced one, so the first constituent is
> $\alpha = (A \vee B)$. The next symbol $\wedge$ is the principal connective, and
> the remainder $C)$ gives $\beta = C$. The vertex splits as
> $\mathcal{E}_\wedge((A \vee B), C)$; recursing on $(A \vee B)$ splits it as
> $\mathcal{E}_\vee(A, B)$. Every choice was forced, so this is the only tree.

## Unique readability

Because every choice the parser makes is forced, it constructs the _only_
possible tree for the given wff. This is the central syntactic fact of the
language.

> **Theorem (Unique readability).** Every wff has exactly one formation tree. Equivalently,
> the five formula-building operations, restricted to wffs, are one-to-one and
> have pairwise-disjoint ranges disjoint from the sentence symbols.

The language is unambiguous, and the parser exhibits the tree — what the truth
recursion needed. For any wff $\varphi$ there is one tree; propagating values up
it assigns $\bar v(\varphi)$ without ambiguity, and the resulting function meets
the recursion clauses. So $\bar v$ exists, completing the half of the
unique-extension theorem left open under
[truth assignments](/logic/sentential-logic/truth-assignments-and-tautologies).
The general form of this "unique readability licenses recursion" argument is the
[recursion theorem](/logic/sentential-logic/induction-and-recursion).

$$
% caption: An almost-ambiguous string is pinned to a single reading by its
% parentheses: the outer conjunction, not the disjunction, is the principal
% connective, so only the left tree is a legal parse.
\begin{tikzpicture}[font=\footnotesize, level distance=12mm,
  op/.style={draw, circle, minimum size=7mm, inner sep=0pt, font=\scriptsize},
  lf/.style={draw, minimum size=6mm, inner sep=1pt, font=\scriptsize},
  no/.style={draw, circle, minimum size=7mm, inner sep=0pt, font=\scriptsize, dash pattern=on 2pt off 1.5pt}]
  \definecolor{acc}{HTML}{4A6FA5}
  % legal reading
  \node[op, draw=acc, text=acc] (a) at (0,0) {and};
  \node[op] (o) at (-1,-1.4) {or};
  \node[lf] (c) at (1,-1.4) {C};
  \node[lf] (aa) at (-1.8,-2.6) {A};
  \node[lf] (bb) at (-0.2,-2.6) {B};
  \draw[black] (a)--(o); \draw[black] (a)--(c);
  \draw[black] (o)--(aa); \draw[black] (o)--(bb);
  \node[font=\scriptsize, text=acc] at (-0.3,0.8) {the only legal tree};
  % rejected reading
  \begin{scope}[xshift=6cm]
    \node[no] (o2) at (0,0) {or};
    \node[lf] (a2) at (-1,-1.4) {A};
    \node[no] (a3) at (1,-1.4) {and};
    \node[lf] (b2) at (0.2,-2.6) {B};
    \node[lf] (c2) at (1.8,-2.6) {C};
    \draw[black, dash pattern=on 2pt off 1.5pt] (o2)--(a2); \draw[black, dash pattern=on 2pt off 1.5pt] (o2)--(a3);
    \draw[black, dash pattern=on 2pt off 1.5pt] (a3)--(b2); \draw[black, dash pattern=on 2pt off 1.5pt] (a3)--(c2);
    \node[font=\scriptsize] at (0.3,0.8) {forbidden by the parentheses};
  \end{scope}
\end{tikzpicture}
$$

The figure shows the two readings of $((A \vee B) \wedge C)$: only the tree whose
root is the conjunction is a legal parse, because the outermost matched pair of
parentheses encloses $(A \vee B) \wedge C$ with $\wedge$ as its principal
connective.

## Polish notation

Parentheses are one way to avoid ambiguity; they are not the only way. **Polish
(prefix) notation** writes the connective before its arguments and drops the
parentheses entirely. In place of $(\alpha \wedge \beta)$ one writes
$\wedge \alpha \beta$, and the P-wffs are generated from the sentence symbols by

$$
D_{\neg}(\alpha) = \neg\alpha, \quad
D_{\wedge}(\alpha,\beta) = \wedge\alpha\beta, \quad
D_{\vee}(\alpha,\beta) = \vee\alpha\beta, \quad
D_{\to}(\alpha,\beta) = {\to}\alpha\beta, \quad
D_{\leftrightarrow}(\alpha,\beta) = {\leftrightarrow}\alpha\beta.
$$

$$
% caption: The same formula parenthesized (infix) and in parenthesis-free Polish
% prefix notation; the connective moves ahead of its operands, and no punctuation
% is needed to recover the structure.
\begin{tikzpicture}[font=\footnotesize,
  b/.style={draw, minimum width=54mm, minimum height=11mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[b] (infix) at (0,0.9) {standard: ( ( A and B ) implies C )};
  \node[b, draw=acc, text=acc] (pol) at (0,-0.6) {Polish: implies and A B C};
  \draw[->, black] (infix) -- (pol);
\end{tikzpicture}
$$

Polish notation is well suited to machine processing; compilers routinely convert
input formulas into it. Its own unique readability theorem is proved in the
[first-order parsing
lesson](/logic/first-order-languages/terms-substitution-and-parsing), where the
parenthesis-free case reappears.

## Omitting parentheses

For readability, some parentheses are dropped by convention when naming wffs, with
precedence rules restoring them.

- **Outermost parentheses** are omitted: $A \wedge B$ names $(A \wedge B)$.
- **Negation binds tightest**: $\neg A \wedge B$ is $((\neg A) \wedge B)$, not
  $(\neg (A \wedge B))$.
- **Conjunction and disjunction bind tighter than the conditional and
  biconditional**: $A \wedge B \to \neg C \vee D$ is
  $((A \wedge B) \to ((\neg C) \vee D))$.
- **Repeated connectives group to the right**: $\alpha \to \beta \to \gamma$ is
  $(\alpha \to (\beta \to \gamma))$.

These abbreviations violate the strict naming rules on purpose; the license is
harmless because only wffs are ever named, and each abbreviation restores to
exactly one wff.

[^enderton-parse]: Enderton, §1.3 — the ambiguity of unparenthesized strings, Lemmas 13A and 13B, the top-down parsing algorithm with its four correctness observations, unique readability, Polish notation, and the parenthesis-omission conventions.