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
    1. Advertisements

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

  3. vaib

    rahul Guest

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

    vaib Guest

    yeah sorry for the way i posted this . could you _now_ please read it
    once . thanx .
     
    vaib, Jun 20, 2008
    #6
  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
    #7
  8. vaib

    vaib Guest

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

    Richard Guest

    Who cares? Your opinion is generally worthless anyway you pedantic busy
    body.
     
    Richard, Jun 20, 2008
    #14
  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
    #15
  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
    #16
  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
    #17
  18. vaib

    vaib Guest

    By the way , why are people so upset with CBFalconer ?
     
    vaib, Jun 25, 2008
    #18
  19. first hit:
    http://en.wikipedia.org/wiki/Recursive_descent_parser

    it has code as well
     
    Nick Keighley, Jun 26, 2008
    #19
  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
    #20
    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.