# Examples for Algorithms for Context-Free Grammars

## G1: A Basic Example

This grammar is a classic example for bnam+1b2n:

 grammar S -> A | bSbb A -> aA | a word to parse

## G2: A Variant of G1

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

 grammar S -> A | bSbb A -> aB B -> A | ϵ word to parse

## G3: ambncm+n

 grammar A -> aAc | B B -> bBc | ϵ word to parse

## G4: ambn where 2m≤n≤3m

 grammar S -> aSbb | aSbbb | ϵ word to parse

## G5: (ab)n(cbm)n

 grammar S -> ϵ | abScB B -> b | bB word to parse

## G6: anbmcn

 grammar S -> aSc | bS | ϵ word to parse

## G7: ambncn

 grammar S -> bSc | aS | ϵ word to parse

## G8: anbncm

 grammar S -> aSb | Sc | ϵ word to parse

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

 grammar S -> ϵ | aSbS | bSaS word to parse

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

 grammar S -> TbS | TbT T -> ϵ | aTbT | bTaT word to parse

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

 grammar S -> U | V U -> TbU | TbT V -> TaV | TaT T -> ϵ | aTbT | bTaT word to parse

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

 grammar S -> ϵ | aSbSbS | bSaSbS | bSbSaS word to parse

## G11: Decimal Numbers Modulo 3

This grammar derives decimal numbers that are multiples of 3. Note that (x*10n+y) mod 3 = ((x mod 3) * (10n 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:

 grammar A -> PA | QB | RC | B -> RA | PB | QC C -> QA | RB | PC P -> 0 | 3 | 6 | 9 Q -> 1 | 4 | 7 R -> 2 | 5 | 8 word to parse

## P0: Parenthesis Matching

 grammar S -> a | (S+S) word to parse

## P1: Arithmetic Expressions (Ambiguous Grammar)

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

 grammar E -> E+E | E*E | (E) | n | v word to parse

## 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)):

 grammar E -> E+T | T T -> T*F | F F -> (E) | n | v word to parse

## 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:

 grammar E -> TZ T -> FY F -> n | v | (E) Z -> ϵ | +TZ Y -> ϵ | *FY word to parse

## 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):

 grammar S -> A | A;S A -> v=E | v[D]=E | i(B)Se |i(B)SlSe | w(B)Se | dSw(B) B -> ErE D -> E | E,D E -> T | E+T T -> F | T*F F -> n | v | (E) word to parse

## 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;

 grammar S -> ZS | OS | Z -> v=E; | iCZeZ | wCZ | dZwC | {S} O -> iCZ | iCZeO C -> b E -> v | n word to parse