Recursive Decent Parsing:Avoiding Backtracking

• An assignment statement is likely one of several types of statements in a language. A complete parser for the language needs to know which type of statement to parse.

• To avoid having to backtrack in parsing, we write our grammar so that we know unambiguously, given one current input look ahead token, which grammar production alternative to choose (Aho section 4.4, Predictive Parsers).

• In many programming languages, the reserved words serve to provide the look ahead token that indicates which type of statement to parse. A language might include several types of statements, each starting with a unique reserved word (see example reserved words below).

• The scanner can recognize the reserved words and return them as token types to the parser, so the parser knows which statement to parse by looking at the one look ahead token. If the look ahead token type isn’t a reserved word, but is an identifier, the parser knows that the statement is an assignment statement. For example, using these statement types:

• ID… | “for”… | “while”… | “switch”… | ...

parser(){

while( tokentype != T_EOF ){

switch( tokentype ){

case ID: assignment(); break;

case FOR: forloop(); break;

case WHILE: whileloop(); break;

case SWITCH: switchstmt(); break;

. . .

default:

error(“Unknown statement type”);

}

}

}