CODEWITHSUNDEEP
parsingtreegrammarparse-tree
Jonathan
Jonathan

Reputation: 1981

Grammar Parse tree?

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?

Upvotes: 2

Views: 2313

Answers (3)

emi
emi

Reputation: 5410

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.

Upvotes: 0

Stuart Golodetz
Stuart Golodetz

Reputation: 20656

Here's part of what you're after:

enter image description here

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

Upvotes: 4

rob mayoff
rob mayoff

Reputation: 385998

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)?

Upvotes: 2

Related Questions