Embedded Systems Group (ES)

Examples for Algorithms for Context-Free Grammars

G1: A Basic Example

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

grammar
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
word to parse

G3: ambncm+n

grammar
word to parse

G4: ambn where 2m≤n≤3m

grammar
word to parse

G5: (ab)n(cbm)n

grammar
word to parse

G6: anbmcn

grammar
word to parse

G7: ambncn

grammar
word to parse

G8: anbncm

grammar
word to parse

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

grammar
word to parse

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

grammar
word to parse

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

grammar
word to parse

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

grammar
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
word to parse

P0: Parenthesis Matching

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

grammar
word to parse