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.

 

[rezeew]

I would first clarify with the person who provided the content what the starting symbol should be and what the commas represent. Once that is determined, I would use my knowledge of grammar and parsing to construct a parse tree for the given expression. If there is confusion about the parentheses, I would ask for clarification on whether they are necessary for the expression to be valid or if they are just included for clarity. In any case, the parse tree would be constructed based on the given grammar rules and the symbols used in the expression.