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
This Question has been solved and asker verified All Experts Exchange premium technology solutions are available to subscription members.
Experts Exchange has been collecting answers to technology questions since 1996…3 million and counting! If you have a question, chances are we already have your answer.
If you can't find the exact answer you're looking for, ask our exclusive community of 50,000 experts. You’ll get a personalized answer from a trusted professional.
Thousands of free tech tips, tricks, how-to’s and tutorials are available in our peer reviewed articles section. See for yourself how smart our experts are, no login required.
Save solutions to your questions, answers you’ve discovered through searching plus helpful articles in your personal knowledgebase for easy future access.
Access the answers to your technology questions today.
30-day free trial. Register in 60 seconds.
Members of the expert community talk about why the experience at Experts Exchange is different than what you will find anywhere else.
Try it out and discover for yourself.
30-day free trial. Register in 60 seconds.
Join the community of experts here and help other tech pros by answering question in your area of expertise. You can earn FREE access to all Experts Exchange's premium features and resources.
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?
> 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 ;) )
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.
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 ;)
Business Accounts
Answer for Membership
by: zmoPosted on 2008-10-20 at 10:09:04ID: 22759906
hm... first, did you have a look at wikipedia's article on :
http://en.wikipedia.org/wi
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.