CODEWITHSUNDEEP
context-free-grammar
Chaos
Chaos

Reputation: 307

Does order matter in context free grammar?

let say i have the follow grammar:

expr = expr + term | term    
term = term +  number | number    
number = (just any integers..)

My question is, is expr = expr + term | term same as expr = term + expr | term?

I expanded the grammar, and it seems does matter. am i correct?

Upvotes: 1

Views: 1485

Answers (2)

Patrick87
Patrick87

Reputation: 28292

The answer, of course, is that it depends on the grammar.

In your case, replacing one rule for the other does not change the set of strings in the language generated by the grammar. The grammar is different, but the language is the same. The only difference is that the first builds strings from the right, and the second builds strings from the left.

It's not hard to come up with grammars where this does not work: sometimes, changing the order of symbols in a production will change the language.

Upvotes: 0

placeybordeaux
placeybordeaux

Reputation: 2216

No they are not the same. Order matters. For examples look at http://en.wikipedia.org/wiki/Context-free_grammar#Example

Upvotes: 1

Related Questions