CODEWITHSUNDEEP
compiler-constructionabstract-syntax-treecontext-free-grammarparse-tree
zed unseened
zed unseened

Reputation: 7

How are these parse tree generated?

I need assistance regarding generating the parse tree and the syntax tree. My version of the solutions are the images below but I don't know if they are correct or way off.

Given the Grammar: S-->aSb | e

And the String: enter image description here

Generate the: (i) Parse Tree, and (ii) Syntax Tree

My Solutions: i)enter image description here

II)enter image description here

Upvotes: -2

Views: 791

Answers (1)

rici
rici

Reputation: 241911

A parse tree (or a syntax tree) needs to correspond to the grammar. The easiest way to construct one is directly from the grammar, since this is exactly what your parser will do. Get out a nice big sheet of paper, and start writing out the derivation.

In this case, you can work forwards because it should be obvious how the derivation proceeds. At every step in the following derivation, try to figure out how I knew which alternative to select. (It's not rocket science.)

Remember that a grammar is simply a game with symbols. A production like S → a S b means (exactly) "replace some S with a S b. S → p q r | x y z is just a short way of writing two productions: S → p q r and S → x y z. The ε symbol means "nothing"; it's just there so that you can see it, since "nothing" is invisible. So S → ε means that you can replace an S with nothing (that is, just delete it).

At each step, you choose one of the rules which applies. Whichever one you think is appropriate. You can stop when there are no rules which apply. That's your goal: to stop exactly at the point when the derivation has produced the string you are parsing.

So it goes like this:

String so far rule result
S S → a S b a S b
a S b S → a S b a a S b b
a a S b b S → a S b a a a S b b b
a a a S b b b S → ε a a a b b b

Now, to make that into a tree, start with the root symbol at the root of the tree, and then write the replacement of a symbol as its children: (non-substitute symbols -- the terminals -- don't have children. They're leaves.)

            S
            |
____________|____________
|           |           |
a           S           b
      ______|______
      |     |     |
      a     S     b      
            |
            …

Upvotes: 3

Related Questions