= Sentential form
A sentential form of a <formal grammar> $G=(N,\Sigma,P,S)$ is any word $\alpha\in(N\cup\Sigma)^*$ derivable from the start symbol: $S\Rightarrow^*\alpha$. It may contain both <terminal symbols> and <nonterminal symbols>. A terminal-only sentential form is a word of the generated <formal language>.
For productions $S\to aSb$ and $S\to\varepsilon$, the derivation $S\Rightarrow aSb\Rightarrow aaSbb\Rightarrow aabb$ contains four sentential forms. The intermediate $aaSbb$ is not a sentence of the terminal language because $S$ remains. An arbitrary word over $N\cup\Sigma$ need not be a sentential form: it must actually be reachable by a <grammar derivation>.
Tracking sentential forms makes it possible to discuss intermediate parsing states and distinguish <leftmost derivations> from other orders of rewriting. The word need not be a complete output or a prefix of one in an arbitrary grammar.
Back to article page
