Grammar Construction - Oya-Learning-Notes/Compilers GitHub Wiki

[!Note]

This passage only records some unusual construction and would NOT be an exhaustive list.

$a^nb^nc^n,\; n\ge1$

$$ \begin{aligned} S &\to ASBC \ S &\to ABC \ CB &\to BC \ A &\to a \ aB &\to ab \ bB &\to bb \ bC &\to bc \ cC &\to cc \end{aligned} $$

Both sufficiency and necessity of this grammar could be proved.

How Terminal Order Be Promised

How this grammar promises the correct order of $a,b,c$:

  1. $A$ will always appear before any $B$ and $C$ non-terminal.
  2. $CB \to BC$ allows all string like $BCBCBC\dots$ to be sorted into $BBBCCC \dots$
  3. Grammar promised non-terminal to terminal production will be performed only when non-terminal are well sorted.

Let's look into the third point now, consider we have a non-well-sorted string $ABCCB$, and we try to perform production to convert it into a sentence (only have terminal):

$$ \begin{aligned} ABCCB &\Rightarrow aBCCB \ &\Rightarrow abCCB \ &\Rightarrow abcCB \ &\Rightarrow abccB \ &Oops! ;No;valid;production.; \end{aligned} $$

Since we don't have something like $cB \to cb$, if a non-terminal $B$ is behind $c$ or $C$, it could never be converted to any terminal (terminal $b$ in this case), therefore will not finally produce a valid sentence.