Examples for Algorithms for Context-Free Grammars

G1: A Basic Example

This grammar is a classic example for bⁿa^m+1b²ⁿ:

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: a^mbⁿc^m+n

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

G4: a^mbⁿ where 2m≤n≤3m

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

G5: (ab)ⁿ(cb^m)ⁿ

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

G6: aⁿb^mcⁿ

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

G7: a^mbⁿcⁿ

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

G8: aⁿbⁿc^m

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

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

grammar	S -> aSc | cSa | bSc | cSb | ϵ
word to parse

G14: Decimal Numbers Modulo 3

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

G15: Requires Basic Cleanups

At the end, it consists of all words on 0 and 1.

grammar	S -> 0S | BD | E0 B -> C | 1 | ϵ C -> 0 D -> 0 | A0 | S | ϵ E -> BE | SE F -> C
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: Arithmetic Prefix Expression Grammar (LL(1)-Grammar)

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

P5: Arithmetic Postfix Expression Grammar

This grammar has been rewritten to satisfy the LL(1) property:

grammar	E -> nZ | vZ Z -> ϵ | EY Y -> *Z | +Z
word to parse

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

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