Grammar Parse tree?

Question

This question is on my CS homework and I have no idea how to do it.

Consider the grammar

S ← ( L ) 
S ← a
L ← L , S 
L ← S 

Draw a parse tree for the sentence ( a , ( a , a ) )

I tried following the structure and I end up with (L,(L,L)) That doesn't seem to be correct though. Could anyone push me in the right direction?

Answer 1

Here's part of what you're after:

Now you get to do the rest of the work :)

Answer 2

Look at the sentence (a, (a, a)). Which of the right-hand sides (RHS's) can it possibly match? Only the first, S ← ( L ). So the root of your tree will be an S-node with three children: a (-node, an L-node, and a )-node.

Now you need to figure out what the children of the L-node are, and they have to match the remaining input: a,(a,a). So look at the rules that have L on the LHS. Of those rules, which one has an RHS that can match a,(a,a)?

Answer 3

The parse tree for (a,(a,a)) is obtainable from a leftmost derivation of (a,(a,a)):

S => (L)        [S -> (L)]
  => (L,S)      [L -> L,S]
  => (S,S)      [L -> S  ]
  => (a,S)      [S -> a  ]
  => (a,(L))    [S -> (L)]
  => (a,(L,S))  [L -> L,S]
  => (a,(S,S))  [L -> S  ]
  => (a,(a,S))  [S -> a  ]
  => (a,(a,a))  [S -> a  ]

The root of your parse tree is S. For each rewrite of a nonterminal symbol in the derivation, draw the appropriate node in the parse tree. Also, your grammar isn't optimal and among other things, contains chain rules. Removing them would prevent having to derive S from L in order to derive a.