CODEWITHSUNDEEP
cparsingcompiler-construction
user2309856
user2309856

Reputation: 99

Left derivation and right derivation for the following grammar

This is such a simple topic, I'm embarrassed for myself. But I'm doing some review problems before the semester starts, and I've realized that I'm totally blanking on this topic.

Assuming the grammar:

int = int digit | digit
digit = 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19

Write out a left derivation and a right derivation for:

15 14 13 12

I know it should look something like:

int => int digit
=> int digit digit
=> int digit digit digit
=> digit digit digit digit

...but then I'm not sure what to do (or even if that much is right), nor do I get how to do it in the other direction!

So it would be wonderful if someone could explain to me a) how to do this in the future, and b) give the answer so I can check that I understand the process. I really appreciate any and all help!

Upvotes: 1

Views: 2928

Answers (1)

user541686
user541686

Reputation: 210685

The leftmost and rightmost derivation are the same in this case, which is as you showed.

The leftmost derivation expands the leftmost nonterminal first; the rightmost derivation expands the rightmost nonterminal first.

Wikipedia has good examples. For the grammar

S → S + S
S → 1
S → a

This is a leftmost derivation:

S → S + S
  → 1 + S
  → 1 + S + S
  → 1 + 1 + S
  → 1 + 1 + a

This is a rightmost derivation:

S → S + S
  → S + a
  → S + S + a
  → S + 1 + a
  → 1 + 1 + a

Upvotes: 2

Related Questions