Re: Am implenting backtracking for the parser-generator

Greg Beaver wrote: Here is a very simple grammar, where backtracking is really nice. Making a LALR(1)-grammar that accepts the same language will basically require you to merge the two kind of separators to one, and make a "date_or_interval" production that accepts from 2 to 6 numbers separated by separators. Afterwards you would have to discard the strings where the separators were wrong. Coming up with further extensions for the language, that ruins this approach and leeds to even more messy grammars is easy. For instance one could add a number-interval (NUMBER TO NUMBER). This would not interfere with the dates in the grammar as given here, because the TO token cannot appear in the outermost numbers. But it would interfere with the genreralised grammar outlines above. %name SimpleExp_ %declare_class {class SimpleExp_yyParser} %include { $parser = new SimpleExp_yyParser; $tokens['/'] = SimpleExp_yyParser::SLASH; $tokens['-'] = SimpleExp_yyParser::DASH; $tokens['1'] = SimpleExp_yyParser::NUMBER; $tokens['t'] = SimpleExp_yyParser::TO; $EOP = SimpleExp_yyParser::EOP; $str = "1-1-1-1"; $parser->doParse($EOP,0); for($i=0; $i< strlen($str); $i++) {

    $token = $tokens[$str{$i}];
    $parser->doParse($token,0);

} $parser->doParse($EOP,0); $parser->doParse(0,0); } %syntax_error {

    foreach ($this->yy_get_expected_tokens($yymajor) as $token) {
        $expect[] = self::$yyTokenName[$token];
    }
    throw new Exception('Unexpected ' . $this->tokenName($yymajor) . '(' . $TOKEN
        . '), expected one of: ' . implode(',', $expect));

} %parse_accept { echo "Accept!\n"; } start ::= EOP interval EOP. start ::= EOP date EOP. interval ::= date to date. date ::= NUMBER datesep NUMBER. date ::= NUMBER datesep NUMBER datesep NUMBER. datesep ::= DASH. datesep ::= SLASH. to ::= DASH. to ::= TO.