Solved

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

Posted on 2008-10-20
8
2,939 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
Netscaler Common Configuration How To guides

If you use NetScaler you will want to see these guides. The NetScaler How To Guides show administrators how to get NetScaler up and configured by providing instructions for common scenarios and some not so common ones.

 

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
 
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

Ransomware: The New Cyber Threat & How to Stop It

This infographic explains ransomware, type of malware that blocks access to your files or your systems and holds them hostage until a ransom is paid. It also examines the different types of ransomware and explains what you can do to thwart this sinister online threat.  

Question has a verified solution.

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

How to remove superseded packages in windows w60 or w61 installation media (.wim) or online system to prevent unnecessary space. w60 means Windows Vista or Windows Server 2008. w61 means Windows 7 or Windows Server 2008 R2. There are various …
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 the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.

831 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