Solved

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

Posted on 2008-10-20
8
2,876 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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
This article is meant to give a basic understanding of how to use R Sweave as a way to merge LaTeX and R code seamlessly into one presentable document.
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

758 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

20 Experts available now in Live!

Get 1:1 Help Now