Solved

How do I get the Phrase, Simple phrase and handle for the following:

Posted on 2008-10-20
8
2,893 Views
Last Modified: 2013-11-18
Hi Experts,

     I am taking a class in Programming Languages and I'm reading from my textbook (sebesta) but do not understand how they are coming up with the phrase, simple phrase and handle.

I know the handle is the RHS. A phrase can be derived from a single nonterminal in one or more tree levels, and a simple phrase can be derived in just a single tree level. But when I look at the following problem I don't understand how they break out the phrase, simple phrase and handle. The examples in the book are not clear to me.

Given the following grammer and the right sentential form, draw a parse tree and show the phrases and simple phrases as well as the handle:

S - AbB | bAc
A - Ab | aBB
B - Ac | cBb | c

a. aAcccbbc
b. AbcaBccb
c. baBcBbbc

Thanks, MissyMadi
0
Comment
Question by:missymadi
  • 4
  • 4
8 Comments
 
LVL 5

Expert Comment

by:zmo
ID: 22759906
hm... first, did you have a look at wikipedia's article on :
http://en.wikipedia.org/wiki/Bottom-up_parsing ?

I think to help you the best is not to give you the result of your exercise, or your exam's day, you'll be doomed. (note to other experts, don't give it straight to him).

can you give us how you begin the parse tree construction, and at what point you don't get it, so we might just give you a little hint on how to get to the next step... and not doing it for you. Usually, you should get some kind of "stupid" algorithm to apply on the grammar to get the tree in your course's documentation.
0
 

Author Comment

by:missymadi
ID: 22761127
I understand the part where, in the book, it describes a bottom up parser like this
S= aAc=aaAc=aabc
The example only has one RHS
S-aAc
A-aA|b
So when you replace b with aabc, A gets the second last sententail form in the derivation aaAc.

For my problem,
S - AbB | bAc
A - Ab | aBB
B - Ac | cBb | c

a. aAcccbbc
b. AbcaBccb
c. baBcBbbc
I'm not sure where to go from here? Do I replace |c with aAcccbbc??  What do you do in the case of many RHS?
0
 
LVL 5

Accepted Solution

by:
zmo earned 250 total points
ID: 22765441
> I'm not sure where to go from here?

well, you have 'aAcccbbc', and you have to iterate with the grammar on it so you get 'S'. ;)
imagine that you are the yacc parser, what can you do, and would you do, then ?

> Do I replace |c with aAcccbbc??

no you don't, that's the contrary...

you have :

aAcccbbc on your input.
you can shift one terminal or reduce your stack to a non-terminal.

ie : first step would be :

aAcccbbc -> aAcccbb {c} (shift)

and what would be the second step :

-> aAcccb {bc} (shift)
or
-> aAcccbb {B} (reduce) ?

to answer that question, you have to figure out how many token in advance can you read before doing a reduction.


(PS: I'm a CS student still learning this at uni, so I may always be wrong in what I'm saying, so if any expert reading this does not agree, please drop a comment and let us know ;) )
0
 

Author Comment

by:missymadi
ID: 22767835
S - AbB | bAc
A - Ab | aBB
B - Ac | cBb | c

a. aAcccbbc
b. AbcaBccb
c. baBcBbbc
So for aAcccbbc, I would look at B - Ac | cBb | c and |c being the RHS I could shift over to b leaving aAcccbb. Now cBb is not RHS so am I looking at A-Ab|aBB and reducing aAcccbb to aAcccbB replacing terminals with non-terminal?

Is there a parsing for dummies book?? I am currently using my text book Sebesta "Concepts of Programming Languages" and the examples are not very good. I have an exam coming up in two weeks and want to have this figured out. If I had some examples I would get a better understanding.
0
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 
LVL 5

Expert Comment

by:zmo
ID: 22772124
hm... I'm gonna take a book to answer this tomorrow when I'll be at work (I made them buy a very good one, which is called the dragon book, "Compilers, Principles and tools" from Aho, also called the Aho book. I really encourage you to take it at your university's library..)

I even wonder if your example grammar is not ambiguous, though I'm sure they did choose carefully their examples in your book... (didn't they ? :P).

And I also have interests to help you, as I'm having an exam in 10 days ;)

0
 

Author Comment

by:missymadi
ID: 22776383
Great! Thanks for you help. I just looked at Amazon, and they have the book. I'm going to order it.
 I'm still curious about this problem. Please let me know what solution you come up with!

Good Luck on your exam!
MissyMadi
0
 
LVL 5

Expert Comment

by:zmo
ID: 22784267
oops, I forgot to do that yesterday... too busy on my work :-S

anyway, we'll keep on this topic, maybe with more examples ;)
what have you to learn for your exam ? only grammars ?
we are now working a lot on the 'w' algorithm (for typing)
0
 

Author Comment

by:missymadi
ID: 22834112
Sorry for the delay. Busy at work

We'll need to know derivation tree, context free grammar, right most derivation, left most derivation, three demensional arrays and show as they would be stored.

Thanks, Pam
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
withoutString  challenge 40 182
viewing source code from eclipse 13 88
no14 challenge 14 62
Python multiple IF statements 4 76
Windows Script Host (WSH) has been part of Windows since Windows NT4. Windows Script Host provides architecture for building dynamic scripts that consist of a core object model, scripting hosts, and scripting engines. The key components of Window…
When we want to run, execute or repeat a statement multiple times, a loop is necessary. This article covers the two types of loops in Python: the while loop and the for loop.
The goal of this video is to provide viewers with basic examples to understand and use conditional statements in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.

895 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now