Am implenting backtracking for the parser-generator

I have just started implementing backtracking for the parser and would like oppinions on how to go ahead with this. I have just reached a state where the first simple grammar compiles parses stuff. The idea: The parser generator only looks one token forwards (lalr(1)). This is sometimes a bit annoying. Instead of implementing a more general parser, the idea of backtracking is, that if you need to look more than 1 token ahead, you simply make a clever guess, and if the guess was wrong you backtrack to the point, and try something else. Notice, that you only backtrack if your guess leads to a compiler error, so backtracking is NO MEANS of disambiguing a grammar. It is a way of implementing LALR(n), where n>1. Backtracking (in my implementation, at least) works in the following way: Rules can be marked as "backtrackable". When the parser generator meets a conflict, and one of the involved rules is backtrackable, that rule is used, and is associated with a pointer to the other rule. When the generated parser reduces a production that has a backtrack-production associated, it pushes a "backtracking mark" onto a special "backtracking stack", and every symbol processed from now on is recorded on that backtracking mark. If the parser meets an error, instead of reporting the error, if the backtracking stack is nonempty, it pops the top mark from the backtracking stack and reverts the state to the state when the mark was pushed onto the stack. Instead of redoing the same production that lead to the mark being pushed onto the stack, it does the associated backtrack-production, and then it reprocesses all the symbols that was processed between the mark and the error. (These might lead to new elements being pushed onto the backtrack stack). To avoid the possibility of a small error leading to a backtrack right back to the start of the program, productions can also be marked as "Stopping backtracks". These stops are safe points, meaning, that if the parser manages to reduce this production then everything up to this point is ok, and THE BACKTRACK STACK IS CLEARED. This is basically it. Because great care has been taken on keeping the parser fast, and backtracking ruins all this by going back and repeating stuff, backtracking should be kept at a minimum. To reflect this, I have the following idea of how the syntax for backtracking should be: Today definition of all rules is terminated by a full stop (.). My suggestion: A full stop means: Stop all backtracking (clear backtrack stack). Don't allow new backtrack on this production. This way the default is not to allow backtracking. If you want to allow old backtracking history to keep on going, but won't allow this rule to start a new backtracking point, this is marked by replacing the full stop with a comma (,). To allow old backtrackings to continue, and also add a new backtrack point for this rule, the rule is terminated by semicolon (;). Finally, to stop old backtrackings, but at the same time inserting a new backtrack point on the stack, the rule is terminated by colon (:). This is sort of intuitive. The lower part of the terminating symbol (. or ,) states whether old backtracks should be allowed, and the top part of it (. or nothing) states whether a new backtrack symbol should be allowed. I have reached the "Hello-world" sortof state. Haven't done much bug testing, but simple grammars can be processed, the relevant productions are marked in the generated parser, and afaics the generated parser seems to work correctly. P.t. I don't handle destructor code, because I could not really understand it. Also I don't understand why the call to "is_expected_token" was added to the innermost loop of the parser. It was not in the c-version, it looks really expensive, and I don't really understand the code in is_expected_token. So I commented it out. Comments? Should I post the whole thing onto this list? Please cc me as I am not subscribed. -Rune