Making context free grammars simpler(prettier)

Question

I'm working with CFG and every time I write up rules to a particular language, my CFG ends up disgusting. It ends up as one line:

S->tooooooo much stuff

I know that putting things into chomsky normal form will put it in the correct format and things will be prettier but I was wondering if there are any ideas to keep in mind for making these look less cluttered.

i.e., lang:

a^n b^m, where n >= m

My CFG (gross):

S -> Sa|Sab|Sba|aS|aSb|abS|bSa|baS|ε

Can anyone help me with my bad habits?

I'm sorry, I messed up which language I was using. I was actually doing one very similar, but the difference is that it didn't matter what order the a's and b's were in. — Riveascore

Markus Jarderot Markus Jarderot · Accepted Answer · 2011-12-02T10:37:04

Do you really need to use CFG to describe this simple language? It would be much easier to just count the a's and b's.

But assuming this is just an example...

CFG's in real parsers usually split it up to one production per line, and group them in some reasonable way.

S -> a b S
   | b a S
   | a S
   | a S b
   | b S a
   | ε

Making context free grammars simpler(prettier)

1 Answers