Re: Am implenting backtracking for the parser-generator

Hello Rune, Rune Zedeler wrote: > 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. The best approach will be to open a feature request at http://pear.php.net/bugs/report.php?package=PHP_ParserGenerator Then, after pear.php.net is updated in the next few days to allow patches to be added to the feature request, upload your patch. However, please don't comment out is_expected_token(). This is extremely important code that allows a syntax error to be thrown at the moment it occurs. It's not as expensive as you might think, as expected token list lookups are O(1) and the worst case is only reached when there really is a syntax error. The most common case is a single call to is_expected_token() for the majority of lookahead tokens. There were cases where invalid grammar was slipping right by the generated parsers, with no errors, and it has to do with the weird way Lemon was designed. Perhaps it worked in the C version, but it most certainly didn't in the PHP version. My basic rule of thumb: don't comment out code just because you don't understand it :) However, if you can demonstrate that your feature does not add bloat and is easy to test for correctness, I would definitely consider adding it. Also, do you have a sample grammar that demonstrates the need for the feature? It may be possible to optimize out the need for backtracking by simply performing the proper check for invalid grammar in the action code, which is much more efficient (no parser looping necessary). Thanks, Greg