Developing Cfgs

Developing CFGs
Developing CFGs is much like programming; there are no hard-andfast rules. Here are reasonably general rules of the thumb for arriving at CFGs:

1. (Use common idioms): Study and remember many common patterns of CFGs and use what seems to fit in a given context. Example: To get the effect of matched brackets, the common idiom is
S -> ( S ) | e.

2. Break the problem into simpler problems: Example: {ambn | m = n, m, n ≥ 0}.
a) So, a’s and b’s must still come in order.
b) Their numbers shouldn’t match up.

i. Formulate matched up a’s and b’s
M -> e | a M b

ii. Break the match by adding either more A’s or more B’s
S -> A M | M B
A -> a | a A
B -> b | b B