newbee help : parser in C

[vaib]

hi all . i am trying to build a parser in ANSI C . I made a lexical
analyser in the same language a while ago . It was a very simple lexer
that tokenised a simple C source code text file - basically a very
simple lexer . I had made use of hash tables for the data structure .
Now i want to know how to build a parser . I'll let you know what i
know about parser building - i'll need a grammar written in the form
of regular expressions , i would need to implement something called a
parse tree in a data structure of my choice and so on . The problem is
that i know stuff here and there but i haven't got a full picture as
to what approach is to be taken to attack the problem ,i.e, i do not
know the steps involved in the learning curve for parser building .
Can anyone out there kindly layout the steps to be taken in proper
order ? i want to have a working parser in the next 15 days since
thats the amount of time after which my college resumes . I have
compiler construction in my next semester so i want to have atleast
the front-end ready before the course starts . I do not want a very
efficient , high-end or hi-tech parser - just a simple one that
demonstrates the concept decently . Any language whose grammar (in the
form of REs) is available would do , its not that i want to stick with
C alone since i made my lexer for that . It would be very appreciative
if anyone who's made a parser before in C could lend me the source
code for studying purposes . Resorces that would not take much time
are welcome - you see , since i have time constraints i'd like to get
to the coding part as soon as possible (and please tell me where to
get that grammar from too) .
Thanking in anticipation . Vaib .

 

[Antoninus Twink]

hi all . i am trying to build a parser in ANSI C .

Check out yacc (aka bison).

 

[rahul]

<snip>
too long to quote.....
<snip>

<off-topic>
Check out yacc(bison). It uses BNF and works very well with
lex(flex). There is a good book from oreilly on flex and bison. They
have implemented SQL parser as an example. That would be helpful for
you. lex/yacc(flex/bison) has been used to implement some popular
compilers. gcc also makes use of them.
</off-topic>

 

[vaib]

     Your question is about the design and implementation of
parsers, not about the C language.  Try asking in a forum whose
topic is compilers, perhaps comp.compilers.

     If you wind up implementing a parser (or anything else) in
C and are have questions about the C itself, feel free to ask
those questions here.

i know that i'm probably in a wrong forum for this particular task but
surely there will be people around here too who could also help me
with this thing .

 

[vaib]

Check out yacc (aka bison).

i know what yacc (aka bison) does but i was avoiding to use tools .
but yes it is a very good idea to look at the code generated by it .
it might be of huge hepl . could you direct me to a grammar that yacc
takes ? thanx .

 

[vaib]

FYI I don't read things that appear is one illegible block, without
any breakup into paragraphs.

yeah sorry for the way i posted this . could you _now_ please read it
once . thanx .

 

[vaib]

<snip>
  too long to quote.....
<snip>

<off-topic>
Check out  yacc(bison). It uses BNF and works very well with
lex(flex). There is a good book from oreilly on flex and bison. They
have implemented SQL parser as an example. That would be helpful for
you. lex/yacc(flex/bison) has been used to implement some popular
compilers. gcc also makes use of them.
</off-topic>

oh yes i've got that book . its called 'lex and yacc' by John Levine .
i'll surely do it . but i needed a simpler grammar .

 

[vaib]

Look up the MiniBasic project on my website.
Once you get the idea, adding features to a recursive descent parser is
quite easy. The next challenge is to compile rather than intepret.

i'll do it rightaway and let you know .

 

[Kenny McCormack]

i know that i'm probably in a wrong forum for this particular task but
surely there will be people around here too who could also help me
with this thing .

Could: Yes. Will: No.

 

[Kenny McCormack]

FYI I don't read things that appear is one illegible block, without
any breakup into paragraphs.

That's OK. Nobody reads anything you post - except to ridicule it.

 

[Nick Keighley]

i know what yacc (aka bison) does but i was avoiding to use tools .
but yes it is a very good idea to look at the code generated by it .
it might be of huge hepl . could you direct me to a grammar that yacc
takes ?

my understanding is that the code produced by bison isn't very
readable.
You arn't meant to read it.

Look up Recursive Descent Parser and try something simpler
than C to start with. Maybe a subset of C.

int i;
float f;

int foo (int x)
{
}

int main(void)
{
foo (i);
return 0;
}

only two simple types and three keywords.

You may know more about parsers than I (not hard)
but specifing the grammar as reg exps sounds odd to me
Why not modified Backus Naar? See the appendix in K&R
for a C grammer.

From the grammar a RDP should follow in quite a
straitforward manner.

Beware C is some tricky corners (eg. typedefs).

 

[Antoninus Twink]

yeah sorry for the way i posted this . could you _now_ please read it
once . thanx .

CBFalconer is a troll, best ignored. Count it a blessing if he doesn't read
your posts.

 

[Bartc]

hi all . i am trying to build a parser in ANSI C . I made a lexical
analyser in the same language a while ago . It was a very simple lexer
that tokenised a simple C source code text file - basically a very
simple lexer . I had made use of hash tables for the data structure .

Now i want to know how to build a parser . I'll let you know what i
know about parser building - i'll need a grammar written in the form
of regular expressions , i would need to implement something called a
parse tree in a data structure of my choice and so on.

I don't know the formal approach to these things but I haven't come across
an RE grammar before, not for an entire language anyway.

