4
$\begingroup$

I am trying to learn how to build parse trees.

I have watched videos and tried to do some on my own, but am a little lost.

In this example, I am given the following:

$$ \begin{align*} &S\to(L) \\ &S\to a \\ &L\to L,S \\ &L\to S \end{align*} $$

and then I am told to draw a parse tree for the expression $(a,(a,a))$.

I know that the first $S$ is the start symbol, I know that since I am trying to draw it for a specific string, I should use the bottom up approach, but I am very confused.

Can the lines above also be written as $$ \begin{align*} &S\to(L)|a \\ &L\to L,S|S \end{align*} $$ or can they not be combined that way?

How would you write this tree? What confuses me the most is how to write the tree using the $L$ and $L,S$ but resulting in $(a,(a,a))$.

I would appreciate any explanation or demonstration offered.

$\endgroup$
  • 1
    $\begingroup$ You're right that, in general, a grammar can let you draw a parse tree of an expression in several different ways. $\endgroup$ – Guildenstern May 7 '14 at 15:21
5
$\begingroup$

The notation $S\to(L)|a$ is shorthand to $S\to(L)$ and $S\to a$, so you can rewrite the grammar in your equivalent form; I don't see how this makes things any different, since the two grammars are exactly the same.

The first step in writing a parse tree is coming up with a derivation. In the derivation below, I use boldface to indicate the non-terminal being expanded. $$ \begin{align*} \mathbf{S}&\to(\mathbf{L}) \\ &\to(\mathbf{L},S) \\ &\to (\mathbf{S},S) \\ &\to (a,\mathbf{S}) \\ &\to (a,(\mathbf{L})) \\ &\to (a,(\mathbf{L},S)) \\ &\to (a,(\mathbf{S},S)) \\ &\to (a,(a,\mathbf{S})) \\ &\to (a,(a,a)) \end{align*} $$ There are several different derivations which "feel" the same. For example, in this derivation I always expanded the left-most non-terminal, but you could just as well expand any other non-terminal. When you draw the derivation tree, all these derivations give rise to the same tree.

Here is the actual derivation tree, drawn by Rick Decker: enter image description here

$\endgroup$
  • $\begingroup$ Here's an image (made in Tikz, no less). Do with it what you want. $\endgroup$ – Rick Decker May 8 '14 at 0:42

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.