Mathematical Properties

Mathematical Properties

As you type in the Grammar Lab editor, AutomataLab continuously parses the rules and instantly computes the fundamental mathematical properties of your Context-Free Grammar. These properties are required for generating robust Parse Tables in the Parser Studio.

---

1. Nullability

A non-terminal $X$ is considered nullable if it can ultimately derive the empty string ($\epsilon$).

AutomataLab uses a recursive algorithm to compute this:

1. If $X \rightarrow \epsilon$ is a rule, $X$ is nullable.
2. If $X \rightarrow Y_1 Y_2 \dots Y_n$ is a rule, and every $Y_i$ is nullable, then $X$ is nullable.

The Diagnostics panel will list every nullable non-terminal. This is critical for computing FIRST and FOLLOW sets, as nullable symbols allow the parser to "look past" them to the next symbol in the string.

---

2. FIRST Sets

The FIRST($X$) set contains all the terminal symbols that can appear as the very first character of any string derived from $X$.

If $X$ is nullable, then $\epsilon$ is also explicitly included in FIRST($X$).

Why it matters

Top-Down predictive parsers (like LL(1)) use the FIRST sets to decide which production rule to pick. If the parser is looking at non-terminal $A$, and the next input token is id, the parser checks the FIRST sets of all RHS alternatives for $A$. It will pick the rule whose FIRST set contains id.

---

3. FOLLOW Sets

The FOLLOW($X$) set contains all the terminal symbols that can appear immediately to the right of $X$ in some valid derivation.

Note that $\epsilon$ is never in a FOLLOW set. However, the special end-of-input marker $ is placed in the FOLLOW set of the Start Symbol $S$.

Why it matters

FOLLOW sets are heavily utilized by LL(1) and SLR(1) parsers.

• In LL(1): If the predictive parser needs to expand $A$, and the next token is not in any FIRST set for $A$, but $A$ is nullable, the parser checks if the token is in FOLLOW($A$). If it is, the parser safely chooses the $A \rightarrow \epsilon$ rule.
• In SLR(1): When the bottom-up parser has completely matched the RHS of $A$ on the stack, it uses FOLLOW($A$) to decide whether to Reduce. It will only reduce if the lookahead token is explicitly in FOLLOW($A$).

---

4. Left Recursion & Left Factoring

AutomataLab's Matrix panel flags two critical structural properties of your grammar:

Left Recursion

A grammar is Left Recursive if a non-terminal can derive a string that starts with itself (e.g., $A \rightarrow A \alpha$).

• Direct: $E \rightarrow E + T$
• Indirect: $A \rightarrow B$, $B \rightarrow A$

Impact: Top-Down parsers (like LL(1)) will enter an infinite loop trying to expand left-recursive rules. You must eliminate left recursion before using the LL(1) algorithm in the Parser Studio. Bottom-up parsers (LR, LALR) handle left recursion perfectly!

Left Factoring

A grammar needs Left Factoring if two or more production rules for the same non-terminal share a common prefix.

• Example: $S \rightarrow \text{if } E \text{ then } S \mid \text{if } E \text{ then } S \text{ else } S$

Impact: Predictive parsers (LL(1)) cannot decide which rule to expand because both rules have the exact same FIRST set. You must factor out the common prefix.

See Also

• Context-Free Grammars
• Grammar Transformations