Languages - Leftmost Derivations

tntcoder · 17 Jan 2009 at 21:22

Hi,

I have an exam coming up soon, and im having problems understanding how to do left/rightmost derivations from my notes for some slightly complex grammars.

I can do it fine for simple grammars and strings e.g

Grammer:
S -> aAs | a
A -> AbA | SS | ba

and so i can derive: "S -> aAs" so there are no more non-terminals. This exam question is slighly more complex though.

Please could someone point me in the right direction for doing a leftmost derivation of that?

Thanks for any help

gumbald · 17 Jan 2009 at 22:56

Replace the leftmost non-terminal first...

tntcoder · 17 Jan 2009 at 23:09

gumbald said:
Replace the leftmost non-terminal first...

I guessed that much... its replacing what with what which is confusing me.

So IF is the first leftmost non-terminal in the string, im not sure what i replace that with because in the examples ive seen if i want to replace X then theres a grammar rule X -> Y | Z... in this example there is nothing for IF -> X and hence I really have no idea what im doing :confused:

gumbald · 17 Jan 2009 at 23:48

You should end up with a list of numbers describing how the grammar creates the program.

http://en.wikipedia.org/wiki/Leftmost_derivation#Derivations_and_syntax_trees