newbee help : parser in C

Discussion in 'C Programming' started by vaib, Jun 19, 2008.

  1. vaib

    vaib Guest

    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 .
    vaib, Jun 19, 2008
    1. Advertisements

  2. Check out yacc (aka bison).
    Antoninus Twink, Jun 19, 2008
    1. Advertisements

  3. vaib

    rahul Guest

    too long to quote.....

    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.
    rahul, Jun 20, 2008
  4. vaib

    vaib Guest

    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, Jun 20, 2008
  5. vaib

    vaib Guest

    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, Jun 20, 2008
  6. vaib

    vaib Guest

    yeah sorry for the way i posted this . could you _now_ please read it
    once . thanx .
    vaib, Jun 20, 2008
  7. vaib

    vaib Guest

    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, Jun 20, 2008
  8. vaib

    vaib Guest

    i'll do it rightaway and let you know .
    vaib, Jun 20, 2008
  9. Could: Yes. Will: No.
    Kenny McCormack, Jun 20, 2008
  10. That's OK. Nobody reads anything you post - except to ridicule it.
    Kenny McCormack, Jun 20, 2008
  11. my understanding is that the code produced by bison isn't very
    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).
    Nick Keighley, Jun 20, 2008
  12. CBFalconer is a troll, best ignored. Count it a blessing if he doesn't read
    your posts.
    Antoninus Twink, Jun 20, 2008
  13. vaib

    Bartc Guest

    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.
    Bartc, Jun 20, 2008
  14. vaib

    Richard Guest

    Who cares? Your opinion is generally worthless anyway you pedantic busy
    Richard, Jun 20, 2008
  15. vaib

    vaib Guest

    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, Jun 25, 2008
  16. vaib

    vaib Guest

    all right . thank you so much . i really find people here who help me
    all the time .
    vaib, Jun 25, 2008
  17. vaib

    vaib Guest

    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, Jun 25, 2008
  18. vaib

    vaib Guest

    By the way , why are people so upset with CBFalconer ?
    vaib, Jun 25, 2008
  19. first hit:

    it has code as well
    Nick Keighley, Jun 26, 2008
  20. vaib

    vaib Guest

    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 .
    vaib, Jun 26, 2008
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.