0
$\begingroup$

I'm starting an online Computer Science class called Advanced Programming Languages, and the book asks me to create a parse tree and generate a grammar from it. Here are the exact instructions:

To verify that a string of characters belongs to a language defined by a grammar, we must create a parse tree that shows that the string can be generated by the grammar.

<list> -> <item> , <list> | <item> 
<item> -> <left> <item> <right> | <left> <right>
<left> -> A| B | C 
<right> -> x | y | z

Choose a string that is in this language and create a parse tree that demonstrates that your claim is true. Identify another string that contains some of these terminals symbols but is not in the language.

I think I know how to get started, but I keep getting confused by examples in the book and examples online. Is there a general method to use when approaching this?

I began it this way:

            <list>
         /          \    
      <item>      <list>
    /    |    \
<left> <item> <right>
  |    /
  A  <left>

But I get confused on the next iterations of the item. Any hints?

$\endgroup$
  • $\begingroup$ 1. OK, good, that makes a significant difference. Now the question makes sense. 2. What does "next iterations of the item mean? 3. You're trying to show us an example parse tree, but what string is that supposed to correspond to? It sounds like you're trying to start with a parse tree, expand it out, and then find a corresponding string. If you're stuck with that, you might also want to try the reverse: pick a string that you know is in the grammar, and then try constructing a parse tree for it (run a standard parsing algorithm by hand, if need be). $\endgroup$ – D.W. Jan 11 '16 at 17:25
  • $\begingroup$ @D.W. 1. Thanks! 2. (Please excuse my lack of understanding as this is new to me.) I actually meant list, and I basically just assumed since it also appears in the production of <list> that it is a recursive call. 3. You're correct, that is what I was trying to do. How can I pick a string that is in the grammar? $\endgroup$ – hax0r_n_code Jan 11 '16 at 17:30
  • $\begingroup$ It's the standard way of doing a derivation with a context-free grammar. Start with the start symbol (non-terminal), and apply productions until you get to a string that contains only terminals. Any good textbook should have some explanation of productions or examples of grammars and production rules. $\endgroup$ – D.W. Jan 11 '16 at 17:31
  • $\begingroup$ @D.W. is A x a string in the grammar? $\endgroup$ – hax0r_n_code Jan 11 '16 at 17:32
  • 1
    $\begingroup$ It sounds like you really need more interactive assistance. Unfortunately, this site is not well-suited for that. I recommend that you find a tutor, teacher, or friend who knows this material and ask them. This site is not a discussion forum and isn't intended for back-and-forths or interactive discussions. $\endgroup$ – D.W. Jan 11 '16 at 18:56
3
$\begingroup$

Before expanding a grammar into a parse tree, we should first try to understand it at a higher level.

<list> -> <item> , <list> | <item> 
<item> -> <left> <item> <right> | <left> <right>
<left> -> A| B | C 
<right> -> x | y | z

First, <list> is a list of <item>, separated by commas if there are multiple ones.

Second, an item is either a pair of alphabets (the left is one of A | B | C; the right is one of x | y | z) or recursively, an item surrounded by such a pair.
Thus, an <item> is a word composed of, say $n$, upper-case alphabets from A | B | C, followed by the same number, $n$, of lower-case alphabets from x | y | z.

$Q_1$: Choose a string that is in this language and create a parse tree that demonstrates that your claim is true.

ABCxyz,ACyz is in this language; can you generate a parse tree for it?

$Q_2$: Identify another string that contains some of these terminals symbols but is not in the language.

AyCz is not in this language; can you explain why?


In addition, when you are searching for any string in a grammar by expanding the grammar into a parse tree, you can push the tree into its leaves as fast as you can, by choosing the non-recursive rules whenever possible.

$\endgroup$
  • $\begingroup$ Thanks so much for your explanation! I can generate the parse tree for the string you have. It helped a lot when I drew out the parse tree and could visually see how the strings were being formed. I generated the string ABxy,CAzx from this grammar, which basically doesn't expand <item> as far down as your string. One more layer of expansion for <item> and I can generate your string. $\endgroup$ – hax0r_n_code Jan 12 '16 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.