The usual approach if you're not using external tools is to program using
'recursive descent' or top-down, whatever the term is. In this case the
grammar is built-in to the code. You will need a tokeniser too, which it
seems you already have.

Then you have all you need and top-down is really easy! But you have to
decide what the output will be, and typically this will be some tree
representation of the syntax.

I don't have any /simple/ examples however (and they're not in C). But if
you post a simple grammar example (which I can understand as I don't know
RE), then maybe I can give a bit more help.

 

[Richard]

FYI I don't read things that appear is one illegible block, without
any breakup into paragraphs.

Who cares? Your opinion is generally worthless anyway you pedantic busy
body.

 

[vaib]

my understanding is that the code produced by bison isn't very
readable.
You arn't meant to read it.

Look up Recursive Descent Parser and try something simpler
than C to start with. Maybe a subset of C.

int i;
float f;

int foo (int x)
{

}

int main(void)
{
    foo (i);
    return 0;

}

only two simple types and three keywords.

You may know more about parsers than I (not hard)
but specifing the grammar as reg exps sounds odd to me
Why not modified Backus Naar? See the appendix in K&R
for a C grammer.

From the grammar a RDP should follow in quite a
straitforward manner.

Beware C is some tricky corners (eg. typedefs).

yes Nick i got your point - do simpler things first and then move onto
more complex issues . i was now thinking of using yacc first and i'm
reading 'lex and yacc' for that purpose . yes now i know that i'll
write a simple grammar in Backus Naur from and then make a recursive
descent parser for the same . but can u tell me how to do it
exactly ?? and no , i dont know about parsers more than you ( or
anybody else for that matter - i'm just a beginner ) . thanks a lot .

 

[vaib]

I don't know the formal approach to these things but I haven't come across
an RE grammar before, not for an entire language anyway.

The usual approach if you're not using external tools is to program using
'recursive descent' or top-down, whatever the term is. In this case the
grammar is built-in to the code. You will need a tokeniser too, which it
seems you already have.

Then you have all you need and top-down is really easy! But you have to
decide what the output will be, and typically this will be some tree
representation of the syntax.

I don't have any /simple/ examples however (and they're not in C). But if
you post a simple grammar example (which I can understand as I don't know
RE), then maybe I can give a bit more help.

all right . thank you so much . i really find people here who help me
all the time .

 

[vaib]

[... about implementing parsers ...]

i know that i'm probably in a wrong forum for this particular task but
surely there will be people around here too who could also help me
with this thing .

     Yes, there are people here who know a bit about the topic.
In a small way, I'm one of them.  But it's not the focus here,
which means that the concentration of experts on your question
is no greater here than on any other computer-related forum.
No matter where you ask, you'll get answers both good and bad --
but if you ask where the experts hang out, bad answers will be
quickly corrected.  Here, corrections are less likely and you
run a greater risk of getting bad information.  Since you wrote
earlier that you have only fifteen days to work with, a bad
answer that sent you down a blind alley would be a serious
setback.

     You've been pointed to a forum where you're likely to get
better answers; I think that's the best help this group can
offer.

Tnank you Eric i got your point . i've also posted in related forums .
Dont worry i generally know how to separate good answers from the bad
ones .

 

[vaib]

Who cares? Your opinion is generally worthless anyway you pedantic busy
body.

By the way , why are people so upset with CBFalconer ?

 

[Nick Keighley]

Look up Recursive Descent Parser and try something simpler
than C to start with. Maybe a subset of C.

You may know more about parsers than I (not hard)
but specifing the grammar as reg exps sounds odd to me
Why not modified Backus Naar? See the appendix in K&R
for a C grammer.

From the grammar a RDP should follow in quite a
straitforward manner.

Beware C [has] some tricky corners (eg. typedefs).

yes Nick i got your point - do simpler things first and then move onto
more complex issues . i was now thinking of using yacc first and i'm
reading 'lex and yacc' for that purpose . yes now i know that i'll
write a simple grammar in Backus Naur from and then make a recursive
descent parser for the same . but can u tell me how to do it
exactly ?? and no , i dont know about parsers more than you ( or
anybody else for that matter - i'm just a beginner )

first hit:
http://en.wikipedia.org/wiki/Recursive_descent_parser

it has code as well

 

[vaib]

... snip ...


I suggest you look at the source for the portable Pascal compiler,
available on the ISO Pascal pages.  You can find out about that on
comp.lang.pascal.ansi-iso newsgroup.  It uses recursive descent.

Similar techniques will teach you much more than just using lex and
yacc.  The first step is a useful lexer, that separates out
reserved words, identifiers, numerics, char symbols, etc.  There is
no need for hash tables here.  When you get to things that develop
symbol tables etc. that is another matter, and I recommend looking
at my hashlib, available at:

   <http://cbfalconer.home.att.net/download/hashlib.zip>

thank you for replying . right now i am reading 'lex and yacc' . i
plan to use yacc for generating a parser and then read its code ( ie ,
the generated parser's code ) and then continue my parser construction
study from the 'dragon book' . then i hope to have a clear picture in
my mind as to what 'exactly' has to be done in parser coding . am i
right in my approach ?? i generally avoid reading the code of the
already stable compilers sice it takes a lot of time for me to do that
and to figure out the complete code (...even of the front-end ) . do
you think my approach is right or is there a speedier way to it ?
thank you again for replying .