 |
|
| Computers Forum Index » Computer Compilers » A few questions about parsing... |
|
Page 1 of 1 |
|
| Author |
Message |
| Chariton Karamitas... |
 Posted: Mon Aug 31, 2009 4:01 pm |
|
|
|
Guest
|
Hello everyone,
I am an undergraduate student at the Electrical Engineering Department
of the Aristotle University of Thessaloniki (Greece) and I'm very
interested, yet a newbie, in compilers. I would like to ask a few
questions for which I was unable to find an answer via google. I
apologize in advance for all those newbie-ish questions that will
follow :-)
I am currently working on a project that requires basic compiler
infrastructure (parse trees, intermediate forms etc). For personal
purposes I've coded a library, called libbnf (soon to be released),
that parses a BNF grammar given in a text file and creates a
graph-like datastructure out of it. What I am planning to do next, is
to create a parser that will receive the BNF grammar from libbnf and
parse the input based on this grammar. I have a couple of questions
though...
1. I've been able to parse the C BNF syntax given in K&R 2nd edition
in Appendix A via libbnf. I've noticed that it contains both left and
right recursions. Isn't this a problem for parsers?
2. What parser can parse this grammar? An LR? LALR? LL? What's the
best choice? I've read that left-recursive grammars are ok for LR and
right-recursive for LL, but the K&R C grammar contains both kinds of
recursions! :-)
3. The wikipedia page at http://en.wikipedia.org/wiki/Left_recursion
describes the so called "indirect left recursion" (we end up in
non-terminal <A> after a bunch of transitions starting from <A>). How
is this problem resolved in a real life parser? What is the situation
if an "indirect right recursion" is found? Is it the same? Modifying
the grammar in order not to have recursions is the only solution?
Probably more newbish questions will follow any answer to this mail!
This is a warning to all those that are brave enough to answer :-)
Thanx in advance!
../ck
[You can parse C with a LALR parser, give or take some ugliness about
typedef names. Back when everything had to fit into 64K, it was
important to keep the parse stack small so you avoided right recursion
whenever possible. These days it's not a big deal unless your production
is liable to recurse thousands of times. -John] |
|
|
| Back to top |
|
|
|
| Hans Aberg... |
| Posted: Mon Aug 31, 2009 11:38 pm |
|
|
|
Guest
|
|
| Back to top |
|
|
|
| Ira Baxter... |
| Posted: Wed Sep 02, 2009 11:32 pm |
|
|
|
Guest
|
"Hans Aberg" <haberg_20080406 at (no spam) math.su.se> wrote in message
Unless you're a glutton for punishment, you really don't want to go
down "roll your own (or even patch up Willink's) C++ parser route".
As an undergrad, the OP will be very well served to stick with trying
to parse C, learning about disambiguating syntax forms using type
information, and building symbol tables for that with the agreement
that C++ is just worse. Reading Willink's thesis is probably a good
way to get a faint sense of how much worse.
To go anywhere with C++, you not only need to parse, but you have to get
the symbol table and name/type resolution right, and that's about 400 pages
of reference manual worse.
If he wants to study a working version of a C++ front end, the EDG one is
available for academics, and so is Elsa.
-- IDB |
|
|
| Back to top |
|
|
|
|
|
All times are GMT
The time now is Sat Nov 28, 2009 1:16 am
|
|