parser error recovery

This is a discussion on parser error recovery within the C Programming forums, part of the General Programming Boards category; I'm writing an LL parser for a C like language and I've run into a bit of confusion on the ...

  1. #1
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357

    parser error recovery

    I'm writing an LL parser for a C like language and I've run into a bit of confusion on the logic of implementing an error recovery scheme. I will be using panic mode, just skip tokens until I find one of Follow(A) or EOF, but I'm not sure if I need to crawl out of my deep stack of function calls, or since I am finding a Follow in the rule I'm currently parsing if I even need to get out. (sorry for the poorly phrased sentence)

    Thanks.

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,045
    but I'm not sure if I need to crawl out of my deep stack of function calls
    It's not that difficult to do this.

    We'll probably need to see your code to help you some more.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    It may be easier if I just give you a chunk of my grammar, the code is somewhat long.
    Just say if you still need some of the code. (E is empty in the below grammar)
    Code:
    expression = id '=' expression | condition
    condition = and ('||' and)*
    and = equal ('&&' equal)*
    equal = relation ('==' relation | E)
    relation = sum (('>' | '<') sum | E)
    sum = term (('+' | '-') term)*
    term = unary (('*' | '/' | '%') unary)*
    unary = atom | ('!' | '-') unary
    atom = int | float | id | '(' expression ')'
    So if I'm parsing:
    q = i+j*+k
    I see the * and call unary, I get down to atom and see I have none of int, float, id, '(' so I error, but then do I just eat tokens till I get one of Follow(atom) and the problem is solved?

  4. #4
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,045
    You could do that, but I would unwind the stack and prompt for another expression.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  5. #5
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    It's not just a simple prompt, it's a small C like language compiler that takes a file to compile as an argument so unfortunately I can't just return the first error I find, I have to try to recover and find more errors.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,045
    Oh, I see. In that case I would keep going.
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    I started the code and it's failing, I imagine it's due to my incorrect understanding and/or logic.

    Given something like this:
    Code:
    program = var_type id(var_type id)
    var_type = int | float | char
    and an input file like this
    Code:
    main(float x)
    The rule program will fail because it first expects to see a var_type but instead sees an id. id is in follow var_type so do I eat no tokens? Or do I eat the erroneous token before I start looking for a new token in Follow?

    Thanks again.

  8. #8
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,600
    recovering is a 'nice' feature but hardly required. the overhead and logic might even introduce bugs in the parser if implemented incorrectly. one way is to join the rules (using binary OR) with an 'expected' rule that sets the parser in the correct state (by eating tokens or whatever) to continue parsing as you build up error messages. something along the lines of:

    some_rule = (var_type | expected(var_type)) (id | expected(id)) /* etc */

    whether that method would work for you or not depends on how the parser is implemented. at any rate it's a pretty top-heavy approach! there are probably better ways of course, you might browse the code to an existing compiler or try google on other approaches to your problem.
    Code:
    if( numeric_limits< byte >::digits != bits_per_byte )
        error( "program requires bits_per_byte-bit bytes" );
    24bbs.cpp

  9. #9
    Dump Truck Internet valis's Avatar
    Join Date
    Jul 2005
    Posts
    357
    Since it's a project for school I sadly am forced to implement it.
    The project specifications only states we use the Follow sets as 'anchor' tokens, however, this works terribly so I added the First sets as well which improved it a bit. I'll go ahead and try to implement what you have suggested as well.

    Thank you very much for your input.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Working with Parser Generators - Functions
    By jason_m in forum C Programming
    Replies: 1
    Last Post: 09-09-2008, 09:38 PM
  2. doubt in c parser coding
    By akshara.sinha in forum C Programming
    Replies: 4
    Last Post: 12-23-2007, 12:49 PM
  3. Parser Help
    By Barnzey in forum C++ Programming
    Replies: 10
    Last Post: 10-26-2005, 12:10 PM
  4. Problem with a file parser.
    By Hulag in forum C++ Programming
    Replies: 7
    Last Post: 03-17-2005, 08:54 AM
  5. Parser - need help!
    By thelma in forum C Programming
    Replies: 2
    Last Post: 04-05-2004, 08:06 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21