# Examples for Algorithms for Context-Free Grammars

## G1: A Basic Example

This grammar is a classic example for b^{n}a^{m+1}b^{2n}:

## G2: A Variant of G1

This grammar is obtained from G1 by elimination of left factors, so that it becomes LL(1):

## G3: a^{m}b^{n}c^{m+n}

## G4: a^{m}b^{n} where 2m≤n≤3m

## G5: (ab)^{n}(cb^{m})^{n}

## G6: a^{n}b^{m}c^{n}

## G7: a^{m}b^{n}c^{n}

## G8: a^{n}b^{n}c^{m}

## G9: L(G9) = { w | #(a) = #(b)}

## G10: L(G10) = { w | #(a) < #(b)}

## G11: L(G11) = { w | #(a) != #(b)}

## G12: L(G12) = { w | #(a)+#(a) = #(b)}

## G11: Decimal Numbers Modulo 3

This grammar derives decimal numbers that are multiples of 3. Note that *(x*10 ^{n}+y) mod 3 = ((x mod 3) * (10^{n} mod 3) + (y mod 3)) mod 3 = ((x mod 3) + (y mod 3)) mod 3* which simply explains the rule that a decimal number modulo 3 is the same as the sum of its digits modulo 3. Note that P,Q,R have remainder 0,1,2, respectively, and also A,B,C have remainders 0,2,1, respectively:

## P0: Parenthesis Matching

## P1: Arithmetic Expressions (Ambiguous Grammar)

The simple grammar for arithmetic expressions below is ambiguous, in particular, it does not consider operator precedences and associativities:

## P2: Arithmetic Expressions with Operator Precedences

The grammar for arithmetic expressions below considers operator precedences and associativities (it is SLR(1) but not LL(1)):

## P3: Arithmetic Expression Grammar (LL(1)-Grammar)

Eliminating the left recursion in the previous grammar yields the one below that is now LL(1) and therefore also SLR(1) so that both kinds of deterministic parsers can handle it:

## P4: A Little Programming Language

This grammar describes a little programming language with sequences, assignments, if-then-else with and without else clauses, while loops and do-while loops. There is no problem with dangling else since the statements use e as end symbol. The grammar is SLR(1), but not LL(1):

## P4: Solution to Dangling Else

This grammar describes a solution to the dangling else problem: Note that C and
E represent conditions and expressions, respectively, where v is any variable,
n any arithmetic expression, and b any boolean expression. S will generate a
finite sequence of open and closed statements represented by O and Z, respectively.
Open statements are of the form (iCZe)^{*}iCZ, thus having a final open
if statement while the closed statements consist only of the listed statements.
Parse a few examples:

- v=n;
- v=n;v=n;
- wbv=n;v=n;
- wb{v=n;v=n;}v=n;
- ibv=n;v=n;
- ibv=n;ibv=n;ev=n;
- ibv=n;ib{v=n;ev=n;}
- ibv=n;wbv=n;
- ib{v=n;wbv=n;}
- ib{v=n;wbv=n;}ev=n;
- ibv=n;ibv=n;ev=n;
- ib{v=n;ibv=n;}ev=n;