How Do You Construct a Parse Tree for the Expression (a, (a, a))?

[toothpaste666]

Homework Statement

Consider the grammar
S←(L)
S←a
L←L,S
L←S

draw a parse tree for the expression (a, (a, a))

The Attempt at a Solution

I can't tell if the starting symbol should be S or L. Also what do the commas mean? The examples we did in class had plus and minus signs and stuff like that but we didn't have an example of what to do when there is a comma. Also is there a difference if the parenthesis weren't there around the L in the first one?

 

[toothpaste666]

This is my attempt at drawing it so far. I don't know how the arrows connecting them should be drawn though.

 

[AlephZero]

There is nothing special about the parentheses and commas. They are just symbols. The question would be exactly the same if the grammar was
S←xLy
S←a
L←LzS
L←S
and the string was xazxazayy.

Also is there a difference if the parenthesis weren't there around the L in the first one?

Since there is nothing special about the parentheses, the answer is clearly "yes". Without the parentheses, the grammar would have two rules
S←L
L←S
so the parse tree would be ambiguous, and could be infinitely big.

Your attempt looks OK. Check your course notes or textbook for how you are expected to draw the tree including arrows.

 

[toothpaste666]

thank you! I think I will draw an arrow connecting each substitution.