A few questions about parsing

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]

Return to the comp.compilers page.
Search the comp.compilers archives again.