1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Parse tree

  1. May 5, 2014 #1
    1. The problem statement, all variables and given/known data

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

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


    3. The attempt at a solution
    I cant 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?
     
  2. jcsd
  3. May 5, 2014 #2
    attachment.php?attachmentid=69448&d=1399323730.jpg This is my attempt at drawing it so far. I dont know how the arrows connecting them should be drawn though.
     

    Attached Files:

  4. May 5, 2014 #3

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    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.

    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.
     
  5. May 5, 2014 #4
    thank you! I think I will draw an arrow connecting each substitution.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Parse tree
  1. Binary trees (Replies: 1)

  2. Recursion Tree (Replies: 3)

  3. Binary Search tree (Replies: 5)

Loading...