• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3586
  • Last Modified:

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

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
missymadi
Asked:
missymadi
  • 4
  • 4
1 Solution
 
zmoCommented:
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
 
missymadiAuthor Commented:
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
 
zmoCommented:
> 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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
missymadiAuthor Commented:
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
 
zmoCommented:
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
 
missymadiAuthor Commented:
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
 
zmoCommented:
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
 
missymadiAuthor Commented:
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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

  • 4
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now